Informatyka

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

1
Przybliżenie minimalnej przepustowości drzew binarnych
Problem z minimalną przepustowością polega na znalezieniu kolejności węzłów wykresu na linii całkowitej, która minimalizuje największą odległość między dowolnymi dwoma sąsiadującymi węzłami. Problem decyzyjny jest NP-zupełny nawet dla drzew binarnych. Wyniki złożoności dla minimalizacji przepustowości. Garey, Graham, Johnson and Knuth, SIAM J. Appl. Math., Vol. 34, nr 3, 1978 . …
6
Przykłady zaawansowanych algorytmów rekurencyjnych
Wyjaśniłem przyjacielowi słynny deterministyczny algorytm wyboru czasu liniowego (mediana algorytmu median). Rekurencja w tym algorytmie (choć jest bardzo prosta) jest dość skomplikowana. Istnieją dwa wywołania rekurencyjne, każde o różnych parametrach. Próbowałem znaleźć inne przykłady tak interesujących algorytmów rekurencyjnych, ale nie znalazłem żadnego. Wszystkie algorytmy rekurencyjne, które mogłem wymyślić, są albo …
3
Co jest nie tak z sumami warunków Landau?
napisałem ∑i=1n1i=∑i=1nO(1)=O(n)∑i=1n1i=∑i=1nO(1)=O(n)\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n) ale mój przyjaciel mówi, że to źle. Z ściągawki TCS wiem, że suma nazywa się również HnHnH_n która ma logarytmiczny wzrost w nnn . Więc moja granica nie jest zbyt ostra, ale wystarcza do analizy, której potrzebowałem. Co zrobiłem źle? …
1
Kroki gwarantujące wyjście z labiryntu
Biorąc pod uwagę dwuwymiarowy labirynt, w którym możesz wydać 4 polecenia „ruch w górę / dół / prawo / lewo”. Znając labirynt, ale nie wiedząc, gdzie jest człowiek, jak znaleźć minimalną sekwencję poleceń, która gwarantuje wyjście z labiryntu? Szukam pojedynczej sekwencji poleceń, która zadziała bez względu na to, od którego …
2
Co to jest „klucz” w informatyce?
Jestem trochę zdezorientowany, co dokładnie oznacza „klucz” w informatyce. Rozumiem pary klucz-wartość, klucze podstawowe itp. Ale nie mogę znaleźć definicji tego, co oznacza pojęcie „klucz” samo w sobie. O ile mogę to stwierdzić, oznacza to po prostu kawałek danych. W CLRS dane powiązane z węzłami drzewa są nazywane „kluczami”. Dane …
1
„Słynni logicy popełniali tutaj zawstydzające błędy”, wiersz z SICP. Do czego to się odnosi?
Oto kontekst ( Struktura i interpretacja programów komputerowych , sekcja 1.1.8, pod nagłówkiem „Nazwy lokalne”): Formalny parametr procedury ma bardzo szczególną rolę w definicji procedury, ponieważ nie ma znaczenia, jaką nazwę ma parametr formalny. Taka nazwa nazywa się zmienną powiązaną i mówimy, że definicja procedury wiąże jej parametry formalne. Znaczenie …
14 logic 
1
Czy pochodna wykresu jest związana z listami przyległości?
Niektóre prace Conora McBride'a, Diff , Dissect , wiążą pochodną typów danych z ich „typem jednootworowych kontekstów”. Oznacza to, że jeśli weźmiesz pochodną typu, pozostanie ci typ danych, który pokazuje, jak typ danych wygląda od wewnątrz w danym punkcie. Na przykład, jeśli masz listę (w Haskell) data List a = …
2
Wykres resztkowy w maksymalnym przepływie
Czytam tutaj o problemie z maksymalnym przepływem . Nie mogłem zrozumieć intuicji stojącej za wykresem rezydualnym. Dlaczego podczas obliczania przepływu bierzemy pod uwagę tylne krawędzie? Czy ktoś może mi pomóc zrozumieć pojęcie wykresu resztkowego? Jak zmienia się algorytm w niekierowanych grafach?
3
Dlaczego operator gwiazdy Kleene jest również nazywany operatorem „zamykania” Kleene?
Przekonałem się, że jeśli nie rozumiem etymologii kryjącej się za terminem cs / programowanie, zwykle oznacza to, że przeoczyłem lub źle zrozumiałem jakąś ważną koncepcję. Nie rozumiem, dlaczego gwiazda Kleene jest również nazywana zamknięciem Kleene. Czy ma to związek z zamknięciami w programowaniu, funkcją ze związanymi zmiennymi nielokalnymi? ... po …
1
Złożoność obliczeniowa a hierarchia Chomsky'ego
Zastanawiam się ogólnie nad związkiem między złożonością obliczeniową a hierarchią Chomsky'ego. W szczególności, jeśli wiem, że jakiś problem jest NP-zupełny, czy wynika z tego, że język tego problemu nie jest pozbawiony kontekstu? Na przykład problem kliki jest NP-zupełny. Czy wynika z tego, że język odpowiadający modelom z klikami ma pewną …
2
Skrócenie czasu między ILP a SAT?
Tak więc, jak wiadomo, problem decyzyjny ILP 0-1 jest NP-zupełny. Pokazanie tego w NP jest łatwe, a pierwotna redukcja pochodziła z SAT; od tego czasu wykazano, że wiele innych problemów z NP-Complete ma formulacje ILP (które działają jako redukcje tych problemów do ILP), ponieważ ILP jest bardzo przydatna ogólnie. Redukcje …
2
Dowód poprawności algorytmu zachłannego dla minimalnego pokrycia wierzchołka drzewa
Istnieje chciwy algorytm znajdowania minimalnego pokrycia wierzchołka drzewa, które korzysta z przejścia DFS. Dla każdego liścia drzewa wybierz jego element nadrzędny (tzn. Jego element nadrzędny znajduje się w minimalnej osłonie wierzchołków). Dla każdego węzła wewnętrznego: jeśli nie zostanie wybrane żadne z jego elementów podrzędnych, wybierz ten węzeł. Jak udowodnić, że …
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.