Mam więc pytanie, aby udowodnić stwierdzenie: O ( n ) ⊂ Θ ( n )O(n)⊂Θ(n)O(n)\subset\Theta(n) ... Nie muszę wiedzieć, jak to udowodnić, po prostu myślę, że to nie ma sensu i myślę, że powinno raczej być tak Θ ( n ) ⊂ O ( n )Θ(n)⊂O(n)\Theta(n)\subset O(n) . Rozumiem, że O ( n )O(n)O(n) jest...
W przypadku niektórych wykresów algorytmy wyszukiwania DFS i BFS przetwarzają węzły w dokładnie tej samej kolejności, pod warunkiem, że oba rozpoczynają się w tym samym węźle. Dwa przykłady to wykresy będące ścieżkami i wykresy w kształcie gwiazdy (drzewa o głębokości z dowolną liczbą dzieci). Czy...
Rozważ kwadrat, ABCD. Intuicyjnie wydawało mi się, że jego wielomian chromatyczny to λ ( λ - 1 ) ( λ - 1 ) ( λ - 2 )λ(λ-1)(λ-1)(λ-2))\lambda(\lambda - 1)(\lambda - 1)(\lambda - 2) tam, gdzie dostępne są kolory λλ\lambda .. Oznacza to, że istnieje λλ\lambda sposobów na wybranie koloru dla A,...
Z Wikipedii : Rodzaj problemu obliczeniowego: Najczęściej stosowanymi problemami są problemy decyzyjne . Klasy złożoności można jednak zdefiniować na podstawie problemów z funkcjami, problemów z liczeniem, problemów z optymalizacją, problemów z obietnicą itp. Widziałem także definicje...
Programowanie dynamiczne z dużą liczbą podproblemów. Więc próbuję rozwiązać ten problem z ulicy wywiadu: Grid Walking (Zdobądź 50 punktów) Znajdujesz się w siatce NNN wymiarowej na pozycji (x1,x2,…,xN)(x1,x2,…,xN)(x_1,x_2,\dots,x_N) . Wymiary siatki to (D1,D2,…,DN(D1,D2,…,DN(D_1,D_2,\dots,D_N...
Natknąłem się na następujący interesujący problem: niech będą wielomianami na polu liczb rzeczywistych i załóżmy, że wszystkie ich współczynniki są liczbami całkowitymi (tzn. Istnieje dokładna reprezentacja tych wielomianów). W razie potrzeby możemy założyć, że stopień obu wielomianów jest równy....
Czy „indukcyjne” i „rekurencyjne” oznaczają bardzo podobne? Na przykład, jeśli istnieje algorytm, który określa wektor n-dim przez określenie jego pierwszych elementów k + 1 na podstawie wyznaczonych pierwszych elementów k i jest inicjalizowany za pomocą pierwszego składnika, czy nazwałbyś go...
Powiedziano mi, że komputery kwantowe nie są obliczeniowo mocniejsze niż maszyny Turinga. Czy ktoś mógłby pomóc w udzieleniu referencji literaturowych wyjaśniających ten
Potrzebuję zwięzłej definicji „stanu obiektu” w programowaniu obiektowym (na papierze). Przez około pół dnia szukałem artykułu, który mogę zacytować na ten temat, ale nie mogłem go znaleźć. Wszystkie artykuły, które znalazłem, były w większości ogólnymi artykułami na temat programowania...
Zwrócono mi uwagę, że koszt wnioskowania o typ w funkcjonalnym języku, takim jak OCaml, może być bardzo wysoki. Twierdzenie jest takie, że istnieje ciąg wyrażeń taki, że dla każdego wyrażenia długość odpowiedniego typu jest wykładnicza względem długości wyrażenia. Wymyśliłem sekwencję poniżej....
Muszę wiedzieć, pod którą klasą CFL jest zamknięty, tj. Jaki zestaw jest uzupełnieniem CFL. Wiem, że CFL nie jest zamknięty pod dopełnieniem i wiem, że P jest zamknięty pod dopełnieniem. Ponieważ CFL PI może powiedzieć, że dopełnienie CFL jest zawarte w P (prawda?). Pozostaje pytanie, czy...
Z Wikipedii Wyszukiwanie informacji to czynność polegająca na uzyskiwaniu zasobów informacyjnych odpowiednich do potrzeb informacyjnych z kolekcji zasobów informacyjnych. Wyszukiwanie może opierać się na metadanych lub indeksowaniu pełnotekstowym. Z Wikipedii Ekstrakcja informacji (IE) to...
Załóżmy, że mamy 10 osób, każda z listą ulubionych książek. Dla danej osoby X chciałbym znaleźć specjalny podzbiór książek X, lubiany tylko przez X, tzn. Nie ma innej osoby, która polubiłaby wszystkie książki w specjalnym podzbiorze X. Uważam ten specjalny podzbiór za unikalny „odcisk palca” dla...
Rozważ skierowany wykres na którym można dynamicznie dodawać krawędzie i tworzyć określone zapytania.GGG Przykład: las rozłączny Rozważ następujący zestaw zapytań: arrow(u, v) equiv(u, v) find(u) pierwszy dodaje strzałkę do wykresu, drugi decyduje, czy u ↔ ∗ v , ostatni znajduje kanoniczny...
Jak definiuje się analizę asymptotyczną (duża o, mała o, duża theta, duża theta itp.) Dla funkcji z wieloma zmiennymi? Wiem, że artykuł w Wikipedii zawiera sekcję, ale wykorzystuje wiele notacji matematycznych, których nie znam. Znalazłem również następujący artykuł:...
Mam algorytm rekurencyjny o złożoności czasowej równoważnej do wybierania elementów k z powtórzeniem i zastanawiałem się, czy mogę uzyskać bardziej uproszczone wyrażenie big-O. W moim przypadku może być większe niż i rosną one niezależnie.kkknnn W szczególności oczekiwałbym wyraźnego wyrażenia...
Przesunięcia cyklicznego (zwany również obracanie lub koniugacji ) języka jest zdefiniowana jako . Według wikipedii (i tutaj ) języki bezkontekstowe są zamknięte w ramach tej operacji, z odniesieniami do artykułów z Osziby i Masłowa. Czy istnieje łatwy dowód tego faktu?L LL{ y x ∣ x y ∈ L...
Czy istnieje algorytm dla następującego problemu: Biorąc pod uwagę maszynę Turinga która decyduje o języku L , czy istnieje maszyna Turinga M 2 decydująca L, tak że t 2 ( n ) = o ( t 1 ( n ) ) ?M.1M1M_1L.LLM.2)M2M_2L.LLt2)( n ) = o ( t1( n ) )t2(n)=o(t1(n))t_2(n) = o(t_1(n)) Funkcje i t 2...
Chcesz poprawić ten post? Podaj szczegółowe odpowiedzi na to pytanie, w tym cytaty i wyjaśnienie, dlaczego Twoja odpowiedź jest poprawna. Odpowiedzi bez wystarczającej ilości szczegółów mogą być edytowane lub usuwane. Zadanie polegało na zbudowaniu biblioteki książek na...
Wiem, że maksymalny niezależny zestaw na sześciennych grafach bez trójkątów jest NP-zupełny. Czy nadal jest NP-kompletny, jeśli potrzebujemy, aby niezależny zestaw miał dokładnie taką samą wielkość ?| V.| / 2|V.|/2)|V|/2 Zasadniczo YES wystąpienie problemu z niezależnym zestawem na szesnastkowym...