Informatyka

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

1
Czy istnieje jakiś nieogólny algorytm analizowania CFG, który rozpoznaje EPAL?
EPAL, język parzystych palindromów, jest definiowany jako język generowany przez następującą jednoznaczną, bezkontekstową gramatykę: S→aaS→aaS \rightarrow a a S→bbS→bbS \rightarrow b b S→aSaS→aSaS \rightarrow a S a S→bSbS→bSbS \rightarrow b S b EPAL jest „zmorą” wielu algorytmów parsowania: jeszcze nie spotkałem się z żadnym algorytmem parsowania dla jednoznacznych CFG, które …
1
Jak fundamentalne są matroidy i greedoidy w projektowaniu algorytmów?
Początkowo wprowadzono matroidy , aby uogólnić pojęcia liniowej niezależności zbioru podzbiorów stosunku do zbioru I podłoża . Niektóre problemy, które zawierają tę strukturę, pozwalają chciwym algorytmom znaleźć optymalne rozwiązania. Koncepcja greedoidów została później wprowadzona w celu uogólnienia tej struktury, aby uchwycić więcej problemów, które pozwalają na znalezienie optymalnych rozwiązań za …
1
Czy istnieje ekwiwalent drzew van Emde Boasa dla lin?
Ktoś, kogo znam, planuje wdrożyć edytor tekstu w najbliższej przyszłości, co skłoniło mnie do zastanowienia się, jakie struktury danych są szybkie dla edytora tekstu. Najczęściej stosowanymi konstrukcjami są najwyraźniej liny lub bufory szczelinowe . Drzewa Van Emde Boas są prawie najszybszymi kolejkami priorytetowymi, jeśli nie przeszkadza ci górna granica liczby …
1
Grupowanie piosenek (The Joe Walsh Problem)
Orły to rockowa supergrupa z lat 70. i 80., odpowiedzialna za takie klasyki jak Hotel California . Mają dwa dość charakterystyczne dźwięki, jeden, w którym gitarzysta Joe Walsh jest obecny (na przykład w Life in the Fast Lane ), a drugi, gdy jest nieobecny. Te ostatnie utwory mają znacznie bardziej …
4
Jak oszukać heurystyczną kontrolę fabuły?
Nad tutaj , Dave Clarke zaproponował, aby porównać asymptotycznej wzrostu należy wykreślić funkcje w zasięgu ręki. Jako teoretycznie skłonny informatyk nazywam (red.) To vodoo, ponieważ fabuła nigdy nie jest dowodem. Po zastanowieniu muszę się zgodzić, że jest to bardzo użyteczne podejście, które czasami jest niedostatecznie wykorzystywane; fabuła to skuteczny sposób …
5
Jak podejść do wyzwania Vertical Sticks
To pytanie zostało przeniesione z Teoretycznej wymiany stosów komputerowych, ponieważ można na nie odpowiedzieć w ramach wymiany stosów komputerowych. Migrował 7 lat temu . Ten problem pochodzi z wywiadstreet.com Dane są wartości całkowitych Y={y1,...,yn}Y={y1,...,yn}Y=\{y_1,...,y_n\} który reprezentuje nnn segmentów linii, tak że punktami końcowymi segmentu ijai są (i,0)(ja,0)(i, 0) i (i,yi)(ja,yja)(i, …
6
Algorytm rozwiązywania „problemu zatrzymania” Turinga
To pytanie zostało przeniesione z Teoretycznej informatyki stosu wymiany, ponieważ można na nie odpowiedzieć w sprawie informatyki stosu wymiany. Migrował 7 lat temu . „Alan Turing udowodnił w 1936 r., Że nie może istnieć ogólny algorytm rozwiązania problemu zatrzymania dla wszystkich możliwych par danych wejściowych programu” Czy mogę znaleźć ogólny …
1
Czy istnieje skuteczny algorytm dla tego problemu pokrycia cyklu wierzchołków?
To pytanie zostało przeniesione z Mathematics Stack Exchange, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 3 lata temu . Próbowałem znaleźć algorytm do znalezienia maksymalnego pokrycia cyklu wierzchołków ukierunkowanego wykresu - to znaczy zestawu rozłącznych cykli, które zawierają wszystkie wierzchołki w , z jak największą liczbą …
1
Co to jest zegar systemowy i zegar procesora; i jakie są ich funkcje?
Czytając książkę, natknąłem się na akapit podany poniżej: Aby zsynchronizować wszystkie operacje komputera, używany jest zegar systemowy - mały kryształ kwarcu umieszczony na płycie głównej. Zegar systemowy regularnie wysyła sygnał do wszystkich innych komponentów komputera. I kolejny akapit: Wiele komputerów osobistych ma obecnie zegary systemowe działające z częstotliwością 200 MHz, …
2
Dowód kompletności NP problemu z drzewem opinającym
Szukam wskazówek w pytaniu zadanym przez mojego instruktora. Właśnie dlatego doszedłem do wniosku, że problemem decyzyjnym jest :NP-completeNP-complete\sf{NP\text{-}complete} Na wykresie znajduje się drzewo rozpinające w G, które zawiera dokładny zestaw S = { x 1 , x 2 , … , x n } jako liście. I zdobione można wykazać, …
3
Dlaczego Radix Sort ?
W sortowaniu radix najpierw sortujemy według najmniej znaczącej cyfry, a następnie sortujemy według drugiej najmniej znaczącej cyfry itd. I kończymy na posortowanej liście. Teraz, jeśli mamy listę liczb, potrzebujemy bitów, aby odróżnić te liczby. Tak więc liczba wykonanych przez nas przejść sortowania będzie wynosić . Każde przejście zajmuje czas O …
1
Czy pętla „do while” jest wystarczająca dla kompletności Turinga?
Wiem, że w imperatywnych językach programowania pętla while-do jest wystarczająca jako konstrukcja przepływu sterowania, aby uzupełnić język Turinga (jeśli chodzi o przepływ sterowania - oczywiście potrzebujemy również nieograniczonej pamięci i niektórych operatorów ...) . Istota mojego pytania brzmi: czy pętla „do-while” ma taką samą moc obliczeniową jak pętla „do-do”? Innymi …
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.