Pytania otagowane jako ds.algorithms

Pytania dotyczące dobrze zdefiniowanych instrukcji wykonania zadania oraz odpowiedniej analizy pod względem czasu / pamięci / itp.

1
Przykłady algorytmów i dowodów, które wydają się poprawne, ale nie są
W moim wstępie do kursu programowania dowiadujemy się o metodzie inicjalizacji, konserwacji i terminacji, aby udowodnić, że algorytm działa zgodnie z oczekiwaniami. Musieliśmy jednak tylko udowodnić, że algorytm, o którym wiadomo, że jest poprawny, jest poprawny. Nigdy nie byliśmy proszeni o wykazanie, że algorytm jest nieprawidłowy. Czy są jakieś klasyczne …
3
Nietrudne problemy do rozwiązania w stałym czasie?
Stały czas jest absolutnie niskim stopniem złożoności czasu. Można się zastanawiać: czy jest coś nietypowego, co można obliczyć w stałym czasie? Jeśli trzymamy się modelu maszyny Turinga, niewiele można zrobić, ponieważ odpowiedź może zależeć tylko od początkowego odcinka wejścia o stałej długości, ponieważ dalsze części wejścia nie mogą być osiągnięte …
2
Sortowanie przy użyciu stosów tylko do odczytu
Rozważ następujące ustawienie: daje nam stos , który zawiera n elementów.sssnnn możemy użyć stałej liczby dodatkowych stosów .O(1)O(1)O(1) na tych stosach możemy zastosować następujące operacje: sprawdź, czy stos jest pusty, porównaj najlepsze przedmioty z dwóch stosów, usuń najwyższy element ze stosu, wydrukuj najwyższy element na stosie, skopiuj górny element stosu …
4
Czy eta-równoważność funkcji jest zgodna z sekwencją Haskella?
Lemat: Zakładając, że równoważność eta istnieje (\x -> ⊥) = ⊥ :: A -> B. Dowód: ⊥ = (\x -> ⊥ x)przez eta-równoważność i (\x -> ⊥ x) = (\x -> ⊥)redukcję pod lambda. Raport Haskell 2010, rozdział 6.2 określa seqfunkcję na podstawie dwóch równań: seq :: a -> b …
2
Parametr wykresu prawdopodobnie związany z szerokością
Interesują mnie wykresy nnn wierzchołków, które można wytworzyć w następujący sposób. Zacznij od dowolnego wykresu GsolG na k≤nk≤nk\le n wierzchołków. Oznacz wszystkie wierzchołki w GsolG jako nieużywane . Opracowanie nowego wykres dodaje się nowy wierzchołek V , który jest połączony z jedną lub więcej niewykorzystanych wierzchołków G i nie jest …
1
Czy zerowa luka integralności oznacza zerową lukę dualności dla niektórych problemów?
Wiemy, że jeśli różnica między wartościami programu liczb całkowitych i jego dualności („dualność”) wynosi zero, wówczas liniowe relaksacje programowania programu liczb całkowitych i dualność relaksacji dopuszczają rozwiązania integralne (integralność zerowa) luka"). Chcę wiedzieć, czy konwersacja się utrzymuje, przynajmniej w niektórych przypadkach. Załóżmy, że mam program liczb całkowitych 0-1 , gdzie …
1
Dokładny algorytm dla problemu znakowania krawędzi w DAG
Wdrażam część systemu, która wymaga pomocy. Dlatego kadruję go jako problem graficzny, aby uczynić go niezależnym od domeny. Problem: Otrzymujemy ukierunkowany wykres acykliczny . Bez utraty ogólności załóżmy, że G ma dokładnie jeden wierzchołek źródłowy s i dokładnie jeden wierzchołek tonący ; pozwolić P oznacza zbiór wszystkich skierowanych ścieżek z …
3
Rozdzielenie wstępnie przetworzonego wielościanu i płaszczyzny
Mam poważne problemy ze zrozumieniem jednego kroku w pracy Dobkina i Kirkpatricka o rozdzieleniu wielościanów. Próbuję zrozumieć tę wersję: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf Twierdzi się, że gdy znamy najlepsze oddzielenie PiPiP_{i} i SSS , realizowanego przez ririr_i i sisis_i , można znaleźć oddzielenie Pi−1Pi−1P_{i-1} i SSS w O(1)O(1)O(1) schodów. Odbywa się to w …
4
Teoretyczne badanie metod zejścia ze współrzędnymi
Przygotowuję materiały szkoleniowe na temat heurystyki do optymalizacji i szukam metod zejścia ze współrzędnymi. Ustawienie jest tu wielowymiarowa funkcja , które chcesz zoptymalizować. f ma właściwość ograniczoną do dowolnej pojedynczej zmiennej, którą łatwo zoptymalizować. Tak więc zejście współrzędnych odbywa się cyklicznie przez współrzędne, ustalając wszystko oprócz wybranego i minimalizując wzdłuż …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.