Informatyka

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

9
Wyjaśnienie różnicy między informatyką a umiejętnością obsługi komputera [zamknięte]
Jaka jest dobra metafora lub przykład dla wyjaśnienia angielskiej ważnej różnicy między klasyczną informatyką a „byciem dobrym w używaniu MS-Windows” Informatyka programowanie komputerowe za pomocą komputerów 3 bardzo różne rzeczy. Większość ludzi nie ma pojęcia, czym jest informatyka. Widzą tylko słowo „komputer”. Dlatego „on jest studentem informatyki” można interpretować jako …
7
Różnice i związki między algorytmami losowymi i niedeterministycznymi?
Jakie różnice i zależności występują między algorytmami losowymi a algorytmami niedeterministycznymi? Z Wikipedii Randomizowane algorytm jest algorytmem, w którym stosuje się stopniem losowości jako część logiki. Algorytm zwykle wykorzystuje jednolicie losowe bity jako pomocnicze dane wejściowe do kierowania jego zachowaniem, w nadziei na osiągnięcie dobrej wydajności w „przeciętnym przypadku” względem …
7
Czy istnieje bardziej intuicyjny dowód nierozstrzygalności problemu zatrzymania niż przekątna?
Rozumiem dowód nierozstrzygalności problemu zatrzymania (podany na przykład w podręczniku Papadimitriou), oparty na przekątnej. Chociaż dowód jest przekonujący (rozumiem każdy jego krok), nie jest dla mnie intuicyjny w tym sensie, że nie widzę, jak ktoś by go wyprowadził, zaczynając od samego problemu. W książce dowód wygląda następująco: „załóżmy, że MHMHM_H …
4
Zlicz wszystkie nieizomorficzne wykresy o określonym rozmiarze
Chciałbym wyliczyć wszystkie niekierowane wykresy wielkości , ale potrzebuję tylko jednego wystąpienia każdej klasy izomorfizmu . Innymi słowy, chcę wyliczyć wszystkie nieizomorficzne (niekierowane) wykresy na wierzchołkach. W jaki sposób mogę to zrobić?nnnnnn Dokładniej, chcę algorytmu, który wygeneruje sekwencję niekierowanych wykresów , z następującą właściwością: dla każdego niekierowanego wykresu na wierzchołkach …
2
Teza Churcha-Turinga i moc obliczeniowa sieci neuronowych
Teza Church-Turinga stwierdza, że ​​wszystko, co można fizycznie obliczyć, można obliczyć na maszynie Turinga. Artykuł „Obliczenia analogowe przez sieci neuronowe” (Siegelmannn i Sontag, Theoretical Computer Science , 131: 331–360, 1994; PDF ) twierdzi, że sieć neuronowa o określonej formie (ustawienia są przedstawione w artykule) jest silniejsza. Autorzy twierdzą, że w …
2
Czy Lambda Calculus jest czysto składniowy?
Czytałem od kilku tygodni o rachunku Lambda, ale jeszcze nie widziałem niczego, co różni się materialnie od istniejących funkcji matematycznych i chcę wiedzieć, czy to tylko kwestia notacji, czy też są jakieś nowe właściwości lub reguły utworzone przez aksjomaty rachunku lambda, które nie mają zastosowania do każdej funkcji matematycznej. Na …
4
Co miał na myśli Turing, mówiąc, że „maszyny nie mogą wywoływać niespodzianek” wynika z błędu?
Natknąłem poniżej rachunku przez Alana M. Turinga tutaj : „Pogląd, że maszyny nie mogą wywoływać niespodzianek, jest, jak sądzę, spowodowany błędem, któremu szczególnie podoba się filozofów i matematyków. Jest to założenie, że jak tylko fakt zostanie przedstawiony umysłowi, wszystkie konsekwencje tego faktu stają się widoczne umysł jednocześnie z nim. Jest …
2
Dlaczego jest więcej funkcji, które nie są obliczalne niż funkcje obliczalne?
Obecnie czytam książkę o algorytmach i złożoności. W tej chwili czytam o funkcjach obliczalnych i niepoliczalnych, a moja książka stwierdza, że ​​jest o wiele więcej funkcji, które nie są obliczalne niż obliczalne, w rzeczywistości większość jest niepoliczalna. W pewnym sensie intuicyjnie mogę to zaakceptować, ale książka nie daje formalnego dowodu …
5
Wyjaśnienie wyszukiwania logicznego
Moja matka bierze udział w kursie internetowym, aby zostać bibliotekarką, w tym kursie obejmują wyszukiwania boolowskie, dzięki czemu mogą skutecznie przeszukiwać bazy danych, jednak pojawiło się pytanie brzmiące mniej więcej tak: Wyszukiwanie „x OR y” spowoduje 105 000 trafień, podczas gdy wyszukiwanie tylko x da 80 000 trafień, a wyszukiwanie …
29 sets  counting 
2
Skąd wziąć wykresy do przetestowania moich algorytmów wyszukiwania?
Wdrażam zestaw algorytmów wyszukiwania ścieżek, takich jak Dijkstra's, Depth First itp. Początkowo korzystałem z kilku samodzielnie wykonanych wykresów, ale teraz chciałbym podjąć wyzwanie nieco dalej, dlatego szukam jednego z nich wykresy stosowane w testach porównawczych; wykresy miast świata rzeczywistego (lub sposób pobrania tego rodzaju informacji z map Google lub innego …
3
Dlaczego relatywizacja jest barierą?
Kiedy wyjaśniłem dowód Baker-Gill-Solovay, że istnieje wyrocznia, którą możemy mieć, , oraz wyrocznia, z którą możemy otrzymać P ≠ N P przyjacielowi, pojawiło się pytanie, dlaczego takie techniki nie nadają się do udowodnienia problemu P ≠ N P i nie mogłem udzielić zadowalającej odpowiedzi.P = N PP=NP\mathsf{P} = \mathsf{NP}P ≠ …
1
Jak trudno policzyć liczbę prostych ścieżek między dwoma węzłami na ukierunkowanym wykresie?
Istnieje prosty algorytm wielomianowy, który decyduje, czy istnieje ścieżka między dwoma węzłami na ukierunkowanym wykresie (po prostu wykonaj rutynowe przemierzanie wykresu za pomocą, powiedzmy, głębokości pierwszego wyszukiwania). Jednak wydaje się, że, co zaskakujące, problem staje się znacznie trudniejszy, jeśli zamiast testowania istnienia chcemy policzyć liczbę ścieżek. Jeśli pozwolimy wierzchołków ścieżki …
7
Czy algorytmy (i ogólnie wydajność) stają się coraz mniej ważne?
Skoro kupowanie mocy obliczeniowej jest znacznie tańsze niż w przeszłości, to czy znajomość algorytmów i efektywność stają się coraz mniej ważne? Oczywiste jest, że chciałbyś uniknąć nieskończonej pętli, więc nie wszystko idzie. Ale jeśli masz lepszy sprzęt, czy możesz mieć gorsze oprogramowanie?
29 efficiency 
2
Dlaczego sumy funkcji nie są policzalne?
Dowiedzieliśmy się o koncepcji wyliczenia funkcji. W praktyce odpowiadają one językom programowania. W pewnej uwadze profesor wspomniał, że klasa wszystkich całkowitych funkcji (tj. Funkcji, które zawsze kończą się dla każdego wejścia) nie jest wyliczalna. Oznaczałoby to, że nie możemy opracować języka programowania, który pozwala nam pisać wszystkie funkcje całkowite, ale …
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.