Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

8
Po co chodzić na informatykę / badania teoretyczne?
Obecnie rozpoczynam naukę na uniwersytecie [informatyka] i tam mamy wiele możliwości, aby zacząć od badań. Przed znalezieniem tej witryny nie miałem zamiaru iść tą drogą [chciałem pracować z AI, prawdopodobnie twórcą gry], ale teraz mogę [lub muszę] dokonać wyboru. Czy możesz mnie przekonać do przyłączenia się do tego „świata”? Jakie …
6
Wyrażenia regularne nie są
Zapytaj nawet kogoś, kto ma doświadczenie w informatyce, co to jest wyrażenie regularne, a odpowiedź prawdopodobnie wykroczy poza ograniczenie bycia w zasięgu automatu skończonego. Na przykład „wyrażenie regularne” /^1?$|^(11+?)\1+$/ stworzona przez znaną osobowość Perla Abigail (i część zestawu testów Perla od 2002 r.) opisuje maszynę, która akceptuje tylko złożone liczby …
1
NP-Kompletność problemu decyzyjnego dla uogólnionego 15-puzzle
Interesuje mnie naturalne uogólnienie słynnej 15-puzzli , w których musisz przesuwać bloki, dopóki nie posortujesz wszystkich podanych liczb (zwykle jest przerwa 1 blok). Teraz uogólnieniem byłoby zwiększenie rozmiaru układanki z 15 do , gdzie jedno pole jest wolne. Stworzyłem małą ilustrację (przerywane strzałki pokazują dozwolone ruchy, a dolna konfiguracja pokazuje …
4
Jaki jest najmniejszy wynik, który publikujesz na ArXivie?
Zasadniczo pytanie brzmi: Jaka jest najmniej możliwa do opublikowania jednostka dla ArXiv? Szczególnie interesujące są pola, które szeroko wykorzystują ArXiv, takie jak obliczenia kwantowe. Ale mile widziane są również komentarze dotyczące innych pól i usług przedruku (takich jak ECCC i ePrint). Szczegółowe pytanie Jest to oparte na dwóch następujących pytaniach: …
6
Zestaw probabilistyczny bez fałszywych trafień?
Tak więc filtry Bloom są całkiem fajne - są zestawami, które obsługują sprawdzanie członkostwa bez fałszywych negatywów, ale z niewielką szansą na fałszywy pozytyw. Ostatnio jednak chciałem mieć „filtr Blooma”, który gwarantuje coś przeciwnego: żadnych fałszywych alarmów, ale potencjalnie fałszywych negatywów. Moja motywacja jest prosta: biorąc pod uwagę ogromny strumień …
3
Dlaczego Coq ma Prop?
Coq ma typ Prop dowodu nieistotne propozycje, które są odrzucane podczas ekstrakcji. Jaki jest tego powód, jeśli używamy Coq tylko do dowodów. Rekwizyt jest impredykatywny, więc Prop: Prop, Coq automatycznie wyszukuje indeksy wszechświata i zamiast tego możemy używać Type (i) wszędzie. Wygląda na to, że Prop bardzo wszystko komplikuje. Czytałem, …
7
Formalne pojęcie złożoności energetycznej problemów obliczeniowych
Złożoność obliczeniowa obejmuje badanie złożoności problemów obliczeniowych w czasie lub przestrzeni. Z punktu widzenia przetwarzania mobilnego energia jest bardzo cennym zasobem obliczeniowym. Czy istnieje dobrze zbadana adaptacja maszyn Turinga, które odpowiadają za energię zużywaną podczas wykonywania algorytmów. Czy istnieją ustalone klasy złożoności energetycznej dla problemów obliczeniowych? Referencje są mile widziane.
2
Jeśli P = NP, czy moglibyśmy uzyskać dowody hipotezy Goldbacha itp.?
To naiwne pytanie z mojej wiedzy; z góry przeprasza. Hipoteza Goldbacha i wiele innych nierozwiązanych pytań w matematyce można zapisać jako krótkie formuły w rachunku predykatów. Na przykład artykuł Cooka „Czy komputery mogą rutynowo odkrywać dowody matematyczne?” formułuje tę hipotezę jako ∀ n [ ( n > 2 ∧ 2 …
7
Jak zacząć w teoretycznej CS?
Jestem studentem pierwszego roku informatyki i już wiem, że chcę studiować na akademii, koncentrując się na kierunkach teoretycznych. Przeczytałem już niektóre artykuły wymienione w tym pytaniu i pytanie to przekonało mnie dalej. Co powinienem teraz robić , jako student, aby zaangażować się w polu? Co mogę zrobić, aby przygotować się …
4
Dowody, które ujawniają głębszą strukturę
Standardowy dowód na powiązanie z Chernoffem (z podręcznika Randomized Algorytmy ) korzysta z funkcji nierówności Markowa i funkcji generowania momentu, z odrobiną rozszerzenia Taylora. Nic zbyt trudnego, ale nieco mechanicznego. Ale istnieją inne dowody związane z Chernoffem, które ujawniają głębszą strukturę napędzającą wynik. Na przykład istnieje wersja teoretyczno-informacyjna, która wykorzystuje …
35 big-list  proofs 
5
Mnożenie liczb całkowitych, gdy jedna liczba całkowita jest ustalona
Niech AAA będzie stałą dodatnią liczbą całkowitą o rozmiarze nnn bitów. Można odpowiednio wstępnie przetworzyć tę liczbę całkowitą. Biorąc pod uwagę kolejną dodatnią liczbę całkowitą BBB o rozmiarze mmm bitów, jaka jest złożoność mnożenia ABABAB ? ϵ = 0(max(n,m))1+ϵ(max(n,m))1+ϵ(\max(n,m))^{1+\epsilon}ϵ=0ϵ=0\epsilon=0
2
Klasy złożoności semantycznej a składniowej
W swojej książce „Computational Complexity” Papadimitriou pisze: RP jest w pewnym sensie nową i niezwykłą klasą złożoności. Żadna żadna wieloznacznie niedeterministyczna maszyna Turinga nie może być podstawą do zdefiniowania języka w RP. Aby maszyna N mogła zdefiniować język w RP , musi mieć niezwykłą właściwość, która na wszystkich wejściach albo …
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.