Informatyka

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

1
Algorytm ścigania ruchomego celu
Załóżmy, że mamy czarną skrzynkę fff którą możemy wyszukać i zresetować. Kiedy przywrócić fff stan fSfSf_S o fff ma wartość pierwiastka wybranego losowo równomiernie ze zbioru {0,1,...,n−1}{0,1,...,n−1}\{0, 1, ..., n - 1\} gdzie nnn jest ustalone i znane dla danego fff . Do zapytania fff , element xxx (przypuszczenie) z …
1
Obsługa struktur danych dla lokalnego wyszukiwania SAT
WalkSAT i GSAT są dobrze znanymi i prostymi lokalnymi algorytmami wyszukiwania służącymi do rozwiązania logicznego problemu satysfakcji. Pseudokod algorytmu GSAT jest kopiowany z pytania Implementacja algorytmu GSAT - Jak wybrać literał, który ma być odwrócony? i przedstawione poniżej. procedure GSAT(A,Max_Tries,Max_Flips) A: is a CNF formula for i:=1 to Max_Tries do …
2
Jak opracować algorytm do rozmieszczania (skalowalnych) okien na ekranie tak, aby zajmował jak najwięcej miejsca?
Chciałbym napisać prosty program, który akceptuje zestaw okien (szerokość + wysokość) oraz rozdzielczość ekranu i wyświetla układ tych okien na ekranie, aby okna zajmowały najwięcej miejsca. Dlatego można zmienić rozmiar okna, zachowując output size >= initial sizei proporcje. Tak więc dla okna chciałbym, aby algorytm zwrócił krotkę .( x , …
3
POŁOWA KLIQUE - NP Kompletny problem
Zacznę od zauważenia, że jest to problem związany z pracą domową, proszę podać tylko porady i związane z nimi obserwacje, proszę BEZ BEZPOŚREDNIEJ ODPOWIEDZI . Powiedziawszy to, oto problem, na który patrzę: Niech HALF-CLIQUE = { | jest nieukierowanym wykresem posiadającym pełny podsgraf z co najmniej węzłami, gdzie n jest …
1
Rodzaje automatycznych dostawców twierdzeń
Uczę się samodzielnie Automated Theorem Proving / SMT solvers / Proof Assistants i piszę serię pytań na temat tego procesu, zaczynając tutaj . Jakie są odpowiednie dowody zautomatyzowanego twierdzenia? Znalazłem Przegląd dostawców twierdzeń Czy to wciąż aktualne? Które są nadal bardzo aktywne, tj. Które są obecnie używane poza grupą, która …
3
Ścieżka do metod formalnych
Często zdarza się, że studenci rozpoczynają doktoraty z ograniczonym doświadczeniem w matematyce i formalnych aspektach informatyki. Oczywiście takim studentom bardzo trudno będzie zostać teoretycznym informatykiem, ale dobrze by było, gdyby mogli się zorientować w stosowaniu metod formalnych i czytaniu artykułów zawierających metody formalne. Jaka jest dobra, krótkoterminowa ścieżka, którą mogą …
3
Czy dzisiejsze masywne równoległe jednostki przetwarzania są w stanie efektywnie uruchamiać automaty komórkowe?
Zastanawiam się, czy obecnie masowo równoległe jednostki obliczeniowe dostępne w kartach graficznych ( na przykład programowalne w OpenCL ) są wystarczająco dobre, aby skutecznie symulować automaty komórkowe 1D (a może automaty komórkowe 2D?). Jeśli wybierzemy dowolną skończoną siatkę, która mieści się w pamięci układu, czy możemy oczekiwać, że jedno przejście …
1
Implementacja algorytmu GSAT - Jak wybrać literał do przerzucenia?
Algorytm GSAT jest w większości prosty: dostajesz formułę w spójnej normalnej formie i przerzucasz literały klauzul, aż znajdziesz rozwiązanie, które spełnia formułę lub nie osiągniesz limitu max_tries / max_flips i nie znajdziesz rozwiązania. Implementuję następujący algorytm: procedure GSAT(A,Max_Tries,Max_Flips) A: is a CNF formula for i:=1 to Max_Tries do S <- …
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.