Informatyka

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

29
Dlaczego zapisywanie dowodów matematycznych jest bardziej odporne na błędy niż pisanie kodu komputerowego?
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, który cały czas mówi im, jaki jest błąd. …
3
Czy istnieje magia analizy algorytmów?
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ę być dostosowana do indywidualnych potrzeb. Z drugiej strony odpowiedzi na …
12
Dlaczego tak naprawdę problem zatrzymania jest tak ważny?
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, który wykrywa, czy lista połączona zapętla się w celu zaimplementowania funkcji zatrzymania o złożoności …
3
Jak można rozstrzygać, czy ma pewną sekwencję cyfr?
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} Wykazać, że jest obliczalne.fff Jak to jest możliwe? O ile mi …
12
Dlaczego jest tyle języków programowania?
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 …
14
Dlaczego mogę spojrzeć na wykres i od razu znaleźć najbliższy punkt do innego punktu, ale programowanie zajmuje mi O (n) czasu?
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 przy programowaniu, biorąc pod uwagę zestaw punktów n, …
6
Czy teoria kategorii jest przydatna do nauki programowania funkcjonalnego?
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ć dobrą podstawę do zrozumienia Haskell?
4
Jak przekonwertować skończone automaty na wyrażenia regularne?
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 równoważne wyrażenia regularne? Czy są zalety dotyczące złożoności czasu lub …
6
Dlaczego nie istniał algorytm szyfrowania oparty na znanych problemach NP-Hard?
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 NP-trudnym. Brzmi (przynajmniej teoretycznie) tak, jakby był …
13
Jak oszukać heurystykę „wypróbuj niektóre przypadki testowe”: Algorytmy, które wydają się prawidłowe, ale w rzeczywistości są nieprawidłowe
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 świetna heurystyka: to świetny sposób na szybkie wyeliminowanie wielu niepoprawnych …
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.