Informatyka

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

3
Co oznaczają „dane niepatologiczne”?
Wziąłem lekcję algorytmów na Coursera. Tak powiedział profesor w filmie o tabelach skrótów Prawdą jest, że w przypadku danych niepatologicznych dostaniesz operacje o stałym czasie w odpowiednio zaimplementowanej tabeli skrótów. Co oznaczają „dane niepatologiczne”? Czy możesz podać jakieś przykłady?
2
Jakie są potencjalne pułapki związane z minimalnym jądrem, które uruchamia kod zarządzany?
Załóżmy, że chcę zbudować system operacyjny oparty na bardzo małym macierzystym dolnym jądrze, które działa jako interpreter / środowisko wykonawcze kodu zarządzanego i większe górne jądro skompilowane do nienatywnego języka maszynowego (bajtowy kod Java, CIL itp.). Przykładami podobnych systemów operacyjnych byłyby Osobliwość i Kosmos . Jakie pułapki i wyzwania związane …
2
Wydajność mikrojądra vs jądro monolityczne
Mikrojądro implementuje wszystkie sterowniki jako programy przestrzeni użytkownika i implementuje podstawowe funkcje, takie jak IPC w samym jądrze. Jądro monolityczne implementuje jednak sterowniki jako część jądra (np. Działa w trybie jądra). Czytałem niektóre twierdzenia, że ​​mikrojądra są wolniejsze niż monolityczne jądra, ponieważ muszą obsługiwać przekazywanie wiadomości między sterownikami w przestrzeni …
2
Jakie są najnowocześniejsze algorytmy wyszukiwania ścieżek na ciągłej mapie Ziemi?
Załóżmy, że mam gdzieś na fiordach Norwegii autonomiczny statek powierzchniowy zasilany energią słoneczną, wyposażony w całkiem nowy zestaw map, odbiornik GPS i nie ma możliwości przesyłania szczegółowych poleceń ode mnie. Statek ten musi dotrzeć na wyspę Hainan w najwcześniejszym możliwym momencie. Jakie są deterministyczne algorytmy wyszukiwania trasy morskiej na kuli …
3
Złożoność problemu adopcji kociąt
To pojawiło się, gdy próbowałem odpowiedzieć na to pytanie dotyczące minimalizacji długości przewodów . Miałem to nazwać problemem „poligamicznego małżeństwa”, ale internet, tak kocięta. Tak! Załóżmy, że mamy kociąt, które muszą być przyjęte przez ludzi, . Dla każdego kociaka, i każdej osoby kosztuje . Chcielibyśmy zminimalizować całkowity koszt przyjęcia wszystkich …
4
Czy wymagana jest przechodnie algorytm sortowania
Czy można zastosować algorytm sortowania z nieprzechodnim porównaniem, a jeśli tak, dlaczego wymienność przechodni jest wymieniona jako wymóg dla sortujących komparatorów? Tło: Algorytm sortowania ogólnie sortuje elementy listy według funkcji komparatora C (x, y), przy pomocy C(x,y)=⎧⎩⎨−10+1if x≺yif x∼ygdyby x≻yC(x,y)={−1if x≺y0if x∼y+1gdyby x≻y\begin{array}{ll} C(x,y) = \begin{cases} -1 & {\text{if}}\ x\prec …
2
Skutecznie próbkuj najkrótsze ścieżki
Niech GGG jest wykresem, niech sss i ttt są dwa wierzchołki GGG . Możemy skutecznie próbki najkrótszą sss - ttt ścieżkę równomiernie i niezależnie losowo ze zbioru wszystkich najkrótszych ścieżek między sss i ttt ? Dla uproszczenia możemy założyć, że GGG jest prosty, nieukierunkowany i nieważony. Nawet w ograniczonych wielu …
2
Najkrótsza nie przecinająca się ścieżka dla wykresu osadzonego w płaszczyźnie euklidesowej (2D)
Jakiego algorytmu użyłbyś do znalezienia najkrótszej ścieżki wykresu, która jest osadzona w płaszczyźnie euklidesowej, tak aby ścieżka nie zawierała żadnych skrzyżowań własnych (w osadzaniu)? Na przykład na poniższym wykresie chcesz przejść z . Zwykle algorytm taki jak algorytm Dijkstry tworzyłby następującą sekwencję:( 0 , 0 ) → ( - 3 …
4
Automatycznie „zgadnij” - co to oznacza?
Zdaję sobie sprawę z tego, że niedeterministyczne automaty wypychające mogą być ulepszeniem w stosunku do automatów deterministycznych, ponieważ mogą „wybierać” spośród kilku stanów i istnieje kilka języków bezkontekstowych, których nie można zaakceptować przez deterministyczne przepychanie. Nadal nie rozumiem, jak dokładnie „wybierają”. Na przykład w przypadku palindormes każde znalezione źródło mówi …
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.