Pytania otagowane jako algorithms

Algorytm jest sekwencją dobrze zdefiniowanych kroków, które definiują abstrakcyjne rozwiązanie problemu. Użyj tego tagu, gdy Twój problem dotyczy projektowania i analizy algorytmów.

3
Algorytm Brzozowskiego do minimalizacji DFA
Algorytm minimalizacji DFA Brzozowskiego buduje minimalny DFA dla DFA poprzez:GGG odwrócenie wszystkich krawędzi w , czyniąc stan początkowy stanem akceptacyjnym, a stanami początkowymi początkowymi, aby otrzymać NFA N ' dla języka odwrotnego,GGGN′N′N' używając konstrukcji powerset, aby uzyskać dla języka odwrotnego,G′G′G' odwrócenie krawędzi (i zamiana początkowej akceptacji) w aby uzyskać NFA …
4
Quicksort wyjaśnił dzieciom
W ubiegłym roku czytałem fantastyczny artykuł na temat „Mechaniki kwantowej dla przedszkola” . To nie był łatwy papier. Zastanawiam się teraz, jak wytłumaczyć quicksort w najprostszych możliwych słowach. Jak mogę udowodnić (lub przynajmniej falę ręczną), że średnia złożoność wynosi i jakie są najlepsze i najgorsze przypadki dla klasy przedszkolnej? A …
6
Dlaczego DFS nie może być używany do znajdowania najkrótszych ścieżek na nieważonych wykresach?
Rozumiem, że użycie DFS „tak jak jest” nie znajdzie najkrótszej ścieżki na nieważonym wykresie. Ale dlaczego poprawianie DFS, aby umożliwić mu znajdowanie najkrótszych ścieżek na nieważonych wykresach, jest tak beznadziejną perspektywą? Wszystkie teksty na ten temat po prostu stwierdzają, że nie można tego zrobić. Nie jestem przekonany (sam tego nie …
2
Czym jest ta struktura / koncepcja danych, w której wykres punktów definiuje podział na przestrzeń
Zetknąłem się z algorytmem rozwiązywania rzeczywistego problemu i pamiętam klasę, w której wziąłem udział, gdzie zrobiłem coś bardzo podobnego dla niektórych na zadanie domowe. Zasadniczo jest to wykres punktów, a linie są rysowane tak, aby były w równej odległości między dwoma punktami. Tworzy idealną przegrodę, w której linie wokół punktu …
8
Kardynalność zbioru algorytmów
Ktoś w dyskusji przywołał, że (uważa) może istnieć co najmniej ciągła liczba strategii podejścia do określonego problemu. Specyficznym problemem były strategie handlowe (nie algorytmy, ale strategie), ale myślę, że to nie ma znaczenia dla mojego pytania. To sprawiło, że pomyślałem o liczności zbioru algorytmów. Trochę szukałem, ale nic nie wymyśliłem. …
9
Jak znaleźć 5 powtarzanych wartości w czasie O (n)?
Załóżmy, że masz tablicę o rozmiarze zawierającą liczby całkowite od do włącznie, z dokładnie pięcioma powtórzeniami. Muszę zaproponować algorytm, który może znaleźć powtarzające się liczby w czasie . Przez całe życie nie mogę myśleć o niczym. Myślę, że sortowanie w najlepszym razie byłoby ? Następnie przejście przez tablicę byłoby , …
2
Skuteczne wstawianie do listy przy minimalnej liczbie inwersji
Załóżmy dwie listy porównywalnych pozycji: u i s. Niech INV (u) będzie liczbą inwersji wu. Szukam wydajnego algorytmu do wstawiania elementów s do u przy minimalnym wzroście INV (u). Zasadniczo chciałbym wstawić obiekty do listy, zachowując ją „tak posortowaną, jak to możliwe”, zachowując kolejność pierwszej listy. Przykład: u = [4,6,2,9,7] …
4
Algorytm Dijkstry na wielkich wykresach
Bardzo dobrze znam Dijkstrę i mam konkretne pytanie dotyczące algorytmu. Jeśli mam ogromny wykres, na przykład 3,5 miliarda węzłów (wszystkie dane OpenStreetMap), to oczywiście nie byłbym w stanie mieć wykresu w pamięci, więc wykres jest przechowywany na dysku w bazie danych. Dostępne są biblioteki do obliczania najkrótszych ścieżek na takich …
1
Testowanie, czy czworościan leży w wielościanie
Mam czworościanu oraz graniastosłupa . jest tak ograniczony, że zawsze dzieli wszystkie swoje wierzchołki z . Chcę ustalić, czy leży wewnątrz .ttt t p tppptttpppttt ppp Chciałbym dodać jeden szczegół do problemu, w przypadku gdy może on przyczynić się do rozwiązania: jest czworościanem Delaunaya, a ściany są trójkątne i silnie …
1
Konstruowanie nierównych macierzy binarnych
Próbuję skonstruować wszystkie nierówne macierze (lub n × n, jeśli chcesz) z elementami 0 lub 1. Operacją, która daje macierze równoważne, jest jednoczesna wymiana wiersza i i j ORAZ kolumny i i j. na przykład. dla 1 ↔ 2 ( 0 0 0 0 1 1 1 0 0 ) …
2
Problemy decyzyjne w
Jakie są przykłady trudnych problemów decyzyjnych, które można rozwiązać w czasie wielomianowym? Szukam problemów, dla których optymalny algorytm jest „wolny” lub problemów, dla których najszybszy znany algorytm jest „wolny”. Oto dwa przykłady: Rozpoznawanie idealnych wykresów. W swojej pracy FOCS'03 [1] Cornuéjols, Liu i Vuskovic podali algorytm czasowy dla problemu, gdzie …
3
Minimalny rozmiar zawarcia DAG w nowy DAG
Mamy DAG. Mamy funkcję na węzłach (luźno mówiąc, numerujemy węzły). Chcielibyśmy utworzyć nowy ukierunkowany wykres z tymi zasadami:fa: V→ N.F:V→NF\colon V\to \mathbb N Tylko węzły o tym samym numerze można zawrzeć w tym samym nowym węźle. . (Jednak .)fa( x ) ≠ F.( y) ⇒ x′. Y′F(x)≠F(y)⇒x′≠y′F(x) \neq F(y) \Rightarrow …
4
Wykres ma dwa / trzy różne minimalne drzewa rozpinające?
Próbuję znaleźć skuteczną metodę wykrywania, czy dany wykres G ma dwa różne minimalne drzewa rozpinające. Próbuję również znaleźć metodę, aby sprawdzić, czy ma 3 różne minimalne drzewa rozpinające. Naiwnym rozwiązaniem, o którym myślałem, jest jednorazowe uruchomienie algorytmu Kruskala i znalezienie całkowitej masy minimalnego drzewa opinającego. Później, usuwając krawędź z wykresu …
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.