Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

2
Wydajny algorytm do aktualizowania drzewa analizy
Powiedzmy, że mam duży blok kodu, który już sprawdziłem i przeanalizowałem. Załóżmy, że zmienia się tylko jedna postać; Chciałbym zaktualizować parsowanie, ale ponieważ modyfikacja jest bardzo niewielka w porównaniu do całości, chciałbym wiedzieć, czy nie można ponownie przeanalizować całości, ale czy istnieją algorytmy określające zakres do ponownej analizy i odpowiednio …
2
Uogólnienie węgierskiego algorytmu na ogólne niekierowane wykresy?
Algorytm węgierski jest kombinatorycznym algorytmem optymalizacyjnym, który rozwiązuje problem dwustronnego dopasowania maksymalnej masy w czasie wielomianowym i przewidywał późniejszy rozwój ważnej metody pierwotnej podwójnej . Algorytm został opracowany i opublikowany przez Harolda Kuhna w 1955 r., Który nadał mu nazwę „algorytm węgierski”, ponieważ algorytm był oparty na wcześniejszych pracach dwóch …
3
Złożoność sprawdzania, czy dwa CNF mają taką samą liczbę rozwiązań
Biorąc pod uwagę dwa CNF, jeśli mają taką samą liczbę zadań, aby były prawdziwe, odpowiedz „Tak”, w przeciwnym razie odpowiedz „Nie”. Łatwo zauważyć, że jest to w , ponieważ jeśli znamy dokładną liczbę rozwiązań dla tych dwóch CNF, po prostu je kampanujemy i odpowiadamy „Tak” lub „Nie”.P#PP#PP^{\#P} Jaka jest złożoność …
2
Uzasadnienie metody węgierskiej (Kuhn-Munkres)
Napisałem implementację algorytmu Kuhna-Munkresa dla problemu dwustronnego idealnego dopasowania minimalnej wagi w oparciu o notatki z wykładu, które znalazłem tu i tam w Internecie. Działa naprawdę dobrze, nawet na tysiącach wierzchołków. I zgadzam się, że teoria jest naprawdę piękna. A jednak wciąż zastanawiam się, dlaczego musiałem tak bardzo się starać. …
1
Generowanie wykresów za pomocą trywialnych automorfizmów
Sprawdzam jakiś model kryptograficzny. Aby pokazać jego nieadekwatność, opracowałem wymyślony protokół oparty na izomorfizmie grafowym. Zakładanie istnienia algorytmów BPP zdolnych do generowania „trudnych wystąpień problemu z izomorfizmem grafów” jest „powszechne” (a jednak kontrowersyjne!). (Wraz ze świadkiem izomorfizmu). W moim skonstruowanym protokole założę istnienie takich algorytmów BPP, które spełniają jeden dodatkowy …
1
Jak zdefiniować funkcję indukcyjnie na podstawie dwóch argumentów w Coq?
Jak przekonać Coq, że podana poniżej funkcja rekurencyjna kończy się? Funkcja przyjmuje dwa argumenty indukcyjne. Intuicyjnie rekursja kończy się, ponieważ którykolwiek argument jest rozkładany. W szczególności funkcja przyjmuje dwa drzewa jako dane wejściowe. Inductive Tree := | Tip: Tree | Bin: Tree -> Tree -> Tree. Na drzewach lubię stosować …
3
Asocjacyjne mieszanie skrótów
Rozważ mało pojedynczo połączoną listę w czysto funkcjonalnym otoczeniu. Jego pochwały śpiewano ze szczytów górskich i nadal będą śpiewane. Zajmę się tutaj jedną z wielu jego mocnych stron i pytaniem, w jaki sposób można ją rozszerzyć na szerszą klasę czysto funkcjonalnych sekwencji opartych na drzewach. Problem jest następujący: Chcesz przetestować …
1
Wykrywanie relacji liczb całkowitych dla podzbioru sumy lub NPP?
Czy istnieje sposób na zakodowanie wystąpienia Sumy Podzbioru lub Problemu Podziału Liczby, aby (małe) rozwiązanie relacji liczb całkowitych dało odpowiedź? Jeśli nie zdecydowanie, to w pewnym sensie probabilistycznym? Wiem, że LLL (i być może PSLQ) zostały zastosowane z umiarkowanym sukcesem w rozwiązywaniu problemów sumy częściowej w regionie „niskiej gęstości”, w …
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.