Informatyka

Pytania i odpowiedzi dla studentów, naukowców i praktyków informatyki

2
Określanie możliwości min-stosu (lub innych egzotycznych) automatów stanowych
Zobacz koniec tego postu, aby uzyskać wyjaśnienie definicji automatów typu min-heap. Można sobie wyobrazić użycie różnych struktur danych do przechowywania informacji do wykorzystania przez automaty stanów. Na przykład automatyczne automaty przechowują informacje na stosie, a maszyny Turinga używają taśmy. Automaty stanowe korzystające z kolejek oraz te, które używają dwóch wielu …
3
Dlaczego ludzie mogą rozwiązać niektóre „nierozstrzygalne” problemy?
Dopasowywanie wzorca wysokiego rzędu jest nierozstrzygalnym problemem. Oznacza to, że nie ma algorytmu, który, biorąc pod uwagę równanie a => b, gdzie ai bsą otwartymi terminami na prostym typie rachunku lambda, znalazłby podstawienie Stakie, że aS => bSgdzie =>skrót oznacza „ma tę samą postać normalną Bn”. Jednak ludzie mogą skutecznie …
1
Co sprawia, że ​​wnioskowanie o typach dla typów zależnych jest nierozstrzygalne?
Widziałem już wspomniane, że systemy typów zależnych nie są wnioskami, ale można je sprawdzić. Zastanawiałem się, czy istnieje proste wyjaśnienie, dlaczego tak jest, i czy istnieje granica „zależności”, w której typy mogą być indeksowane według wartości, poniżej której możliwe jest wnioskowanie typu, a powyżej której nie jest?
9
Dlaczego niektóre języki programowania Turing są kompletne, ale brakuje im umiejętności innych języków?
Napotkałem dziwny problem podczas pisania interpretera, który (powinien) zaczepia się o zewnętrzne programy / funkcje: Funkcje w „C” i „C ++” nie mogą przechwytywać funkcji variadic , np. Nie mogę utworzyć funkcji, która wywoła „printf” z dokładnie tymi samymi argumentami, które otrzymał, i zamiast tego musi wywołać alternatywną wersję, która …
5
Iteracja może zastąpić rekurencję?
Widziałem przepełnienie całego stosu, np. Tutaj , tutaj , tutaj , tutaj , tutaj i kilku innych, których nie chcę wspominać, że „każdy program, który korzysta z rekurencji, można przekonwertować na program wykorzystujący tylko iterację”. Był nawet wysoko oceniany wątek z bardzo pozytywną odpowiedzią, która powiedziała, że ​​tak, to możliwe. …
11
Dlaczego ktokolwiek miałby chcieć CISC?
W naszym wykładzie dotyczącym systemów komputerowych zapoznaliśmy się z procesorem MIPS. Został (ponownie) opracowany w trakcie tego okresu i faktycznie był dość łatwy do zrozumienia. Wykorzystuje projekt RISC , co oznacza, że ​​jego podstawowe polecenia są regularnie kodowane, a jest ich niewiele, aby uprościć przewody. Wspomniano, że CISC kieruje się …
1
Wyobraź sobie czerwono-czarne drzewo. Czy zawsze istnieje sekwencja wstawiania i usuwania, która ją tworzy?
Załóżmy następującą definicję drzewa czerwono-czarnego: Jest to drzewo wyszukiwania binarnego. Każdy węzeł ma kolor czerwony lub czarny. Korzeń jest czarny. Dwa węzły połączone krawędzią nie mogą być jednocześnie czerwone. Oto dobra definicja liścia NIL, jak na wiki. Liść NIL ma kolor czarny. Ścieżka od korzenia do dowolnego liścia NIL zawiera …
1
Czy automat zwijający z dwoma stosami jest równoważny maszynie Turinga?
W tej odpowiedzi wspomniano o tym Skończony automat może rozpoznać zwykły język. Język bezkontekstowy wymaga stosu, a język kontekstowy wymaga dwóch stosów (co jest równoważne z twierdzeniem, że wymaga pełnej maszyny Turinga) . Chciałem wiedzieć o prawdzie odważnej części powyżej. Czy to prawda, czy nie? Jaki jest dobry sposób na …
3
Kontrastujące algorytmy Petersona i Dekkera
Próbuję zrozumieć algorytmy Petersona i Dekkera, które są bardzo podobne i wykazują wiele symetrii. Próbowałem sformułować algorytmy w nieformalnym języku w następujący sposób: Peterson's: "I want to enter." flag[0]=true; "You can enter next." turn=1; "If you want to enter and while(flag[1]==true&&turn==1){ it's your turn I'll wait." } Else: Enter CS! …
2
Wydajne struktury danych do budowy szybkiego sprawdzania pisowni
Próbuję napisać moduł sprawdzania pisowni, który powinien działać z dość dużym słownikiem. Naprawdę chcę efektywnego sposobu indeksowania danych słownikowych za pomocą odległości Damerau-Levenshteina w celu ustalenia, które słowa są najbliższe błędnie napisanemu słowu. Szukam struktury danych, która dałaby mi najlepszy kompromis między złożonością przestrzeni a złożonością środowiska wykonawczego. Na podstawie …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.