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.

5
Co oznacza szybszy algorytm w informatyce teoretycznej?
Jeśli istnieje algorytm działający w czasie O(f(n))O(f(n))O(f(n)) dla jakiegoś problemu A, a ktoś wymyśli algorytm działający w czasie, , gdzie , czy uważa się to za ulepszenie w stosunku do poprzedniego algorytmu?O(f(n)/g(n))O(f(n)/g(n))O(f(n)/g(n))g(n)=o(f(n))g(n)=o(f(n))g(n) = o(f(n)) Czy ma sens, w kontekście informatyki teoretycznej, wymyślić taki algorytm?
18 algorithms 
3
Dlaczego nie ma algorytmów aproksymacyjnych dla SAT i innych problemów decyzyjnych?
Mam problem z decyzją o zakończeniu NP. Biorąc pod uwagę przykład problemu, chciałbym zaprojektować algorytm, który wyświetli TAK, jeśli problem jest wykonalny, i NIE, w przeciwnym razie. (Oczywiście, jeśli algorytm nie jest optymalny, popełni błędy.) Nie mogę znaleźć algorytmów aproksymacyjnych dla takich problemów. Szukałem w szczególności SAT i na stronie …
2
Wydajne algorytmy dla problemu widoczności pionowej
Myśląc o jednym problemie, zdałem sobie sprawę, że muszę stworzyć wydajny algorytm rozwiązujący następujące zadanie: Problem: otrzymujemy dwuwymiarowe kwadratowe pudełko o boku nnn którego boki są równoległe do osi. Możemy spojrzeć na to z góry. Istnieją jednak również mmm segmenty poziome. Każdy segment ma całkowitą współrzędną yyy ( 0≤y≤n0≤y≤n0 \le …
3
Algorytm sprawdzający, czy język jest pozbawiony kontekstu
Czy istnieje algorytm / systematyczna procedura sprawdzania, czy język jest pozbawiony kontekstu? Innymi słowy, biorąc pod uwagę język określony w formie algebraicznej (pomyśl o czymś takim jak ), sprawdź, czy język jest pozbawiony kontekstu, czy nie . Wyobraź sobie, że piszemy serwis internetowy, który pomaga uczniom we wszystkich zadaniach domowych; …
2
Co jest trudniejsze: tasowanie posortowanej talii lub sortowanie potasowanej talii?
Masz tablicę różnych elementów. Masz dostęp do komparatora (funkcja czarnej skrzynki, która bierze dwa elementy a i b i zwraca prawdziwy iff a &lt; b ) oraz naprawdę losowe źródło bitów (funkcja czarnej skrzynki nie przyjmuje argumentów i zwraca niezależnie jednakowo losowy bit). Rozważ następujące dwa zadania:nnnaaabbba&lt;ba&lt;ba < b Tablica …
4
Rekurencje i funkcje generujące w algorytmach
Kombinatoryka odgrywa ważną rolę w informatyce. Często stosujemy metody kombinatoryczne zarówno w analizie, jak i projektowaniu w algorytmach. Na przykład jedna metoda znajdowania zestawu okładek kkk -vertex na wykresie może po prostu sprawdzić wszystkie możliwe podzbiory . Podczas gdy funkcje dwumianowe rosną wykładniczo, jeśli jest jakąś stałą stałą, w wyniku …
8
Dlaczego możemy założyć, że algorytm może być reprezentowany jako ciąg bitowy?
Zaczynam czytać książkę o złożoności obliczeniowej i maszynach Turinga. Oto cytat: Algorytm (np. Maszyna) może być reprezentowany jako ciąg bitów, gdy zdecydujemy się na pewne kodowanie kanoniczne. To twierdzenie zostało przedstawione jako prosty fakt, ale nie rozumiem tego. Na przykład, jeśli mam algorytm, który przyjmuje jako dane wejściowe i oblicza …
1
Znajdź wielomian w dwóch lub trzech zapytaniach
Czarna ramka oznacza, że ​​mogę ocenić wielomian w dowolnym punkcie.f(x)f(x)f(x)f(x)f(x)f(x) Dane wejściowe : czarne pole wielomianu monicznego stopnia .f(x)∈Z+[x]f(x)∈Z+[x]f(x) \in\mathbb{Z}^+[x]ddd Wydajność: W współczynniki wielomianu .dddf(x)f(x)f(x) Mój algorytm: let f(x)=xd+ad−1xd−1+⋯+a1x+a0f(x)=xd+ad−1xd−1+⋯+a1x+a0f(x) = x^{d} + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0 Oszacuj wielomian w wielu punktach za pomocą czarnej skrzynki …
4
Znajdowanie pary nie nakładających się wektorów bitowych
Daję ci listę wektorów bitowych o szerokości . Twoim celem jest zwrócenie dwóch wektorów bitowych z listy, które nie mają wspólnych 1, lub zgłoszenie, że taka para nie istnieje.n nnkkk Na przykład, jeśli dam ci wówczas jedynym rozwiązaniem jest . Alternatywnie, wejście nie ma rozwiązania. Każda lista zawierająca całkowicie zerowy …
4
Czy problem grafu skończonego jest rozstrzygalny? Jakie czynniki decydują o problemie?
Chcę wiedzieć, czy można rozwiązać następujący problem i jak się dowiedzieć. W każdym problemie, który widzę, mogę powiedzieć „tak” lub „nie”, więc czy większość problemów i algorytmów można rozstrzygać, z wyjątkiem kilku (które podano tutaj )? Wejście: kierowane i skończonych wykres z i , jak wierzchołki Pytanie: Czy ścieżką w …
4
Dlaczego nie używamy szybkiego sortowania na połączonej liście?
Algorytm szybkiego sortowania można podzielić na następujące kroki Zidentyfikuj oś przestawną. Podziel listę połączoną na partycje na podstawie przestawnej. Podziel listę połączoną rekurencyjnie na 2 części. Teraz, jeśli zawsze wybieram ostatni element jako oś przestawną, wówczas identyfikacja elementu przestawnego (1. krok) zajmuje czas.O ( n )O(n)\mathcal O(n) Po zidentyfikowaniu elementu …
3
Największa suma podzielna przez n
Zadałem to pytanie na StackOverflow , ale myślę, że tutaj jest bardziej odpowiednie miejsce. Jest to problem od kursu Wprowadzenie do algorytmów : Musisz tablicę aaa z liczb całkowitych dodatnich (tablica nie muszą być sortowane lub elementów unikalnych). Zaproponuj algorytm , aby znaleźć największą sumę elementów, która jest podzielna przez …
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.