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

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!

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

• Materiały dla matematyków, którzy chcą dowiedzieć się więcej informatyki
• Czy w teoretycznym CS są jakieś tematy, które bardziej dotyczą czystej matematyki?
• Zastosowania TCS w matematyce klasycznej?
• Solidne zastosowania teorii kategorii w TCS?

The Nature of Computation - Cristopher Moore i Stephan Mertens.