Informatyka

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

4
Jak symulować odwołania wsteczne, wyprzedzenia i spojrzenia w automatach skończonych?
To pytanie zostało przeniesione z Przepełnienia stosu, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 7 lat temu . Stworzyłem prosty leksymetr i analizator wyrażeń regularnych, aby pobrać wyrażenie regularne i wygenerować jego drzewo analizy. Utworzenie niedeterministycznego automatu skończonego z tego drzewa analizy jest stosunkowo proste w …
1
Najdłuższa powtarzająca się (rozproszona) sekwencja w ciągu
Nieformalne oświadczenie o problemie: Biorąc pod uwagę ciąg znaków, np. ACCABBABACCABBABACCABBAB , chcemy pokolorować niektóre litery na czerwono, a niektóre na niebiesko (a niektóre wcale), tak że czytanie tylko czerwonych liter od lewej do prawej daje taki sam wynik jak czytanie tylko niebieskie litery. W przykładzie możemy je pokolorować w …
3
Narzędzia do programowania wizualnego, dlaczego nie współpracują bezpośrednio z AST?
Znalazłem kilka narzędzi do programowania wizualnego typu open source, takich jak Blockly i przyjaciele oraz inne projekty hostowane w Github, ale nie mogłem znaleźć żadnego, który działałby bezpośrednio z abstrakcyjnym drzewem składni. Dlaczego? Pytam, ponieważ kiedy odkryłem, że każdy kompilator ma fazę w procesie kompilacji, w której analizuje kod źródłowy …
2
Struktura danych z wyszukiwaniem, wstawianie i usuwanie w zamortyzowanym czasie
Czy istnieje struktura danych umożliwiająca utrzymanie uporządkowanej listy, która obsługuje następujące operacje w zamortyzowanym czasie ?O(1)O(1)O(1) GetElement (k) : zwraca ty element listy.kkk InsertAfter (x, y) : Wstaw nowy element y do listy natychmiast po x. Usuń (x) : Usuń x z listy. W przypadku dwóch ostatnich operacji można założyć, …
4
Czy problem zatrzymania jest rozstrzygalny dla czystych programów na idealnym komputerze?
Dość proste jest zrozumienie, dlaczego problem zatrzymania jest nierozstrzygalny w przypadku nieczystych programów (tj. Tych, które mają operacje we / wy i / lub stany zależne od stanu globalnego maszyny); ale intuicyjnie wydaje się, że zatrzymanie czystego programu na idealnym komputerze byłoby rozstrzygalne np. poprzez analizę statyczną. Czy tak jest …
4
Dowód nierozstrzygalności problemu zatrzymania
Mam problem ze zrozumieniem dowodu nierozstrzygalności problemu zatrzymania. Jeśli zwraca, czy program a zatrzymuje się na wejściu b , dlaczego musimy przekazać kod P zarówno dla a, jak i b ?H.( a , b )H(a,b)H(a,b)zaaabbbP.PPzaaabbb Dlaczego nie możemy karmić z P i jakimś arbitralnym wejściowego, powiedzmy, X ?H.( )H()H()P.PPxxx
6
Dlaczego bramy odwracalne nie są używane?
Czytałem książkę „Osobliwość jest bliska” napisaną przez Kurzweila, który wspomniał o odwracalnych bramach, takich jak na przykład brama Fredkina . Zaletą korzystania z takich bram jest to, że moglibyśmy pozbyć się odpadów termicznych związanych z obliczeniami, w których bity po prostu znikają w cieple, a obliczenia nie będą wymagały żadnego …
5
Czy jest filtr przeciw Bloomowi?
Filtr Bloom pozwala efektywnie śledzić, czy różne wartości zostały już napotkał podczas przetwarzania. Gdy jest wiele elementów danych, filtr Bloom może spowodować znaczne oszczędności pamięci w tabeli skrótów. Główną cechą filtra Bloom, który dzieli z tabelą skrótów, jest to, że zawsze mówi „nie nowy”, jeśli element nie jest nowy, ale …
3
Nauczanie kompletności NP - redukcje Turinga i karp
Interesuje mnie pytanie, jak najlepiej uczyć kompletności NP na kierunkach informatycznych. W szczególności, czy powinniśmy tego uczyć stosując redukcje Karp czy redukcje Turinga? Uważam, że koncepcje kompletności i redukcji NP są czymś, czego powinien nauczyć się każdy kierunek informatyki. Jednak ucząc kompletności NP zauważyłem, że stosowanie redukcji Karp ma pewne …
2
Kodowanie ograniczenia 1 na n dla solverów SAT
Używam solwera SAT do zakodowania problemu, a jako część instancji SAT mam zmienne logiczne gdzie jest zamierzone, że dokładnie jedna z nich powinna być prawdziwa, a reszta powinna być fałszywa . (Czasami widziałem to opisywane jako kodowanie „na gorąco”).x1,x2,…,xnx1,x2,…,xnx_1,x_2,\dots,x_n Chcę zakodować ograniczenie „dokładnie jeden z musi być prawdziwe” w SAT. …
2
Jak wdrożyć tłumacza prologu w czysto funkcjonalnym języku?
Czy istnieje wyraźne odniesienie, z pseudo-kodem, dotyczące sposobu wdrażania interpretera Prolog w czysto funkcjonalnym języku? To, co do tej pory znalazłem, wydaje się dotyczyć wyłącznie języków imperatywnych, jest jedynie demonstracją samego Prologu zaimplementowanego lub nie oferuje żadnego konkretnego algorytmu do zastosowania w interpretacji. Byłbym bardzo wdzięczny za odpowiedź.
6
Jaki jest związek między językami programowania, wyrażeniami regularnymi i językami formalnymi
Rozejrzałem się w sieci, szukając odpowiedzi na to pytanie i wydaje się, że wszyscy domyślnie znają odpowiedź oprócz mnie. Przypuszczalnie dzieje się tak, ponieważ jedynymi osobami, które się opiekują, są osoby z wyższym wykształceniem na ten temat. Z drugiej strony zostałem wrzucony w głęboki koniec za zadanie do szkoły średniej. …
3
Znalezienie minimalnego cięcia niekierowanego wykresu
Oto pytanie z poprzedniego egzaminu, który próbuję rozwiązać: Dla niekierowanego wykresu z dodatnimi wagami w ( e ) ≥ 0 staram się znaleźć minimalne cięcie. Nie znam innych sposobów na zrobienie tego poza wykorzystaniem twierdzenia o maksymalnym przepływie min-cut. Ale wykres nie jest przekierowany, więc jak mam go pokierować? Myślałem …
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.