Gdzie dowiedzieć się więcej o tym, czym jest informatyka teoretyczna?


15

Jestem absolwentem matematyki, a informatyka teoretyczna to dziedzina, w której nigdy nie rozumiałam, o co chodzi, ponieważ nie mogłam znaleźć dobrej lektury na ten temat. Chcę wiedzieć, o co tak naprawdę chodzi w tej domenie, jakie tematy ona dotyczy, jakie warunki są potrzebne, aby się w nią zaangażować itp. Na razie chcę tylko wiedzieć:

Jaka jest dobra książka wprowadzająca do informatyki teoretycznej?

Biorąc pod uwagę, że istnieje coś takiego. Jeśli nie, to gdzie powinien zacząć matematyk, który ma podstawową wiedzę z zakresu informatyki (tj. Zna podstawy jednego lub dwóch języków programowania), jeśli chce zrozumieć, na czym polega informatyka teoretyczna? Co polecasz?

dzięki!


1
Świetne pytanie. Naprawdę jestem zagubiony. Teoretyczna CS jest tak szeroka i różnorodna, że ​​wątpię, by ktokolwiek próbował to wszystko zbadać w jednym miejscu. Istnieją książki wprowadzające, takie jak „Teoria obliczeń” Sipsera lub „Algorytmy” Dasgupty, Papadimitriou i Vazirani. Ale są to warunki wstępne dla studentów i nie dają pojęcia o tym, czym właściwie jest TCS „o”…
usul

6
Pytanie jest o wiele za szerokie. Można zatem równie dobrze zapytać: „Gdzie dowiedzieć się więcej o tym, czym jest matematyka?”. Należy zatem przyjrzeć się obszarom TCS zbliżonym do matematyki, takim jak teoria złożoności, kryptografia, przybliżenie. Powiedzmy, że złożoność obwodu jest tylko częścią Extremal Combinatorics. Książka Sipsera jest naprawdę świetna: jest poglądem matematyków na TCS (oczywiście niewielka jej część); Sam Sipser jest matematykiem.
Stasys

2
Nadchodzący tekst Aviego Wigdersona
András Salamon

Odpowiedzi:


29

Po pierwsze, „informatyka teoretyczna” oznacza różne rzeczy dla różnych ludzi. Myślę, że dla większości użytkowników tej witryny historyczną karykaturą (która odzwierciedla niektóre współczesne tendencje socjologiczne) jest to, że istnieje „Teoria A” i „Teoria B” (bez wzajemnej zależności między nimi): Teoria A składa się z teorii algorytmy, teoria złożoności, kryptografia i podobne. Teoria B składa się z takich rzeczy, jak teoria języków programowania, teoria automatów itp. W zależności od upodobań matematycznych możesz preferować jedną z nich (lub podobną). Jestem bardziej zaznajomiony z „Teorią A”, więc pozwólcie, że podam tam kilka odniesień:

  • Zacznij od książki Sipsera. To da ci dobre wprowadzenie do automatów, maszyn Turinga, obliczalności, złożoności Kołmogorowa, P vs NP i kilku innych klas złożoności. Jest bardzo dobrze napisany (moim zdaniem jest to jedna z najlepiej napisanych książek technicznych w historii )

  • Jeśli chodzi o algorytmy, mam niewielkie preferencje wobec Kleinberga-Tardosa, ale istnieje wiele dobrych książek wprowadzających. Być może szczególnie interesuje Cię geometria obliczeniowa, która ma własny zestaw świetnych książek.

  • Biorąc pod uwagę, że jesteś studentem matematyki, główną gałęzią TCS, której brakuje w tych książkach, jest teoria złożoności algebraicznej , która często jest ściśle związana z algebrą (zarówno przemienną, jak i nieprzemienną), teorią reprezentacji, teorią grup i geometrią algebraiczną . Jest tu kanoniczny tekst, którym jest Burgisser-Clausen-Shokrollahi. Jest to nieco encyklopedyczne, więc może nie być najlepszym wstępem, ale nie jestem pewien, czy w tej dziedzinie jest naprawdę książka wprowadzająca. Możesz także sprawdzić ankiety Chen-Kayal-Wigderson i Shiplka-Yehudayoff.

Następnie sugeruję przeglądanie bardziej zaawansowanych książek na określone tematy, w zależności od twojego gustu matematycznego:

  • Arora-Barak jest bardziej nowoczesną teorią złożoności (kontynuuje tam, gdzie, że tak powiem, książka Sipsera kończy się), dając ci posmak zastosowanych technik (głównie kombinacja kombinatoryki i algebry)

  • Książka Jukny na temat złożoności funkcji boolowskich jest podobna, ale bardziej dogłębna w szczególności dla złożoności obwodu boolowskiego (bardzo kombinatoryczny w smaku)

  • Teoria złożoności geometrycznej. Zobacz tutaj lub wprowadzenie Landsberga dla geometrów .

  • Książka O'Donnella „ Analiza funkcji boolowskich” ma bardziej pochylony Fouriera.

  • Kryptografia. Bardziej zaawansowanymi aspektami matematycznymi są zazwyczaj teoria liczb i geometria algebraiczna. Chociaż te czyste matematyczne aspekty stanowią tylko niewielką część kryptografii, są one ważne i mogą cię zainteresować. Nie będąc moim obszarem, nie jestem pewien, jaka jest dobra książka na początek.

  • Teoria kodowania. Tutaj teoria matematyczna rozciąga się od pakowania sfery (patrz książka Conwaya i Sloane'a) do geometrii algebraicznej (np. Książka Stichtenotha). Ponownie, nie moja okolica, więc nie jestem pewien, czy są to najlepsze punkty początkowe, ale przeglądając je szybko uzyskasz smak i zdecydujesz, czy chcesz zagłębić się głębiej.

Jest też wiele innych tematów matematycznych, które pojawiają się tylko w literaturze naukowej, takich jak powiązania z piankami, teoria grafów, algebry C * (pozwólcie, że wskażę tylko hipotezę Kadisona-Singera ), teoria niezmienna, teoria reprezentacji, kwadratury, i tak dalej. Zobacz także te powiązane pytania


2
Dobra książka początkowa do kryptografii to Wprowadzenie do współczesnej kryptografii autorstwa Katz-Lindell: cs.umd.edu/~jkatz/imc.html - Alternatywną (starszą) opcją są Podstawy kryptografii autorstwa Goldreicha: wisdom.weizmann.ac.il /~oded/foc-book.html
Daniel Apon

4

The Nature of Computation - Cristopher Moore i Stephan Mertens.


Ja kocham tę książkę - nie polecam go w moją odpowiedź głównie na jego długości, choć oczywiście zawsze można wybierać rozdziały czytać.
Joshua Grochow
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.