Informatyka

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

10
Jeśli prędkość ładowania elektrycznego się nie zmieniła, w jaki sposób komputery stały się szybsze?
Wszyscy wiedzą, że prędkość obliczeniowa drastycznie wzrosła od czasu ich wynalezienia i wygląda na to, że będzie kontynuowana. Zastanawia mnie jednak jedna rzecz: gdybyś dzisiaj przepuścił prąd elektryczny przez materiał, poruszałby się on z taką samą prędkością, jak gdybyś zrobił to z tym samym materiałem 50 lat temu. Mając to …
8
Jak udowodnić, że język jest regularny?
Istnieje wiele metod, aby udowodnić, że dany język nie jest regularny , ale co muszę zrobić, aby udowodnić, że jakiś język jest prawidłowy? Na przykład, jeśli otrzymam informację, że jest regularne, jak mogę udowodnić, że następujące jest również regularne?L ′LLLL′L′L' L′:={w∈L:uv=w for u∈Σ∗∖L and v∈Σ+}L′:={w∈L:uv=w for u∈Σ∗∖L and v∈Σ+}\qquad \displaystyle …
2
Definicja kolejności wzrostu od Reynolds & Tymann
Czytam książkę Principles of Computer Science (2008) Carla Reynoldsa i Paula Tymanna (wydaną przez Zarysy Schauma). Drugi rozdział przedstawia algorytmy z przykładem wyszukiwania sekwencyjnego, które po prostu iteruje listę nazw i zwraca PRAWDA, jeśli dana nazwa zostanie znaleziona na liście. Autor kontynuuje (strona 17): Mówimy, że „kolejność wzrostu” algorytmu wyszukiwania …
10
O (·) nie jest funkcją, więc w jaki sposób funkcja może być jej równa?
Całkowicie rozumiem, co oznacza duża notacjaMój problem polega na tym, że mówimy , gdzie jest czasem działania algorytmu na wejściu wielkości .OOOT(n)=O(f(n))T(n)=O(f(n))T(n)=O(f(n))T(n)T(n)T(n)nnn Rozumiem semantykę tego. Ale i to dwie różne rzeczy.T(n)T(n)T(n)O(f(n))O(f(n))O(f(n)) T(n)T(n)T(n) jest dokładną liczbą, ale nie jest funkcją, która wyrzuca liczbę, więc technicznie nie możemy powiedzieć, że równa się …
4
Dlaczego drzewa czerwono-czarne są tak popularne?
Wygląda na to, że gdziekolwiek spojrzę, struktury danych są wdrażane przy użyciu czerwono-czarnych drzew ( std::setw C ++, SortedDictionaryw C # itp.) Właśnie omawiając (a, b), czerwono-czarne i drzewa AVL w mojej klasie algorytmów, oto co wyciągnąłem (również z pytania po profesorach, przeglądania kilku książek i przeglądania go trochę): Drzewa …
9
Czy istnieje kolejka priorytetowa z wyciągami ?
Istnieje wiele struktur danych, które implementują interfejs kolejki priorytetowej: Wstaw: wstaw element do struktury Get-Min: zwraca najmniejszy element w strukturze Extract-Min: usuń najmniejszy element ze struktury Typowe struktury danych implementujące ten interfejs to (min) hałdy . Zazwyczaj (zamortyzowane) czasy wykonywania tych operacji są następujące: Wstaw: (czasami )O ( log n …
5
Dlaczego badania algorytmów genetycznych uległy spowolnieniu?
Omawiając dziś niektóre tematy wprowadzające, w tym wykorzystanie algorytmów genetycznych; Powiedziano mi, że badania naprawdę spowolniły w tej dziedzinie. Podany powód był taki, że większość ludzi koncentruje się na uczeniu maszynowym i eksploracji danych. Aktualizacja: czy to jest dokładne? A jeśli tak, jakie zalety ma ML / DM w porównaniu …
2
Znaleźć medianę niesegregowanych tablicy w
Aby znaleźć medianę nieposortowanej tablicy, możemy wykonać min-stos w czasie dla n elementów, a następnie możemy wyodrębnić jeden po drugim n / 2 elementów, aby uzyskać medianę. Ale takie podejście zająłoby czas O ( n log n ) .O ( n logn )O(nlog⁡n)O(n\log n)nnnn / 2n/2)n/2O ( n logn )O(nlog⁡n)O(n …
2
Jak kombinator Y ilustruje „niespójność rachunku Lambda”?
Na stronie Wikipedii dla Fixed Point Combinators jest napisany dość tajemniczy tekst Kombinator Y jest przykładem tego, co powoduje, że rachunek Lambda jest niespójny. Dlatego należy to traktować podejrzliwie. Można jednak bezpiecznie rozważyć kombinator Y, gdy jest on zdefiniowany tylko w logice matematycznej. Czy wdałem się w jakąś powieść szpiegowską? …
7
Minimalne drzewo opinające vs Najkrótsza ścieżka
Jaka jest różnica między algorytmem minimalnego drzewa opinającego a algorytmem najkrótszej ścieżki? W mojej klasie struktur danych omówiliśmy dwa algorytmy minimalnego drzewa opinającego (Prim i Kruskala) oraz jeden algorytm najkrótszej ścieżki (Dijkstry). Minimalne drzewo opinające to drzewo na wykresie, które obejmuje wszystkie wierzchołki, a całkowita waga drzewa jest minimalna. Najkrótsza …
3
Najdłuższa ścieżka w niekierowanym drzewie z tylko jednym przejściem
Istnieje standardowy algorytm znajdowania najdłuższej ścieżki w nieukierunkowanych drzewach przy użyciu dwóch wyszukiwań w pierwszej kolejności: Uruchom DFS od losowego wierzchołka i znajdź od niego najdalszy wierzchołek; powiedzmy, że to v ′ .vvvv′v′v' Teraz uruchom DFS od aby znaleźć wierzchołek najdalej od niego. Ta ścieżka jest najdłuższą ścieżką na wykresie.v′v′v' …
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.