Pytania dotyczące dobrze zdefiniowanych instrukcji wykonania zadania oraz odpowiedniej analizy pod względem czasu / pamięci / itp.
Paul Erdos mówił o „Księdze”, w której Bóg przechowuje najbardziej elegancki dowód każdego twierdzenia matematycznego. To nawet zainspirowało książkę (która, jak sądzę, jest teraz w czwartym wydaniu): Dowody z książki . Gdyby Bóg miał podobną książkę na temat algorytmów, jaki według ciebie...
Aby zademonstrować znaczenie algorytmów (np. Dla studentów i profesorów, którzy nie zajmują się teorią lub nawet pochodzą z zupełnie innych dziedzin), czasem warto mieć pod ręką listę przykładów, w których podstawowe algorytmy zostały zastosowane w celach komercyjnych, rządowych, lub powszechnie...
Załóżmy, że Mario chodzi po powierzchni planety. Jeśli zacznie chodzić ze znanego miejsca, w ustalonym kierunku, na określoną odległość, jak szybko możemy ustalić, gdzie się zatrzyma? Bardziej formalnie, załóżmy, że otrzymujemy wypukły politop w 3-przestrzeni, punkt początkowy na powierzchni ,...
Losowanie dwóch ciągów znaków polega na przeplataniu znaków w nowy ciąg znaków, utrzymując porządek znaków każdego łańcucha. Na przykład, MISSISSIPPIjest losowanie MISIPPi SSISI. Nazwijmy kwadrat ciągów, jeśli jest to tasowanie dwóch identycznych ciągów. Na przykład ABCABDCDjest kwadratowy,...
Informatyka teoretyczna dostarczyła kilka przykładów „ceny abstrakcji”. Dwa najbardziej znaczące dotyczą eliminacji i sortowania Gaussa. Mianowicie: Wiadomo, że eliminacja Gaussa jest optymalna do, powiedzmy, obliczenia wyznacznika, jeśli ograniczysz operacje do wierszy i kolumn jako całości [1]....
W ostatnich latach opracowano wiele algorytmów wyszukiwania ścieżek, które potrafią obliczyć najlepszą ścieżkę w odpowiedzi na zmiany wykresu znacznie szybciej niż A * - czym one są i czym się różnią? Czy są w różnych sytuacjach, czy też niektóre są przestarzałe? Oto te, które do tej pory udało...
W odpowiedzi na wcześniejsze pytanie wspomniałem o powszechnym, ale fałszywym przekonaniu, że eliminacja „gaussowska” przebiega w czasie . Chociaż oczywiste jest, że algorytm wykorzystuje operacje arytmetyczne , nieostrożna implementacja może tworzyć liczby z wykładniczo wieloma bitami. Jako prosty...
Jakie są algorytmy legalnej użyteczności, które są po prostu zbyt skomplikowane, aby je zaimplementować? Wyjaśnię: nie szukam algorytmów takich jak obecny asymptotyczny algorytm optymalnego mnożenia macierzy (Coppersmith-Winograd), który jest rozsądny do wdrożenia, ale ma stałą, która czyni go...
Czy znasz rozsądne algorytmy działające w czasie wielomianowym w (Długość wejściowa + Długość wyjściowa), ale których asymptotyczny czas działania w tej samej mierze ma naprawdę ogromny wykładnik / stałą (przynajmniej tam, gdzie jest udowodniona górna granica czasu działania taka...
Powszechnie przypuszcza się, że , optymalny wykładnik mnożenia macierzy, w rzeczywistości jest równy 2. Moje pytanie jest proste:ωω\omega Jakie mamy powody, by sądzić, że ?ω=2ω=2\omega = 2 Mam świadomość szybkich algorytmów, takich jak Coppersmith-Winograd, ale nie wiem, dlaczego można je...
tło Kilka lat temu, kiedy byłem studentem, otrzymaliśmy zadanie domowe z analizy zamortyzowanej. Nie udało mi się rozwiązać jednego z problemów. Poprosiłem o to w teorii porównawczej , ale nie uzyskałem zadowalającego rezultatu. Pamiętam kurs, który TA nalegał na coś, czego nie mógł udowodnić, i...
Algorytmy genetyczne nie cieszą się dużą popularnością w świecie teorii, ale są one dość dobrze stosowaną metodą metaheurystyczną (przez metaheurystyczny mam na myśli technikę, która ogólnie stosuje się w wielu problemach, takich jak wyżarzanie, opadanie gradientu i tym podobne). W rzeczywistości...
Istnieją dwa sposoby analizy wydajności algorytmu nałożyć asymptotyczną górną granicę czasu działania, oraz aby go uruchomić i zebrać dane eksperymentalne. Zastanawiam się, czy są znane przypadki, w których istnieje znaczna różnica między (1) a (2). Rozumiem przez to, że albo (a) dane...
W przypadku (wyszukiwania wersji) problemów z NP zakończonych weryfikacja rozwiązania jest wyraźnie łatwiejsza niż znalezienie, ponieważ weryfikacja może być przeprowadzona w czasie wielomianowym, podczas gdy znalezienie świadka zajmuje (prawdopodobnie) wykładniczy czas. Jednak w P rozwiązanie...
Załóżmy, że mam ukierunkowany wykres acykliczny z wagami liczb rzeczywistych na jego wierzchołkach. Chcę znaleźć uporządkowanie topologiczne DAG, w którym dla każdego prefiksu uporządkowania topologicznego suma wag jest nieujemna. Lub jeśli wolisz terminologię teoretyczną, mam ważoną częściową...
Zawsze miałem problem ze zrozumieniem znaczenia luki integralności (IG) i ją ograniczam. IG jest stosunkiem (jakości) optymalnej liczby całkowitej do (jakości) optymalnego rzeczywistego rozwiązania złagodzenia problemu. Rozważmy przykrycie wierzchołków (VC) jako przykład. VC można określić jako...
Szukam domysłów na temat algorytmów i złożoności, które przez pewien czas były postrzegane przez wielu jako wiarygodne, ale później zostały one obalone lub przynajmniej niewiary, z powodu narastających kontr-dowodów. Oto dwa przykłady: Hipoteza o losowej wyroczni: relacje między klasami...
Gdybyś mógł zmienić nazwę programowania dynamicznego, jak byś to
Jakie są teoretyczne wyjaśnienia praktycznego sukcesu solverów SAT i czy ktoś może dać przegląd i wyjaśnienie w stylu „wikipedii” łącząc je wszystkie? Analogicznie, wygładzona analiza ( wersja arXiv )) dla algorytmu simplex świetnie się tłumaczy, dlaczego działa tak dobrze w praktyce, mimo że w...
W innym wątku Joe Fitzsimons zapytał o „najlepsze obecne dolne granice 3SAT”. Chciałbym pójść w drugą stronę: jakie są najlepsze obecne górne granice 3SAT? Innymi słowy, jaka jest złożoność czasowa najbardziej wydajnego solvera SAT? W szczególności, czy można sobie wyobrazić algorytm...