Informatyka

4

Dlaczego używamy trwałych struktur danych w programowaniu funkcjonalnym?

Programowanie funkcjonalne wykorzystuje trwałe struktury danych i niezmienne obiekty. Moje pytanie brzmi: dlaczego tak ważne jest posiadanie takich struktur danych? Chcę na niskim poziomie zrozumieć, co by się stało, gdyby struktura danych nie była trwała? Czy program często się zawieszał?

22 data-structures functional-programming programming-paradigms persistent-data-structure

2

Co rozumie teoria kategorii, nie wie jeszcze, jak radzić sobie z funkcjami wyższego rzędu?

Czytając Uday Reddy za odpowiedź na Jaka jest relacja między funktorów w SML i teorii kategorii? Stwierdza Uday Teoria kategorii nie wie jeszcze, jak radzić sobie z funkcjami wyższego rzędu. Pewnego dnia to zrobi. Ponieważ myślałem, że teoria kategorii może służyć jako podstawa matematyki, powinna istnieć możliwość uzyskania wszystkich funkcji …

22 functional-programming category-theory

3

Przybliżenie złożoności Kołmogorowa

Studiowałem coś na temat złożoności Kołmogorowa , przeczytałem kilka artykułów i książek Vitanyi i Li i wykorzystałem koncepcję znormalizowanej odległości kompresji, aby zweryfikować stilometrię autorów (określić, w jaki sposób każdy autor pisze niektóre dokumenty tekstowe i grupowe według ich podobieństwa). W takim przypadku zastosowano kompresory danych w celu przybliżenia złożoności …

22 computability approximation data-compression kolmogorov-complexity

1

Ile najkrótszych odległości zmienia się podczas dodawania krawędzi do wykresu?

Niech będzie jakimś kompletnym, ważonym, niekierowanym wykresem. Budujemy drugi wykres , dodając krawędzie jeden po drugim od do . Łącznie dodajemy krawędzie do .G ′ = ( V , E ′ ) E E ′ Θ ( | V | ) G ′G = ( V, E)G=(V,E)G=(V,E)sol′= ( V, E′)G′=(V,E′)G'=(V, …

22 algorithms graphs graph-theory shortest-path

1

Zdecyduj, czy języki bezkontekstowe mogą być akceptowane przez deterministyczny automat przesuwania

Biorąc pod uwagę bezkontekstową gramatykę G, istnieje niedeterministyczny automat pushdown N, który akceptuje dokładnie język, który akceptuje G. (i odwrotnie) Nie może również istnieć deterministyczny automat ze stosem D, który akceptuje dokładnie język G akceptuje też. To zależy od gramatyki. Za pomocą jakiego algorytmu produkcji G możemy ustalić, czy D …

22 automata context-free pushdown-automata

2

Czy istnieje „naturalny” nierozstrzygalny język?

Czy istnieje jakiś „naturalny” język, który jest nierozstrzygalny? przez „naturalny” rozumiem język zdefiniowany bezpośrednio przez właściwości ciągów, a nie przez maszyny i ich odpowiedniki. Innymi słowy, jeśli język wygląda jak gdzie to TM, DFA (lub regularny exp), PDA (lub gramatyka) itp., To nie jest naturalne. Jednak jest naturalne.L={⟨M⟩∣…}L={⟨M⟩∣…} L = …

22 formal-languages automata computability undecidability

1

Drzewa AVL nie są zrównoważone pod względem masy?

W poprzednim pytaniu była definicja drzew zrównoważonych pod względem masy i pytanie dotyczące drzew czerwono-czarnych. To pytanie dotyczy tego samego pytania, ale dotyczy drzew AVL . Pytanie brzmi, biorąc pod uwagę definicję drzew zrównoważonych jak w drugim pytaniu,μμ\mu Czy jest jakieś takie, że wszystkie wystarczająco duże drzewa AVL są zrównoważone …

22 data-structures binary-trees search-trees balanced-search-trees avl-trees

