Natknąłem się na dziwne doświadczenie w programowaniu C. Rozważ ten kod: int main(){ int array1[6] = {0, 1, 2, 3, 4, 5}; int array2[6] = {6, 7, 8, 9, 10, 11}; printf("%d\n", array1[-1]); return 0; } Podczas kompilacji i uruchamiania nie otrzymuję żadnych błędów ani ostrzeżeń. Jak powiedział...
Chcę wiedzieć, czy można rozwiązać następujący problem: Instancja: NFA A z n stanami Pytanie: Czy istnieje jakaś liczba pierwsza p, taka, że A akceptuje pewien ciąg długości p. Wierzę, że ten problem jest nierozstrzygalny, ale nie mogę tego udowodnić. Decydent może łatwo mieć algorytm, aby...
Przeprowadziłem pewne testy różnych temperatur początkowych w moim algorytmie symulującym wyżarzanie i zauważyłem, że temperatura początkowa ma wpływ na wydajność algorytmu. Czy jest jakiś sposób obliczenia dobrej temperatury
Biorąc pod uwagę nieważony DAG (skierowane acykliczny wykres) oraz dwa wierzchołki i , jest możliwe znalezienie najkrótszej ścieżki, a najdłuższy z na w czasie wielomianowym? Długości ścieżek są mierzone liczbą krawędzi.s t s tD=(V,A)D=(V,A)D = (V,A)ssstttsssttt Interesuje mnie znalezienie zakresu...
Załóżmy, że podano różnych liczb całkowitych , takich, że dla pewnej stałej i dla wszystkich .nnna1,a2,…,ana1,a2,…,ana_1, a_2, \dots, a_n0≤ai≤kn0≤ai≤kn0 \le a_i \le knk>0k>0k \gt 0iii Interesuje nas znalezienie zliczeń wszystkich możliwych sum . ( jest dozwolone).Sij=ai+ajSij=ai+ajS_{ij} =...
Muszę skonstruować wykres ekspandera regularnego d dla niektórych małych stałych d (jak 3 lub 4) n wierzchołków. Jaka jest najłatwiejsza metoda na zrobienie tego w praktyce? Konstruujesz losowy wykres d-regularny, który okazał się być ekspanderem? Czytałem także o konstrukcjach Margulis i grafach...
Zastanawiałem się, kiedy języki zawierające taką samą liczbę wystąpień dwóch podciągów będą normalne. Wiem, że język zawierający taką samą liczbę 1 i 0 nie jest regularny, ale jest językiem takim jak , gdzie = liczba wystąpień podłańcucha „001” jest równa liczbie wystąpień podłańcucha „ 100 "...
Istnieje chciwy algorytm znajdowania minimalnego pokrycia wierzchołka drzewa, które korzysta z przejścia DFS. Dla każdego liścia drzewa wybierz jego element nadrzędny (tzn. Jego element nadrzędny znajduje się w minimalnej osłonie wierzchołków). Dla każdego węzła wewnętrznego: jeśli nie zostanie...
Problem Biorąc pod uwagę maszynę Turinga która zna czas działania O ( g ( n ) ) w odniesieniu do długości wejściowej n , czy czas działania M ∈ O ( f ( n ) ) ?MMMO(g(n))O(g(n)){O}(g(n))nnnM∈O(f(n))M∈O(f(n))M \in {O}(f(n)) Czy powyższy problem jest rozstrzygalny dla niektórych niebrywalnych...
Wiem, że możemy zminimalizować DFA poprzez znajdowanie i łączenie równoważnych stanów, ale dlaczego nie możemy zrobić tego samego z NFA? Nie szukam dowodu ani nic takiego - chyba że dowód jest łatwiejszy do zrozumienia. Chcę tylko intuicyjnie zrozumieć, dlaczego minimalizacja NFA jest tak trudna,...
Wiadomo, że język słów o równej liczbie 0 i 1 nie jest regularny, podczas gdy język słów o równej liczbie 001 i 100 jest regularny ( patrz tutaj ). Biorąc pod uwagę dwa słowa , czy jest rozstrzygalne, czy język słów zawierający taką samą liczbę i jest regularny?w 1 w...
Czy ktoś może skierować mnie do recenzowanych artykułów badających zalety lub wady pisania kodu w funkcjonalnym stylu? Czy są artykuły omawiające zastosowania Lambda Calculus w takich dziedzinach, jak uczenie maszynowe, projektowanie języków
Zdaję sobie sprawę z tego, że niedeterministyczne automaty wypychające mogą być ulepszeniem w stosunku do automatów deterministycznych, ponieważ mogą „wybierać” spośród kilku stanów i istnieje kilka języków bezkontekstowych, których nie można zaakceptować przez deterministyczne przepychanie. Nadal...
Patrzyłem na tę stronę i mówi, że ludzie znaleźli rozwiązania dla wycieczek TSP, które są tylko o 0,031% wyższe niż optymalna wycieczka. Bez znalezienia optymalnej trasy, skąd wiedzą, jaka to powinna być
Tak więc, jak wiadomo, problem decyzyjny ILP 0-1 jest NP-zupełny. Pokazanie tego w NP jest łatwe, a pierwotna redukcja pochodziła z SAT; od tego czasu wykazano, że wiele innych problemów z NP-Complete ma formulacje ILP (które działają jako redukcje tych problemów do ILP), ponieważ ILP jest bardzo...
Rodzina funkcji skrótu h : U → { 0 , … , M - 1 } jest uniwersalna, jeśli ∀ x , y ∈ U , x ≠ y ⇒ Pr h ∈ H [ h ( x ) = h ( y ) ] ≤ 1H.H.Hh : U→ { 0 , … , M- 1 }h:U→{0,…,M.-1}h: U \rightarrow \{0,\ldots,M-1\} Więcej informacji o uniwersalnym haszowaniu można znaleźć w tymartykule naWikipedii.∀ x ,...
Jakiego algorytmu użyłbyś do znalezienia najkrótszej ścieżki wykresu, która jest osadzona w płaszczyźnie euklidesowej, tak aby ścieżka nie zawierała żadnych skrzyżowań własnych (w osadzaniu)? Na przykład na poniższym wykresie chcesz przejść z . Zwykle algorytm taki jak algorytm Dijkstry tworzyłby...
Niech GGG jest wykresem, niech sss i ttt są dwa wierzchołki GGG . Możemy skutecznie próbki najkrótszą sss - ttt ścieżkę równomiernie i niezależnie losowo ze zbioru wszystkich najkrótszych ścieżek między sss i ttt ? Dla uproszczenia możemy założyć, że GGG jest prosty, nieukierunkowany i...
Mam dwóch dużych zestawów liczb całkowitych i B . Każdy zestaw ma około miliona wpisów, a każdy wpis jest dodatnią liczbą całkowitą o długości co najwyżej 10 cyfr. AAABBB Jaki jest najlepszy algorytm do obliczania i B ∖ A ? Innymi słowy, jak mogę skutecznie obliczyć listę pozycji A , które nie są...
To pojawiło się, gdy próbowałem odpowiedzieć na to pytanie dotyczące minimalizacji długości przewodów . Miałem to nazwać problemem „poligamicznego małżeństwa”, ale internet, tak kocięta. Tak! Załóżmy, że mamy kociąt, które muszą być przyjęte przez ludzi, . Dla każdego kociaka, i każdej osoby...