Pytania otagowane jako ds.algorithms

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

9
Zwięzłe wprowadzenie do algorytmów dla matematyków
Szukam zwięzłego tekstu wprowadzającego na temat algorytmów z omówioną teorią wysokiego współczynnikatheory coveredtotal number of pages.theory coveredtotal number of pages.\frac{\mbox{theory covered}}{\mbox{total number of pages}}.Powinno zacząć się od początku, ale potem szybko postępować, nie poświęcając zbyt wiele czasu na przykłady z prawdziwego świata, elementarne techniki dowodowe itp. Jako matematyk badawczy mam …
1
Generowanie labiryntu obrony wieży, czyli Znalezienie K najbardziej istotnych węzłów („interwencja nodewise”) na nieważonym wykresie siatkowym
W grze typu tower defense masz siatkę NxM z początkiem, wykończeniem i wieloma ścianami. Wrogowie podążają najkrótszą ścieżką od początku do końca, nie przechodząc przez ściany (zwykle nie są ograniczeni do siatki, ale dla uproszczenia powiedzmy, że są. W obu przypadkach nie mogą poruszać się po przekątnych „otworach”) Problem (przynajmniej …
1
Propagacja przekonań dla rzeczywistego przybliżenia 3LIN?
W artykule naukowym z 2002 r. Mezard, Parisi i Zecchina przedstawili heurystyczną propagację przekonań dla losowego 3SAT. Eksperymenty wskazują, że heurystyka działa dobrze dla współczynników ograniczeń na zmienną, dla których prawdopodobne jest istnienie zadowalającego przypisania. Moje pytania to: (1) Co się stanie, jeśli weźmiesz pod uwagę losowy 3LIN zamiast losowego …
2
Wykrywanie dwóch rodzajów prawie prostych wielokątów
Interesuje mnie złożoność decydowania, czy dany nie-prosty wielokąt jest prawie prosty, w jednym z dwóch różnych formalnych zmysłów: słabo prostym lub nie-samokreślącym . Ponieważ te terminy nie są powszechnie znane, zacznę od niektórych definicji. Wieloboku jest zamknięty cykl odcinków łączenia kilku skończoną sekwencję punkty na płaszczyźnie. Punkty nazywane są wierzchołkami …
3
Dobre praktyki pisania algorytmów
Chodzi o to, jak skutecznie możemy wyrazić algorytm. Potrzebuję tego do moich studiów licencjackich. Rozumiem, że nie ma czegoś takiego jak standardowy sposób pisania pseudo kodu. Różni autorzy stosują różne konwencje. Byłoby pomocne, gdyby ludzie tutaj wskazywali, w jaki sposób podążają i myślą najlepiej. Czy jest jakaś książka, która zajmuje …
5
Aplikacje Vertex Cover w prawdziwym świecie
Jakie aplikacje mają problemy z wierzchołkiem w prawdziwym świecie? Które projekty branżowe lub badawcze wykorzystują faktycznie zaimplementowane oprogramowanie oparte na teoretycznych wynikach problemu dotyczącego Vertex Cover? W szczególności, czy któryś z poniższych wyników teoretycznych jest wdrażany w używanym oprogramowaniu? Algorytmy aproksymacyjne dla pokrywy wierzchołków Algorytmy czasu wykładniczego dla osłony wierzchołków …
1
Maksymalny przepływ dzięki Ford-Fulkerson i DFS
To pytanie dotyczy złożoności czasowej algorytmu maksymalnego przepływu Forda-Fulkersona podczas korzystania z DFS w celu znalezienia ścieżek rozszerzających. Istnieje dobrze znany przykład pokazujący, że przy użyciu DFS można potrzebować liniowej liczby iteracji w maksymalnym przepływie, patrz na przykład strona Wikipedii, do której prowadzi link powyżej. Jednak tak naprawdę nie przekonuje …
3
Źródło edukacyjne lub ankieta na temat analizy programu półfinałowego?
Podczas projektowania algorytmów aproksymacyjnych czasami rozwiązuje się program półfinałowy, po którym następuje etap zaokrąglania. Często ilustrowanym przykładem jest Max-Cut. (Zobacz np. Algorytmy aproksymacji Vijay Vazirani.) Czy istnieją dobre źródła edukacyjne lub ankiety wykraczające poza problem Max-Cut w celu wyjaśnienia bardziej złożonych algorytmów zaokrąglania i technik wykorzystywanych do ich analizy? Mam …
1
Złożoność obliczania najkrótszych ścieżek w płaszczyźnie z wielokątnymi przeszkodami
Załóżmy, że podano kilka rozłącznych wielokąt prosty w samolocie, a dwa punkty i t zewnątrz każdego wielokąta. Problem najkrótszej ścieżki euklidesowej polega na obliczeniu najkrótszej ścieżki euklidesowej od s do t , która nie przecina wnętrza żadnego wielokąta. Dla konkretności załóżmy, że współrzędne s i t oraz współrzędne każdego wierzchołka …
7
Znajdowanie bliźniaczych wierzchołków na wykresach
Niech będzie wykresem. Przez wierzchołek , określa za (otwarty) sąsiedztwie w . To znaczy, . Zdefiniuj dwa wierzchołki w aby były bliźniakami, jeżeli i mają ten sam zestaw sąsiadów, to znaczy, jeśli .G=(V,E)G=(V,E)G=(V,E)x∈Vx∈Vx\in VN(x)N(x)N(x)xxxGGGN(x)={y∈V|{x,y}∈E}N(x)={y∈V|{x,y}∈E}N(x)=\{y\in V \,\vert\, \{x,y\}\in E\}u,vu,vu,vGGGuuuvvvN(u)=N(v)N(u)=N(v)N(u)=N(v) Biorąc pod uwagę wykres na wierzchołkach i krawędziach jako dane wejściowe, jak …
1
Mnożenie binarne i splot parzystości
To pytanie dotyczy związku między normalnym mnożeniem liczb binarnych a wielomianowym mnożeniem mod 2. Aby uczynić pytanie konkretnym, idealnie chciałbym wiedzieć, czy istnieje lepsze rozwiązanie pytania z Knuth vol. 2, wydanie trzecie, strona 420 niż podano w książce. „Czy mnożenie wielomianów modulo 2 można ułatwić, stosując zwykłe operacje arytmetyczne na …
2
Multiplikatywna wersja 3-SUM
Co wiadomo na temat złożoności czasowej następującego problemu, który nazywamy 3-MUL? Biorąc pod uwagę zestaw z liczb całkowitych, czy są elementami taki sposób, że ?SSSnnna,b,c∈Sa,b,c∈Sa,b,c\in Sab=cab=cab=c Ten problem jest podobny do problemu 3-SUM, który pyta, czy istnieją trzy elementy tak, że (lub równoważnie ). Przypuszcza się, że 3-SUM wymaga czasu …
2
Algorytmy aproksymacji czasu wielomianowego do planowania maszyny: ile pozostało otwartych problemów?
W 1999 r. Petra Schuurman i Gerhard J. Woeginger opublikowali artykuł „Wielomianowe algorytmy aproksymacji czasu dla szeregowania maszynowego: dziesięć otwartych problemów” . Od tego czasu, o ile mi wiadomo, nie pojawiły się recenzje, które dotyczyłyby tej samej listy problemów. Byłoby więc świetnie i przydatne, gdyby każdy z nas mógł sporządzić …
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.