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.

1
Jak czas działania algorytmu Ukkonen zależy od wielkości alfabetu?
Niepokoi mnie kwestia asymptotycznego czasu działania algorytmu Ukkonena , być może najpopularniejszego algorytmu do konstruowania drzewek sufiksów w czasie liniowym (?). Oto cytat z książki „Algorytmy na strunach, drzewach i sekwencjach” Dana Gusfielda (sekcja 6.5.1): „... wszystkie algorytmy Aho-Corasick, Weiner, Ukkonen i McCreight wymagają albo przestrzeni , albo ograniczenie czasowe …
1
Ważona suma ostatnich N liczb
Załóżmy, że otrzymujemy liczby w strumieniu. Po otrzymaniu każdej liczby należy obliczyć ważoną sumę ostatnich liczb, przy czym wagi są zawsze takie same, ale dowolne.NNN Jak skutecznie można to zrobić, jeśli pozwolimy zachować strukturę danych, która pomoże w obliczeniach? Czy możemy zrobić coś lepszego niż , tj. Przeliczać sumę za …
3
Dlaczego warto używać porównań zamiast środowiska wykonawczego do porównywania dwóch algorytmów?
Zauważam, że w kilku artykułach z badań CS, w celu porównania wydajności dwóch algorytmów, zamiast samych rzeczywistych czasów obliczeniowych użyto całkowitej liczby kluczowych porównań w algorytmach. Dlaczego nie możemy porównać, który z nich jest lepszy, uruchamiając oba programy i licząc całkowity czas potrzebny do uruchomienia algorytmów?
1
Generujesz dane wejściowe dla algorytmów graficznych do testowania losowego?
Podczas testowania algorytmów powszechnym podejściem jest testowanie losowe: generuj znaczną liczbę danych wejściowych zgodnie z pewnym rozkładem (zwykle jednolitym), uruchom na nich algorytm i sprawdź poprawność. Nowoczesne ramy testowania mogą generować dane wejściowe automatycznie na podstawie podpisu algorytmów, z pewnymi ograniczeniami. Jeśli dane wejściowe są liczbami, listami lub łańcuchami, generowanie …
3
Linia oddziela dwa zestawy punktów
Czy istnieje sposób na stwierdzenie, czy dwa zestawy punktów można oddzielić linią? Mamy dwa zestawy punktów i jeśli istnieje linia, która oddziela i tak że wszystkie punkty i tylko po jednej stronie linii oraz wszystkie punkty i tylko po drugiej stronie.B A B A A B BAAABBBAAABBBAAAAAABBBBBB Najbardziej naiwnym algorytmem, …
5
Maksymalny niezależny zestaw wykresu dwudzielnego
Próbuję znaleźć maksymalny niezależny zestaw wykresu biparytu. W niektórych notatkach „13 maja 1998 r. - University of Washington - CSE 521 - Zastosowania przepływu sieci” znalazłem : Problem: Biorąc pod uwagę dwudzielny wykres , znalezienie niezależnego zestawu , który jest tak duży, jak to tylko możliwe, w którym i . …
1
rozproszone przycinanie alfa beta
Szukam wydajnego algorytmu, który pozwala mi przetwarzać drzewo wyszukiwania minimax dla szachów z przycinaniem alfa-beta w architekturze rozproszonej. Algorytmy, które znalazłem (PVS, YBWC, DTS, patrz poniżej) są dość stare (najpóźniej 1990). Zakładam, że od tego czasu nastąpiło wiele istotnych postępów. Jaki jest obecny standard w tej dziedzinie? Proszę również wskazać …
3
Maksymalny krąg zamykający danego promienia
Próbuję znaleźć podejście do następującego problemu: Biorąc pod uwagę zestaw punktu i promień , znajdź punkt środkowy okręgu, tak aby okrąg zawierał maksymalną liczbę punktów ze zbioru. Czas działania powinien wynosić .SSSrrrO(n2)O(n2)O(n^2) Na początku wydawało się, że jest to coś podobnego do najmniejszego otaczającego problemu, które można łatwo rozwiązać w …
2
Algorytmy sprawdzania typu
Zaczynam osobiste badanie bibliograficzne algorytmów sprawdzania typu i chcę uzyskać wskazówki. Jakie są najczęściej stosowane algorytmy sprawdzania typu, strategie i techniki ogólne? Szczególnie interesują mnie złożone algorytmy sprawdzania typu, które zostały zaimplementowane w powszechnie znanych, silnie statycznych językach, takich jak na przykład C ++, Java 5+, Scala lub inne. IE, …
5
Rozróżnienie przypadków w programowaniu dynamicznym: potrzebny przykład!
Od jakiegoś czasu pracuję nad programowaniem dynamicznym. Kanonicznym sposobem oceny dynamicznej rekurencji programowania jest utworzenie tabeli wszystkich niezbędnych wartości i wypełnienie jej wiersz po wierszu. Zobacz na przykład Cormen, Leiserson i in .: „Wprowadzenie do algorytmów” . Skupiam się na opartym na tabeli schemacie obliczeń w dwóch wymiarach (wypełnianie wiersz …
6
Czym różni się programowanie dynamiczne od siły Brute?
Czytałem o Programowaniu dynamicznym, kiedy natknąłem się na następujący cytat Algorytm programowania dynamicznego zbada wszystkie możliwe sposoby rozwiązania problemu i wybierze najlepsze rozwiązanie. Dlatego z grubsza możemy myśleć o programowaniu dynamicznym jako inteligentnej metodzie brutalnej siły, która pozwala nam przejść przez wszystkie możliwe rozwiązania, aby wybrać najlepsze . Jeśli zakres …
1
Wydajne obliczanie lub przybliżanie wymiaru VC sieci neuronowej
Moim celem jest rozwiązanie następującego problemu, który opisałem na podstawie jego danych wejściowych i wyjściowych: Wejście: Kierunkowy wykres acykliczny z m węzłami, n źródłami i 1 ujściem ( m > n ≥ 1 ).GGGmmmnnn111m>n≥1m>n≥1m > n \geq 1 Wynik: VC wymiar (lub zbliżanie niego) dla sieci neuronowej z topologii .GGG …
4
Cel szarego węzła w wyszukiwaniu na głębokości pierwszego wykresu
W wielu implementacjach pierwszego wyszukiwania głębokości, które widziałem (na przykład: tutaj ), kod rozróżnia szary wierzchołek (wykryty, ale nie odwiedzono wszystkich jego sąsiadów) i czarny wierzchołek (odkryty i odwiedzono wszystkich jego sąsiadów) . Jaki jest cel tego rozróżnienia? Wygląda na to, że algorytm DFS nigdy nie odwiedzi odwiedzonego wierzchołka, niezależnie …
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.