Informatyka

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

2
Jak wdrożyć algorytm AO *?
Zauważyłem, że podczas implementacji algorytmów wyszukiwania stosowane są różne struktury danych. Na przykład używamy kolejek do implementacji pierwszego wyszukiwania szerokości, stosów do implementacji wyszukiwania z głębokości pierwszej i stosów min do implementacji algorytmu A * . W takich przypadkach nie musimy jawnie budować drzewa wyszukiwania. Ale nie mogę znaleźć prostej …
2
W jaki sposób wariancja czasu wykonania zadania wpływa na makespan?
Powiedzmy, że mamy duży zbiór zadań i zbiór identycznych (pod względem wydajności) procesorów które działają całkowicie w równolegle. W przypadku interesujących scenariuszy możemy założyć . Każde zajmuje pewną ilość czasu / cykli, gdy jest przypisane do procesora , a po przypisaniu nie można go ponownie przypisać, dopóki nie zostanie zakończone …
2
Dlaczego niektóre silniki wnioskowania potrzebują ludzkiej pomocy, a inne nie?
Uczę się samodzielnie Automated Theorem Proving / Solver SMT / Proof Assistants i zamieszczam serię pytań na temat tego procesu, zaczynając tutaj . Dlaczego automatyczne dowodzenia twierdzeń, tj. ACL2 i solwery SMT, nie potrzebują ludzkiej pomocy, podczas gdy asystenci dowodzenia, tj. Isabelle i Coq , tak? Znajdź następne pytanie z …
3
Różnica między „informacją” a „użyteczną informacją” w algorytmicznej teorii informacji
Według Wikipedii : Nieformalnie, z punktu widzenia algorytmicznej teorii informacji, zawartość informacyjna ciągu jest równoważna długości możliwie najkrótszej możliwej niezależnej reprezentacji tego ciągu. Jaka jest analogiczna nieformalna rygorystyczna definicja „użytecznych informacji”? Dlaczego „użyteczne informacje” nie są uważane za bardziej naturalne lub bardziej podstawowe pojęcie; naiwnie wydaje się, że czysto przypadkowy …
2
Udowodnienie, że plik binarny ma
Próbuję udowodnić, że sterty binarne z węzłami mają dokładnie liści, biorąc pod uwagę, że stertę buduje się w następujący sposób:nnn⌈n2⌉⌈n2⌉\left\lceil \frac{n}{2} \right\rceil Każdy nowy węzeł jest wstawiany przez przeskalowanie w górę . Oznacza to, że każdy nowy węzeł musi zostać utworzony przy następnym dostępnym podrzędnym. Rozumiem przez to, że dzieci …
2
Języki akceptowane przez zmodyfikowane wersje automatów skończonych
Deterministyczny automat skończony (DFA) to model maszyny stanów zdolny do przyjmowania wszystkich i tylko zwykłych języków. DFA można (i zwykle są) definiować w taki sposób, że każdy stan musi zapewnić pewne przejście dla wszystkich elementów alfabetu wejściowego; innymi słowy, funkcja przejścia δ:Q×Σ→Qδ:Q×Σ→Q\delta : Q \times \Sigma \rightarrow Q powinna być …
1
Potwierdzenie zamknięcia w zamian języków akceptowanych przez automaty min-heap
To jest kolejne pytanie tego . W poprzednim pytaniu dotyczącym egzotycznych automatów stanowych Alex ten Brink i Raphael odnieśli się do możliwości obliczeniowych szczególnego rodzaju automatu stanowego: automatów typu min-heap. Udało im się wykazać, że zestaw języków akceptowanych przez takie maszyny ( ) nie jest ani podzbiorem, ani nadzbiorem zestawu …
1
Skuteczne kodowanie łamigłówek sudoku
Określenie dowolnej dowolnej siatki 9x9 wymaga podania pozycji i wartości każdego kwadratu. Naiwne kodowanie tego może dać 81 (x, y, wartość) trypletów, wymagając 4 bitów dla każdego x, y i wartości (1-9 = 9 wartości = 4 bity) w sumie 81x4x3 = 972 bitów. Numerując każdy kwadrat, można zmniejszyć informację …
1
Metody oceny systemu pisemnych reguł
Próbowałem wymyślić system, który oceniałby regulaminy organizacji w celu ustalenia ich podstawowej logiki. Myślę, że system predykatów pierwszego rzędu działałby w celu reprezentowania reguł, które mogłyby być przetłumaczone z tekstu za pomocą tagowania części mowy i innych technik NLP. Czy istnieje systematyczny sposób interpretacji reguł logicznych pierwszego rzędu jako całości …
2
Dlaczego w wielu kompilatorach wykorzystywanych w branży preferowane jest przypisanie statycznego pojedynczego nad stylem przekazywania ciągłego?
Według strony Wikipedii na temat statycznego pojedynczego przypisania (SSA) , SSA jest używany przez duże i dobrze znane projekty, takie jak LLVM, GCC, MSVC, Mono, Dalvik, SpiderMonkey i V8, podczas gdy strona o projektach używa stylu kontynuacji przejścia (CPS) jest trochę brakuje w porównaniu. Mam pojęcie, że CPS jest preferowany …
3
Jak zrobić język homoiconic
Zgodnie z tym artykułem następujący wiersz kodu Lisp wypisuje „Hello world” na standardowe wyjście. (format t "hello, world") Lisp, który jest językiem homoiconic , może traktować kod jako dane w następujący sposób: Teraz wyobraź sobie, że napisaliśmy następujące makro: (defmacro backwards (expr) (reverse expr)) wstecz to nazwa makra, która przyjmuje …
2
Oblicz maksymalny przepływ z minimalnego cięcia
Wiemy, że obliczenie maksymalnego przepływu lub. minimalne ograniczenie sieci o przepustowości jest równoważne; por. twierdzenie o maksymalnym przepływie min. cięcie . Mamy (mniej lub bardziej wydajne) algorytmy obliczania maksymalnych przepływów, a obliczanie minimalnego cięcia przy maksymalnym przepływie nie jest ani trudne, ani drogie. Ale co na odwrót? Biorąc pod uwagę …
1
Obliczenia kwantowe - związek między modelem Hamiltonian a modelem Unitary
Podczas opracowywania algorytmów obliczeń kwantowych zauważyłem, że istnieją dwa podstawowe modele, w których odbywa się to. Niektóre algorytmy - takie jak problem drzewa Hamiltonian NAND (Farhi, Goldstone, Guttman) - działają poprzez zaprojektowanie stanu hamiltonowskiego i pewnego stanu początkowego, a następnie umożliwienie ewolucji systemu zgodnie z równaniem Schrödingera przez pewien czas …
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.