Dopasowanie jest podzbiorem krawędzi grafu, tak że żadna krawędź w podzbiorze nie ma wspólnego wierzchołka z innym.
Mądrzy inni redaktorzy Wikipedii odrzucili moją prośbę o przeniesienie artykułu z Wikipedii na temat algorytmu Rabin – Karp do tego, co moim zdaniem powinno się nazywać, algorytm Karp – Rabin, ponieważ częściej używa się nazwy Rabin – Karp ( fałsz, jeśli ktoś idzie według liczb uczonego Google) lub...
Biorąc pod uwagę ogromną bazę dozwolonych słów (posortowane alfabetycznie) i słowo, znajdź słowo z bazy danych, która jest najbliższa podanemu słowu pod względem odległości Levenshteina. Naiwnym podejściem jest oczywiście po prostu obliczenie odległości levenshteina między danym słowem a...
Problem stabilnego małżeństwa: http://en.wikipedia.org/wiki/Stable_marriage_problem Zdaję sobie sprawę, że w przypadku SMP możliwe jest wiele innych stabilnych małżeństw, z wyjątkiem algorytmu Gale-Shapleya. Jeśli jednak otrzymamy tylko , liczbę mężczyzn / kobiet, zadajemy następujące pytanie: Czy...
Jakie są znane wyniki znalezienia dokładnej n-wymiarowej podtablicy wewnątrz n-wymiarowej tablicy? W 1D jest to tylko problem dopasowania łańcucha, KMP robi to w czasie liniowym. W 2D ten dokument pokazał, że można to zrobić w czasie liniowym z niewielką dodatkową przestrzenią. Czy ten problem...
Niech będzie prostym grafem bezkierunkowym i niech będą odrębnymi wierzchołkami. Niech długość prostej ścieżki st będzie liczbą krawędzi na ścieżce. Interesuje mnie obliczenie maksymalnego rozmiaru zestawu prostych ścieżek st, tak że każda ścieżka ma nieparzystą długość, a zestawy wierzchołków...
Załóżmy, że otrzymujemy macierz n przez n, M, z wpisami liczb całkowitych. Czy możemy zdecydować w P, czy istnieje permutacjaσσ\sigma taka, że dla wszystkich permutacji mamy ?π≠ σπ≠σ\pi\ne\sigmaΠ Mi σ( i )≠ Õ Mi π( i )ΠM.jaσ(ja)≠ΠM.jaπ(ja)\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)} Uwagi Oczywiście...
Ja jako dane wyjściowe DAG z n wierzchołków gdzie każdy wierzchołek x dodatkowo znakowane pewnym S ( x ) ⊆ { 1 , ... , N } .GGGnnnxxxS(x)⊆{1,…,n}S(x)⊆{1,…,n}S(x) \subseteq \{1, \ldots, n\} Topologicznym rodzajem jest bijection f z wierzchołków G do { 1 , … , n } taki, że dla wszystkich x , y ,...
Zastanów się nad problemem znalezienia maksymalnej liczby rycerzy, którzy mogą zostać postawieni na szachownicy bez atakowania się dwóch z nich. Odpowiedź brzmi 32: nie jest zbyt trudno znaleźć idealne dopasowanie (wykres wywołany ruchami rycerza jest dwustronny, i istnieje idealne dopasowanie dla...
W artykule Randomized Primal-Dual analiza RANKING dla Online Dwustronnego dopasowywania , udowadniając jednocześnie, że algorytm RANKING jest -konkurencyjne, autorzy pokazują, że dualność jest wykonalna w oczekiwaniu (patrz Lemat 3 na stronie 5). Moje pytanie brzmi:(1−1e)(1−1e)\left(1 -...
Razborov udowodnił, że dopasowanie funkcji monotonicznej nie występuje w MP . Ale czy możemy obliczyć dopasowanie za pomocą obwodu wielkości wielomianowej z kilkoma negacjami? Czy istnieje obwód P / poli z który oblicza dopasowanie? Jaki jest kompromis między liczbą negacji a rozmiarem...
Motywacja: Współautor redaguje manuskrypt i chciałbym zobaczyć jasne podsumowanie edycji. Wszystkie narzędzia podobne do „diff” są zwykle bezużyteczne, jeśli zarówno przenosisz tekst (np. Reorganizując strukturę), jak i edytujesz lokalnie. Czy to naprawdę takie trudne? Definicje: Chciałbym...
Razborov udowodnił, że każdy obwód monotoniczny, który oblicza idealną funkcję dopasowania dla grafów dwustronnych, musi mieć co najmniej bramek (nazwał to „logicznym stałym”). Czy od tego czasu udowodniono lepszą dolną granicę dla tego samego problemu? (powiedzmy 2 n ϵ ?) O ile pamiętam ten...
Biorąc pod uwagę ciąg , okładka palindromu jest sekwencją słów tak że i takie, że każdy jest palindromem.w=σ1σ2…σnw=σ1σ2…σnw=\sigma_1\sigma_2\ldots\sigma_np1p2⋯pmp1p2⋯pmp_1p_2\cdots p_mpipip_ip1p2⋯pm=wp1p2⋯pm=wp_1p_2\cdots p_m = wpipip_i Jak trudno jest znaleźć minimalną wielkość palindromu?...
Czy w literaturze jest coś zbliżonego do następującego problemu: Biorąc pod uwagę dwuczęściowy wykres ze zrównoważonym dwuczęściowym , czy istnieje idealne dopasowanie w tak że dla każdej 2 krawędzi występuje krawędź lub krawędź (lub oba) w ?G ( V, E)G(V,E)G(V,E){ U, W}{U,W} \{U,W\}M.M M solG G...
To może brzmieć bardziej jak pytanie z nauk społecznych niż TCS, ale tak nie jest. Czytając „ Randomizowane algorytmy ” opisujące problem stabilnego małżeństwa, można przeczytać następujące informacje (str. 54) „Można wykazać, że dla każdego wyboru list preferencji istnieje co najmniej jedno...
W moim starym czeskim podręczniku algorytmów natknąłem się na następujący problem, niestety przyszedł bez wskazówek i rozwiązania. „Określamy Fibonacciego słów , , , gdzie i są ogólnie literami. Jak w danej ciąg (ponad potencjalnie dużym alfabetem) czy możesz znaleźć najdłuższe pod-słowo...
Biorąc pod uwagę dwudzielny wykres G=(U∪V,E)G=(U∪V,E)G = (U \cup V, E) z dodatnimi wagami, niech f:2U→Rf:2U→Rf: 2^U \rightarrow \mathbb{R} z f(S)f(S)f(S) równym maksymalnemu dopasowaniu masy na wykresie .G[S∪V]G[S∪V]G[S\cup V] Czy to prawda, że jest funkcją
Motywacja : Opracowując narzędzia do wersjonowania danych, zaczęliśmy szukać algorytmów do „różnicowania” dwóch zestawów liczb całkowitych, wymyślając sekwencję przekształceń, które przenoszą jeden zestaw liczb całkowitych na drugi. Udało nam się zredukować ten problem do następującego bardzo...
Mam następujący problem: Dane wejściowe: dwa zestawy przedziałów i (wszystkie punkty końcowe są liczbami całkowitymi). Pytanie: czy istnieje biotonia monotoniczna ?T f : S → TS.S.ST.T.Tfa: S→ T.fa:S.→T.f:S \to T Bijection jest monotoniczne WRT kolejnością włączenie do i . T ∀ X ⊆ Y ∈ S , f ( X )...
Próbuję użyć drzewa sufiksów do porównania sekwencji ciągów. Znalazłem implementacje / teorię najdłuższego wspólnego problemu podciągów przy użyciu drzewek sufiksów. Jednak to, czego szukam, to omówienie powiązanego problemu - „wszystkich typowych podciągów”. W szczególności mam problem, w którym...