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.

8
Czy każdy typ danych po prostu sprowadza się do węzłów ze wskaźnikami?
Tablica lub wektor to tylko sekwencja wartości. Z pewnością można je zaimplementować za pomocą połączonej listy. To tylko kilka węzłów ze wskaźnikami do następnego węzła. Stosy i kolejki to dwa abstrakcyjne typy danych powszechnie nauczane na kursach CS wprowadzających. Gdzieś w klasie uczniowie często muszą implementować stosy i kolejki, używając …
4
Rezerwuj algorytmy poza Cormen
Skończyłem większość materiału w książce Cormen's Intro to Algorytmy i szukam książki o algorytmach, która obejmowałaby materiał poza książką Cormana. Czy są jakieś rekomendacje? UWAGA: Zapytałem o to przy przepełnieniu stosu, ale nie byłem zbyt zadowolony z odpowiedzi. UWAGA: Patrząc na większość komentarzy, myślę, że idealnie chciałbym znaleźć książkę, która …
1
Kompresja nazw domen
Jestem ciekawy, jak można bardzo kompaktowo skompresować domenę dowolnej nazwy hosta IDN (zgodnie z definicją w RFC5890 ) i podejrzewam, że może to stać się ciekawym wyzwaniem. Host lub nazwa domeny Unicode (etykieta U) składa się z ciągu znaków Unicode, zwykle ograniczonego do jednego języka w zależności od domeny najwyższego …
3
Jak rygorystycznie sformułować problem obliczeniowy?
Często wchodzę w interakcje z ludźmi, którzy chcą poprosić o algorytm dla problemu obliczeniowego (lub jego złożoności), ale nie wyrażają go w sposób rygorystyczny dla nas (informatyków) do zrozumienia. Odsyłanie ich do książek takich jak CLRS nie jest pomocne, ponieważ tamtejsze przykłady zwykle mają dość prosty sposób rygorystycznego określania, np. …
3
Praktyczne zastosowania Radix Sort
Sortowanie Radix jest teoretycznie bardzo szybkie, gdy wiesz, że klucze znajdują się w pewnym ograniczonym zakresie, np. wartości z zakresu [ 0 … n k - 1 ] . Jeśli k < lg n po prostu przekonwertujesz wartości na bazę n, co zajmuje Θ ( n ) czasu, wykonaj sortowanie …
2
Uzyskiwanie ujemnego cyklu za pomocą Bellmana Forda
Muszę znaleźć cykl ujemny na ukierunkowanym wykresie ważonym. Wiem, jak działa algorytm Bellmana Forda i który mówi mi, czy istnieje możliwy do osiągnięcia cykl ujemny. Ale nie określa go wprost. Jak uzyskać rzeczywistą ścieżkę cyklu?v1,v2,…vk,v1v1,v2,…vk,v1v1, v2, \ldots vk, v1 Po zastosowaniu standardowego algorytmu wykonaliśmy już iteracji i dalsza poprawa nie …
1
Problemy, dla których algorytmy oparte na zawężaniu partycji działają szybciej niż w czasie logarytmicznym
Udoskonalenie partycji to technika, w której zaczynasz od skończonego zestawu obiektów i stopniowo dzielisz zestaw. Niektóre problemy, takie jak minimalizacja DFA, można rozwiązać dość skutecznie za pomocą zawężania partycji. Nie znam żadnych innych problemów, które zwykle rozwiązuje się za pomocą udoskonalenia partycji innych niż te wymienione na stronie Wikipedii. Spośród …
3
Jak trudno jest znaleźć dyskretny logarytm?
bbbab=cmodNab=cmodNa^b=c \bmod NaaacccNNN Zastanawiam się, w jakich grupach złożoności (np. Dla komputerów klasycznych i kwantowych) to jest i jakie podejścia (tj. Algorytmy) są najlepsze do wykonania tego zadania. Powyższy link do Wikipedii tak naprawdę nie zapewnia bardzo konkretnych środowisk uruchomieniowych. Mam nadzieję na coś bardziej podobnego do najbardziej znanych metod …
3
Problemy w P z znacznie szybszymi algorytmami randomizowanymi
Czy są jakieś problemy w które mają algorytmy losowe przekraczające dolne granice algorytmów deterministycznych? Mówiąc konkretniej, czy znamy jakieś dla którego ? Tutaj \ mathsf {PTIME} (f (n)) oznacza zestaw języków rozstrzygalnych przez losową TM z błędem o stałym ograniczeniu (jedno- lub dwustronny) w krokach f (n) .PP\mathsf{P}kkkDTIME(nk)⊊PTIME(nk)DTIME(nk)⊊PTIME(nk)\mathsf{DTIME}(n^k) \subsetneq \mathsf{PTIME}(n^k)PTIME(f(n))PTIME(f(n))\mathsf{PTIME}(f(n))f(n)f(n)f(n) …
2
Jak opisywać algorytmy, je udowadniać i analizować?
Przed przeczytaniem „Sztuki programowania komputerowego” (TAOCP) nie zastanawiałem się głęboko nad tymi pytaniami. Używałbym pseudokodu do opisywania algorytmów, rozumienia ich i szacowania czasu działania tylko o rzędach wzrostu. TAOCP gruntownie zmienia zdanie. TAOCP używa angielskiego mieszanego z krokami i goto do opisywania algorytmu, i wykorzystuje schematy blokowe do łatwiejszego zobrazowania …
4
Jak użyć chciwego algorytmu, aby znaleźć malejącą sekwencję najbliższą podanej?
Otrzymujesz n liczb całkowitych wszystkie od do . Pod każdą liczbą całkowitą należy wpisać liczbę całkowitą między a z warunkiem, że tworzą ciąg nie malejący. Zdefiniuj odchylenie takiej sekwencji na . Zaprojektuj algorytm, który znajdzie b_i z minimalnym odchyleniem w czasie wykonywania O (n \ sqrt [4] {l}) .a1,…,ana1,…,ana_1, \ldots, …
1
Algorytm ścigania ruchomego celu
Załóżmy, że mamy czarną skrzynkę fff którą możemy wyszukać i zresetować. Kiedy przywrócić fff stan fSfSf_S o fff ma wartość pierwiastka wybranego losowo równomiernie ze zbioru {0,1,...,n−1}{0,1,...,n−1}\{0, 1, ..., n - 1\} gdzie nnn jest ustalone i znane dla danego fff . Do zapytania fff , element xxx (przypuszczenie) z …
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.