2

Jaka kombinacja struktur danych skutecznie przechowuje dyskretne sieci bayesowskie?

Rozumiem teorię leżącą u podstaw sieci bayesowskich i zastanawiam się, co trzeba zbudować w praktyce. Powiedzmy na przykład, że mam sieć bayesowską (ukierunkowaną) 100 dyskretnych zmiennych losowych; każda zmienna może przyjąć jedną z maksymalnie 10 wartości. Czy przechowuję wszystkie węzły w DAG i dla każdego węzła przechowuję tabelę prawdopodobieństwa warunkowego …

22 data-structures machine-learning

2

Czym różni się kompilator JIT od zwykłego kompilatora?

Wiele komplikuje się w kompilatorach JIT dla języków takich jak Java, Ruby i Python. Czym różnią się kompilatory JIT od kompilatorów C / C ++ i dlaczego kompilatory napisane dla Java, Ruby lub Python nazywane są kompilatorami JIT, podczas gdy kompilatory C / C ++ to tylko kompilatory?

22 compilers

4

Czy maszyna, która nigdy się nie zatrzymuje, zawsze pętli?

Maszyna Turinga, która powróci do wcześniej napotkanego stanu z głowicą do odczytu / zapisu w tej samej komórce dokładnie tej samej taśmy, zostanie przechwycona w pętli. Taka maszyna się nie zatrzymuje. Czy ktoś może podać przykład ciągłej maszyny, która się nie zapętla?

22 computability turing-machines halting-problem

1

Naturalni kandydaci do hierarchii wewnątrz NPI

Załóżmy, że . to klasa problemów w które nie są ani w ani w -hard. Listę problemów, które mogą być tutaj .P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}NPINPI\mathsf{NPI}NPNP\mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}NPINPI\mathsf{NPI} Twierdzenie Ladnera mówi nam, że jeśli wówczas istnieje nieskończona hierarchia problemów , tzn. Istnieją problemy , które są trudniejsze niż inne problemy.N P I N P …

22 complexity-theory np-hard

4

Algorytmy sortowania, które akceptują losowy komparator

Ogólne algorytmy sortowania zazwyczaj wymagają zestawu danych do sortowania i funkcji komparatora, która może porównywać dwa pojedyncze elementy. Jeśli komparator jest relacją rzędu¹, to wynikiem działania algorytmu jest posortowana lista / tablica. Zastanawiam się jednak, które algorytmy sortowania faktycznie działałyby z komparatorem, który nie jest relacją rzędu (w szczególności, który …

22 algorithms randomized-algorithms sorting

4

Czy istnieją inne sposoby opisywania języków formalnych inne niż gramatyka?

To pytanie zostało przeniesione z Teoretycznej informatyki stosu wymiany, ponieważ można na nie odpowiedzieć w sprawie informatyki stosu wymiany. Migrował 7 lat temu . Szukam teorii matematycznych, które zajmują się opisywaniem języków formalnych (zestawu ciągów) w ogólności, a nie tylko hierarchii gramatycznej.

22 formal-languages formal-grammars

2

Czy algorytm Dijkstry to tylko BFS z kolejką priorytetową?

Według tej strony algorytm Dijkstry to po prostu BFS z kolejką priorytetową. Czy to naprawdę takie proste? Myślę, że nie.

22 algorithms graphs shortest-path

2

W jaki sposób problem sprzedawcy podróży jest weryfikowalny w czasie wielomianowym?

Rozumiem więc, że problem decyzyjny jest zdefiniowany jako Czy istnieje ścieżka P taka, że koszt jest niższy niż C? i możesz łatwo sprawdzić, czy to prawda, weryfikując otrzymaną ścieżkę. Co jednak, jeśli nie ma ścieżki, która spełniałaby te kryteria? Jak zweryfikowałbyś odpowiedź „nie” bez rozwiązania problemu z najlepszą ścieżką TSP, …

21 complexity-theory time-complexity np decision-problem traveling-salesman