Pytania otagowane jako ds.algorithms

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

3
Czy któryś z najnowszych algorytmów maksymalnego przepływu jest praktyczny?
W przypadku problemu maksymalnego przepływu wydaje się, że istnieje wiele bardzo wyrafinowanych algorytmów, przy czym co najmniej jeden opracowano dopiero w zeszłym roku. Max przepływy Orlina w czasie O (mn) lub lepiej daje algorytm działający w O (VE). Z drugiej strony algorytmy, które najczęściej widzę, są zaimplementowane (nie twierdzę, że …
10
Świetne algorytmy, uczenie maszynowe i brak algebry liniowej
Prowadzę kurs zaawansowanych algorytmów i chciałbym uwzględnić niektóre tematy związane z uczeniem maszynowym, które zainteresują moich studentów. W związku z tym chciałbym usłyszeć opinie ludzi na temat najbardziej interesujących / największych wyników algorytmicznych w uczeniu maszynowym. Potencjalnie trudnym ograniczeniem jest to, że uczniowie nie będą mieli żadnej konkretnej wcześniejszej wiedzy …
10
Aktualne modele równoległe do obliczeń
Lata osiemdziesiąte dały początek modelom obliczeń równoległych PRAM i BSP . Wygląda na to, że okres świetności obu modeli przypadał na przełom lat 80. i 90. Czy obszary te są nadal aktywne w zakresie badań algorytmów równoległych? Czy istnieją nowsze, bardziej wyrafinowane modele do obliczeń równoległych? Czy ogólne modele są …
1
Znalezienie stronniczej monety za pomocą kilku rzutów monetą
Podczas badań pojawił się następujący problem, który jest zaskakująco czysty: Masz źródło monet. Każda moneta ma stronniczość, a mianowicie prawdopodobieństwo upadku na „głowę”. Dla każdej monety niezależnie istnieje prawdopodobieństwo 2/3, że ma ona stronniczość co najmniej 0,9, a przy pozostałym prawdopodobieństwie jej stronniczość może wynosić dowolną liczbę w [0,1]. Nie …
2
Czy potrafisz określić sumę dwóch permutacji w czasie wielomianowym?
Były dwa pytania zadawane niedawno na cs.se które były albo spokrewnione lub miał szczególny przypadek równoznaczne z następującym pytaniem: Załóżmy, że masz ciąg a1,a2,…ana1,a2,…ana_1, a_2, \ldots a_n z nnn liczb takich, że Rozłóż go na sumę dwóch permutacji, i , z , tak aby∑ni=1ai=n(n+1).∑i=1nai=n(n+1).\sum_{i=1}^n a_i = n(n+1).ππ\piσσ\sigma1…n1…n1 \dots nai=πi+σiai=πi+σia_i = …
2
Najczęstsze następstwa
Łańcuch ma podsekwencje, ale zwykle nie wszystkie są odrębne. Jaka jest złożoność znalezienia maksymalnej częstotliwości dowolnego podsekwencji?2n2n2^n Na przykład ciąg „podsekwencja” zawiera 7 kopii podsekwencji „sue” i jest to maksimum. Przykładowy kod brute-force na stronie http://ideone.com/UIp3t Czy istnieją powiązane twierdzenia strukturalne? Oba okazują się fałszywe : najdłuższa z podsekwencji o …
4
Problemy „ukierunkowane”, które są łatwiejsze niż ich wariant „niekierowany”.
Prezentowałem wykład na temat sortowania naleśników i wspomniałem, że: Sortowanie według zamian jest trudne „podpisany” sortując odwrócenia jest w P . Co skłoniło mnie do myślenia. W pewnym sensie sortowanie „sygnowane” jest „ukierunkowane” - możesz postrzegać znak jako kierunek (i rzeczywiście jest to motywacja z biologii ewolucyjnej). Ale to łatwiejszy …
16
Trudno wyglądające problemy algorytmiczne ułatwiane przez twierdzenia
Szukam ładnych przykładów, w których występuje następujące zjawisko: (1) Problem algorytmiczny wygląda na trudny, jeśli chcesz go rozwiązać, korzystając z definicji i używając tylko standardowych wyników. (2) Z drugiej strony staje się łatwe, jeśli znasz jakieś (nie tak standardowe) twierdzenia. Ma to na celu zilustrowanie uczniom, że uczenie się większej …
4
Maksymalne klasy, dla których największy niezależny zbiór można znaleźć w czasie wielomianowym?
W ISGCI listy ponad 1100 klas grafów. W przypadku wielu z nich wiemy, czy można ustalić niezależny zestaw w czasie wielomianowym; nazywane są czasem klasami IS-easy . Chciałbym skompilować listę maksymalnych klas IS-easy. Klasy te razem tworzą granicę (znanej) podatności na rozwiązywanie tego problemu. Ponieważ do dowolnej nieskończonej klasy IS-easy …
3
Jak stworzyć losowy wykres, który nie ma cyklu hamiltonowskiego?
Niech klasa A oznacza wszystkie wykresy wielkości które mają cykl hamiltonowski. Z tej klasy łatwo jest utworzyć losowy wykres - weź n izolowanych węzłów, dodaj losowy cykl hamiltonowski, a następnie losowo dodaj krawędzie.nnnnnn Niech klasa B oznacza wszystkie wykresy wielkości które nie mają cyklu hamiltonowskiego. Jak możemy wybrać losowy wykres …
10
Algorytmy probabilistyczne (randomizowane) przed pojawieniem się „nowoczesnej” informatyki
Edycja: wybieram odpowiedź z najwyższym wynikiem do 6 grudnia 2012 r. To delikatne pytanie. Pojęcie (deterministycznych) algorytmów sięga BC. Co z algorytmami probabilistycznymi? W tym wpisie wiki algorytm Rabina dla problemu najbliższej pary w geometrii obliczeniowej podano jako pierwszy algorytm losowy (rok ???). Lipton wprowadził algorytm Rabina jako początek ery …
4
Złożoność zastosowania permutacji w miejscu
Ku mojemu zaskoczeniu nie udało mi się znaleźć artykułów na ten temat - prawdopodobnie przeszukałem niewłaściwe słowa kluczowe. Mamy więc tablicę czegokolwiek i funkcję na jej indeksach; jest permutacją.ffffff Jak zmienić kolejność tablic zgodnie z pamięcią i czasem działania tak blisko i jak to możliwe?fffO(1)O(1)O(1)O(n)O(n)O(n) Czy są jakieś dodatkowe warunki, …
2
Czy można sprawdzić, czy sekwencja istnieje w czasie wielomianowym w następującym problemie?
Przez jakiś czas myślałem o następującym problemie i nie znalazłem rozwiązania wielomianowego. Tylko brutalne źródło. Próbowałem też zredukować problem NP-Complete bez powodzenia. Oto problem : Masz posortowany zestaw {(A1,B1),(A2,B2),…,(An,Bn)}{(A1,B1),(A2,B2),…,(An,Bn)}\{(A_1, B_1), (A_2, B_2), \ldots, (A_n, B_n)\} par dodatnich liczb całkowitych. (Ai,Bi)&lt;(Aj,Bj)⇔Ai&lt;Aj∨(Ai=Aj∧Bi&lt;Bj)(Ai,Bi)&lt;(Aj,Bj)⇔Ai&lt;Aj∨(Ai=Aj∧Bi&lt;Bj)(A_i, B_i) < (A_j, B_j) \Leftrightarrow A_i < A_j \lor (A_i …
1
Inne zastosowania wzmocnienia rozgałęzień Karger-Stein?
Właśnie nauczyłem losowego algorytmu skrótu Karger-Stein w mojej klasie algorytmów dla absolwentów. To prawdziwy klejnot algorytmiczny , więc nie mogę tego nie uczyć, ale zawsze denerwuje mnie, ponieważ nie znam innych zastosowań głównej techniki. (Trudno więc przypisać pracę domową, która doprowadzi ten punkt do domu.) Algorytm Kargera i Steina jest …
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.