Pytania i odpowiedzi dla studentów, naukowców i praktyków informatyki
W standardowym kursie z algorytmów uczymy się, że quicksort wynosi średnio a O ( n 2 ) w najgorszym przypadku. Jednocześnie badane są inne algorytmy sortowania, które w najgorszym przypadku to O ( n log n ) (np. Scalesort i heapsort ), a nawet czas liniowy w najlepszym przypadku (np. Bąbelkowy ),...
Zauważyłem, że o wiele łatwiej jest mi zapisać matematyczne dowody bez popełniania błędów niż napisać program komputerowy bez błędów. Wydaje się, że jest to coś bardziej rozpowszechnionego niż tylko moje doświadczenie. Większość ludzi cały czas popełniają błędy w oprogramowaniu i mają kompilator,...
Patrząc na stronę Julii , możesz zobaczyć testy porównawcze kilku języków w kilku algorytmach (czasy pokazane poniżej). W jaki sposób język z kompilatorem napisanym pierwotnie w C może przewyższyć kod C? Rysunek: czasy testu porównawczego w stosunku do C (im mniejsze, tym lepsza wydajność C =...
Istnieje wiele pytań dotyczących sposobu analizowania czasu pracy algorytmów (patrz np runtime-analiza i algorytm-analysis ). Wiele z nich jest podobnych, na przykład ci, którzy proszą o analizę kosztów zagnieżdżonych pętli lub algorytmy dzielenia i zdobywania, ale większość odpowiedzi wydaje się...
Nie rozumiem, dlaczego problem zatrzymania jest tak często wykorzystywany do odrzucenia możliwości ustalenia, czy program się zatrzymuje. Wikipedia [artykuł] [1] poprawnie wyjaśnia, że deterministyczna maszyna ze skończoną pamięcią zatrzyma lub powtórzy poprzedni stan. Możesz użyć algorytmu,...
Jestem dość biegły w C / C ++ i potrafię poruszać się po różnych językach skryptowych (awk / sed / perl). Zacząłem używać Pythona o wiele więcej, ponieważ łączy on kilka fajnych aspektów C ++ z możliwościami skryptowymi awk / sed / perl. Ale dlaczego jest tak wiele różnych języków programowania?...
Otrzymaliśmy następujące ćwiczenie. Pozwolić f(n)={100n occurs in the decimal representation of πelsef(n)={10n occurs in the decimal representation of π0else\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}...
Pozwól mi wyjaśnić: Biorąc pod uwagę wykres punktowy pewnej liczby punktów n, jeśli chcę znaleźć mentalnie najbliższy punkt do dowolnego punktu na wykresie, mogę natychmiast zignorować większość punktów na wykresie, zawężając moje wybory do niewielkiej, stałej liczby punktów w pobliżu . Jednak...
Uczę się języka Haskell i fascynuje mnie język. Nie mam jednak żadnego poważnego doświadczenia matematycznego ani CS. Ale jestem doświadczonym programistą. Chcę nauczyć się teorii kategorii, abym mógł stać się lepszy w Haskell. Których tematów z teorii kategorii powinienem nauczyć się zapewniać...
Konwersja wyrażeń regularnych na (minimalne) NFA, które akceptują ten sam język, jest łatwa dzięki standardowym algorytmom, np . Algorytmowi Thompsona . Drugi kierunek wydaje się jednak bardziej nużący, a czasem wynikowe wyrażenia są nieuporządkowane. Jakie są algorytmy przekształcania NFA w...
Większość współczesnego szyfrowania, takiego jak RSA, opiera się na faktoryzacji liczb całkowitych, co nie jest uważane za problem trudny dla NP, ale należy do BQP, co czyni go podatnym na komputery kwantowe. Zastanawiam się, dlaczego nie istniał algorytm szyfrowania oparty na znanym problemie...
Aby spróbować sprawdzić, czy algorytm dla jakiegoś problemu jest prawidłowy, zwykle punktem wyjścia jest próba uruchomienia algorytmu ręcznie na kilku prostych przypadkach testowych - wypróbuj go na kilku przykładowych przypadkach problemów, w tym na kilku prostych „przypadkach narożnych” „. To...
Drzewo indeksowane binarnie nie ma żadnej literatury lub ma stosunkowo niewiele literatury w porównaniu do innych struktur danych. Jedynym miejscem, w którym jest nauczany, jest samouczek topcodera . Chociaż samouczek jest kompletny we wszystkich objaśnieniach, nie rozumiem intuicji stojącej za...
Istnieje wiele prób udowodnienia albo albo P ≠ N P , i oczywiście wiele osób myśli o tym pytaniu, mając pomysły na udowodnienie obu kierunków.P = N PP=NP\mathsf{P} = \mathsf{NP} P ≠ N PP≠NP\mathsf{P} \neq \mathsf{NP} Wiem, że istnieją metody, które okazały się nieskuteczne, i prawdopodobnie jest...
Wiele programów informatycznych wymaga dwóch lub trzech klas rachunku różniczkowego. Zastanawiam się, jak i kiedy stosuje się rachunek różniczkowy w informatyce? Treść CS pewnego stopnia w dziedzinie informatyki zwykle koncentruje się na algorytmach, systemach operacyjnych, strukturach danych,...
Zastanawiam się nad tym pytaniem, odkąd byłem studentem. To pytanie ogólne, ale opiszę poniżej przykłady. Widziałem wiele algorytmów - na przykład dla problemów z maksymalnym przepływem znam około 3 algorytmów, które mogą rozwiązać problem: Ford-Fulkerson, Edmonds-Karp i Dinic, przy czym Dinic ma...
Te dwa wydają się bardzo podobne i mają prawie identyczną strukturę. Co za różnica? Jakie są zawiłości czasowe dla różnych operacji każdego z
W większości klas algorytmów wprowadzających wprowadzane są notacje takie jak (Big O) i , a uczeń zazwyczaj uczy się korzystania z jednej z nich w celu znalezienia złożoności czasowej.ΘOOOΘΘ\Theta Istnieją jednak inne oznaczenia, takie jak , i . Czy są jakieś konkretne scenariusze, w których jedna...
Wzór Vapnika – Chervonenkisa (VC) dla sieci neuronowych zawiera się w przedziale od do , przy czym w najgorszym przypadku, gdzie jest liczbą krawędzi i to liczba węzłów. Liczba próbek treningowych potrzebnych do uzyskania silnej gwarancji uogólnienia jest liniowa z wymiarem...
Istnieją dwie metody partycji Quicksort wymienione w Cormen: Hoare-Partition(A, p, r) x = A[p] i = p - 1 j = r + 1 while true repeat j = j - 1 until A[j] <= x repeat i = i + 1 until A[i] >= x if i < j swap( A[i], A[j] ) else return j i: Lomuto-Partition(A, p, r) x = A[r] i =...