Czytałem Wstęp do algorytmów Cormena i in. i czytam twierdzenie Twierdzenia Mistrza zaczynające się na stronie 73 . W przypadku 3 istnieje również warunek regularności, który należy spełnić, aby zastosować twierdzenie: ... 3. Jeśli fa( n ) = Ω ( nlogba + ε)fa(n)=Ω(nlogbza+ε)\qquad...
Dla mnie ten problem wygląda bardzo interesująco. Już miał znaleźć prosty cykl (tj. Cykl, w którym nie ma powtarzalnych węzłów) na ukierunkowanym wykresie. Moje rozwiązanie wygląda następująco, tzn. Ten wykres jest problemem przypadku: Wiem, że na wykresie jest cykl, w którym można znaleźć...
Aktualne algorytmy szachowe idą około 1 lub może 2 poziomy w dół drzewa możliwych ścieżek w zależności od ruchów gracza i ruchów przeciwnika. Powiedzmy, że mamy moc obliczeniową do opracowania algorytmu, który przewiduje wszystkie możliwe ruchy przeciwnika w grze w szachy. Algorytm, który ma...
Najwyraźniej, jeśli , wszystkie języki w z wyjątkiem i byłyby -kompletne.P = N PP=NP{\sf P}={\sf NP}P.P{\sf P}∅∅\emptysetΣ∗Σ∗\Sigma^*N P.NP{\sf NP} Dlaczego w szczególności te dwa języki? Czy nie możemy zredukować do nich żadnego innego języka w , wysyłając je podczas przyjmowania lub...
Maszyny liczące z dwoma lub więcej licznikami są zwykle pokazywane jako równoważne maszynom Turinga w kursach teorii teorii obliczeń. Jednak nie widziałem formalnej analizy tego, które języki mogą być rozpoznawane przez maszynę z jednym kontem. Czy te języki są równoważne z językami...
Niedawny post na łamigłówce dotyczący znalezienia trzech równomiernie rozłożonych prowadzi mnie do pytania o przepełnienie stosu z najlepszą odpowiedzią, która twierdzi, że zrobię to w czasie O (n lg n). Interesujące jest to, że rozwiązanie polega na podniesieniu kwadratu do wielomianu, odnosząc...
Po tym, jak nauczyłem się, jak budować tablicę sufiksów w złożoności , jestem zainteresowany odkrywaniem zastosowania tablic sufiksów. Jednym z nich jest znalezienie najdłuższego wspólnego podłańcucha między dwoma łańcuchami w czasie . W Internecie znalazłem następujący...
Hidoku to siatka n×nn×nn \times n z niektórymi wstępnie wypełnionymi liczbami całkowitymi od 1 do n2n2n^2 . Celem jest znalezienie ścieżki kolejnych liczb całkowitych (od 1 do n2n2n^2 ) w siatce. Bardziej konkretnie, każda komórka siatki musi zawierać inną liczbę całkowitą od 1 do n2n2n^2 a każda...
Tak więc w zasadzie L spełnia warunki pompowania lematu dla CFL, ale nie jest CFL (jest to możliwe zgodnie z definicją
Próbuję znaleźć skuteczną metodę wykrywania, czy dany wykres G ma dwa różne minimalne drzewa rozpinające. Próbuję również znaleźć metodę, aby sprawdzić, czy ma 3 różne minimalne drzewa rozpinające. Naiwnym rozwiązaniem, o którym myślałem, jest jednorazowe uruchomienie algorytmu Kruskala i...
W przełomowym dokumencie dotyczącym systemów rozproszonych The Part Time Parliament (protokół Paxos) Leslie Lamport wymienia fikcyjnych prawodawców, którzy są zaangażowani w protokół Parlamentu Paxon. Zgodnie z tym pismem zauważa, że: Nadałem greckim prawodawcom nazwiska informatyków...
Wikipedia mówi : Kompletne sieci pojawiają się w wielu zastosowaniach w matematyce i informatyce Czy odnosi się to tylko do faktu, że standardowa algebra boolowska wykorzystywana w obliczeniach jest kompletną siecią? Czy coś zyskujemy dzięki pracy na abstrakcyjnym poziomie sieci, a nie logice...
Najprawdopodobniej pytanie to zostało zadane wcześniej. Pochodzi z problemu CLRS (2nd Ed) 6.5-8 - Podaj algorytm czasu O(nlgk)O(nlgk)O(n \lg k) , aby połączyć kkk sortowanych list w jedną posortowaną listę, gdzie nnn jest całkowitą liczbą elementów na wszystkich listach wejściowych. (Wskazówka:...
Jakie są przykłady trudnych problemów decyzyjnych, które można rozwiązać w czasie wielomianowym? Szukam problemów, dla których optymalny algorytm jest „wolny” lub problemów, dla których najszybszy znany algorytm jest „wolny”. Oto dwa przykłady: Rozpoznawanie idealnych wykresów. W swojej pracy...
Ostatnio zadano interesujące pytanie, a następnie usunięto. W przypadku zwykłego języka jego złożoność DFA jest wielkością minimalnej akceptacji DFA, a złożoność NFA jest wielkością minimalnej akceptacji NFA. Dobrze wiadomo, że istnieje wykładnicza separacja między tymi dwoma złożonościami,...
Chciałbym zacząć od stwierdzenia, że to NIE jest zadanie domowe. Czytam Wstęp do algorytmów - słynny tekst CLRS, aby stać się lepszym programistą. Próbuję samodzielnie rozwiązać problemy i ćwiczenia podane w książce. Próbuję rozwiązać Ćwiczenie 10.1-2 z rozdziału 10 Elementarne struktury danych...
Czy jest jakaś różnica między nimi? Zgodnie z książką Ullmana , kompilatory konwertują jeden język na inny (zwykle na niskim poziomie), podobnie jak asembler. Czym się różnią?
library(ggplot2) compress <- function(str) { length(memCompress(paste(rep("a", str), collapse=""), type="bzip2")) / nchar(paste(rep("a", str), collapse="")) } cr <- data.frame(i = 1:10000, r = sapply(1:10000, compress)) ggplot(cr[cr$i>=5000 & cr$i<=10000,], aes(x=i, y=r)) +...
Robiłem ćwiczenia programowania dynamicznego i znalazłem algorytm Floyda-Warshalla. Najwyraźniej znajduje wszystkie pary najkrótszych ścieżek dla wykresu, który może mieć ujemne krawędzie wagi, ale nie ma ujemnych cykli. Zastanawiam się więc, jakie jest rzeczywiste znaczenie ujemnych krawędzi...
Mamy DAG. Mamy funkcję na węzłach (luźno mówiąc, numerujemy węzły). Chcielibyśmy utworzyć nowy ukierunkowany wykres z tymi zasadami:fa: V→ N.F:V→NF\colon V\to \mathbb N Tylko węzły o tym samym numerze można zawrzeć w tym samym nowym węźle. . (Jednak .)fa( x ) ≠ F.( y) ⇒ x′. Y′F(x)≠F(y)⇒x′≠y′F(x)...