Pytania otagowane jako ds.algorithms

Pytania dotyczące dobrze zdefiniowanych instrukcji wykonania zadania oraz odpowiedniej analizy pod względem czasu / pamięci / itp.

30
Algorytmy z książki.
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 algorytm byłby kandydatem (kandydatami)? Jeśli to możliwe, proszę …
29
Wdrożone podstawowe algorytmy
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 używane oprogramowanie / sprzęt. Szukam takich przykładów, które spełniają następujące …
2
Problem z Super Mario Galaxy
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 , wektor kierunku (w płaszczyźnie pewnej ścianki zawierającej ) i odległość …
11
Jak trudne jest tasowanie sznurka?
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, ponieważ jest to przetasowanie ABCDi ABCD, ale ciąg ABCDDCBAnie jest kwadratowy. Czy istnieje …
17
Przykłady ceny abstrakcji?
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]. Oczywiście algorytm Strassena nie przestrzega tego ograniczenia i jest asymptotycznie lepszy niż eliminacja Gaussa. …
2
Jaka jest faktyczna złożoność czasowa eliminacji Gaussa?
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 przykład, załóżmy, że chcemy diagonalizować następującą macierz:O(n3)O(n3)O(n^3)O(n3)O(n3)O(n^3) ⎡⎣⎢⎢⎢⎢⎢⎢⎢211⋮1021⋮1002⋮1⋯⋯⋯⋱⋯000⋮2⎤⎦⎥⎥⎥⎥⎥⎥⎥[200⋯0120⋯0112⋯0⋮⋮⋮⋱⋮111⋯2]\begin{bmatrix} 2 & 0 & …
9
Potężne algorytmy zbyt skomplikowane do wdrożenia
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 bezużytecznym w praktyce. Szukam algorytmów, które mogłyby mieć praktyczną wartość, ale są …
4
Dowody na to, że mnożenie macierzy można przeprowadzić w czasie kwadratowym?
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 uznać za dowód na .ω=2ω=2\omega = 2 Naiwnie wydaje mi …
10
Jeden stos, dwie kolejki
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 powiedział, że zapomniał dowodu i …
10
Sprawdzalne stwierdzenia na temat algorytmów genetycznych
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 technika podobna do GA jest dość skuteczna w przypadku …
7
Dla jakich problemów w P łatwiej jest zweryfikować wynik niż go znaleźć?
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 można znaleźć również w czasie wielomianowym, więc nie wydaje się oczywiste, kiedy weryfikacja jest szybsza …
13
Dla jakich algorytmów istnieje duża luka między analizą teoretyczną a 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 eksperymentalne sugerują silniejszą asymptozę, albo (b) istnieją algorytmy …
8
Czy istnieją dowody istnienia niekonstruktywnego algorytmu?
Pamiętam, że mogłem spotkać odniesienia do problemów, które zostały udowodnione, że można je rozwiązać ze szczególną złożonością, ale bez znanego algorytmu, który by faktycznie osiągnął tę złożoność. Walczę z tym, jak to się dzieje; jak wyglądałby niekonstruktywny dowód na istnienie algorytmu. Czy rzeczywiście istnieją takie problemy? Czy mają dużą wartość …
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.