Teoretyczne informatyczne zasoby do samodzielnej nauki dla programistów

14

Jestem dość sprawnym inżynierem oprogramowania, ale niewiele wiem teorii. Chcę dowiedzieć się więcej teorii. Szczególne tematy, którymi się interesuję, to: złożoność obliczeniowa, języki formalne i teoria typów. Ale nie wiem, jak zacząć uczyć się o tych dziedzinach.

Jakie zasoby poleciłbyś komuś, kto chce nauczyć się więcej teorii poprzez samokształcenie? Czy są jakieś teoretyczne przewodniki do samodzielnej nauki dla inżynierów oprogramowania?

soft-question teaching books Henry H.
źródło
3
To zależy od tego, czego chcesz się nauczyć. Arora-Barak daje gruntowne wprowadzenie do teorii złożoności obliczeniowej (i jest bezpłatnie dostępna online). To dobre miejsce na rozpoczęcie.
Thomas wspiera Monikę
4
Czy uczestniczyłeś w kursach teoretycznych na uniwersytecie, takich jak struktury danych, algorytmy itp.? Jeśli nie wybrałeś zazwyczaj wymaganych kursów teoretycznych na studiach licencjackich, dobrym punktem wyjścia będą podręczniki do tych kursów. Następnie możesz przejrzeć artykuły z wikipedii, naszą listę książek i filmów , kursy online w Coursera / Udacity / EdX / ... Coursera ma całkiem niezłe kursy teoretyczne.
Kaveh
Czego studiowałeś na studiach?
Omar Shehab
W jakich językach programujesz? Wiele teoretycznych CS można nauczyć się w połączeniu z czymś konkretnym. Na przykład, jeśli chcesz dowiedzieć się więcej o językach formalnych, dobrym językiem na początek są regularne języki / wyrażenia (tj. Wyrażenia regularne), podobnie jak nauka kompilatorów. W przypadku teorii typów możesz chcieć grać statycznie typowanym językiem, takim jak haskell, F # lub ML.
Baby Dragon
wypróbuj New Turing Omnibus by Dewdney jako szeroki / dostępny wstęp do ref / ankiety / przekroju. patrz także pop książek naukowych, które inspirują TCS
vzn

Odpowiedzi:

7

To szerokie pole z kilkoma całkiem różnymi obszarami.

Zacznę od kilku najbardziej podstawowych pomysłów na temat komputerów: Hopcroft i Ullman, „Wprowadzenie do teorii automatów, języków i obliczeń”.

Powodem, dla którego szczególnie polecam, jest nacisk na dowody. Prowadzą cię przez rygorystyczny sposób myślenia. To jest różnica między pisaniem programów a byciem naukowym.

Kate F.
źródło
1
Dzięki! Nie wiem, czy to cokolwiek zmienia, ale tak naprawdę mam pewne doświadczenie w matematyce opartej na dowodach (prawdopodobnie powinienem był o tym wspomnieć w pytaniu). Przeprowadziłem prawdziwą analizę opartą na dowodach, topologię punktów i algebrę abstrakcyjną.
Henry H.
Wtedy będziesz w stanie szybko przez to przejść :)
Kate F
jego różnica ale nie różnica. CS pociąga za sobą wiele innych zasad itp.
od
Nie sądzę, że potrzeba rygorystyczności jest tak naprawdę różnicą między programowaniem a matematyką. Twierdzenia o programowaniu i dowodzeniu są bardzo podobnymi zadaniami (por. Izomorfizm Curry'ego-Howarda) i prawie żadne zadanie nie matematyczne wymaga więcej rygorystyczności niż programowanie. Kompilatory znacznie mniej wybaczają błędy niż ludzie, którzy czytają dowody.
Jan Johannsen
2
@JanJohannsen Nie zgadzam się - na przykład patrz Niezdefiniowane zachowanie C.
Kate F
9

Istnieje kilka sposobów na poznanie teorii typów. Dla działającego programisty Typy i języki programowania autorstwa B. Pierce to dobry początek. Praktyczne podstawy dla języków programowania autorstwa R. Harpera również mogą być dobre. Jeśli chcesz trochę czytelnego tła na temat semantyki operacyjnej, polecam G. Winskel's, The Formal Semantics of Programming Languages: An Introduction . Z T. Nipkow, G. Klein, Concrete Semantics , wariant książki Winskela został sformalizowany dla interaktywnego asystenta dowodu Isabelle / HOL. Podejrzewam, że naprawdę trudno jest poradzić sobie z koniczyną właśnie z tej (lub dowolnej) książki, chciałbyś, aby ekspert w pobliżu zadawał pytania. Jeśli chcesz bardziej matematycznego podejścia do teorii typów, możesz spojrzeć na JR Hindleya, JP Seldina,Rachunek Lambda i kombinatory: wprowadzenie lub H. Barendregt's, Lambda Calculi z typami . Chociaż nie polecałbym zaczynać od Barendregt.

Jeśli chcesz jednej rekomendacji, powiedziałbym, że przeczytałeś wszystkie artykuły Pierce z wyjątkiem Części VI (Systemy wyższego rzędu) i zaimplementowałem języki zabawek omówione w książce. Skończysz z silnym ugruntowaniem teorii typów i prawdopodobnie lepszym programistą.

Martin Berger
źródło
2

Polecam Obliczalność, złożoność i języki autorstwa Martina Davisa, Rona Sigala i Elaine Weyuker.

valepert
źródło
To piękna książka dla old-skool TCS. Z wyjątkiem części semantyki teorii domen, którą można pominąć.
Martin Berger,
1

Jestem wielkim fanem teorii i algorytmów. Miałem kiedyś okazję odwiedzić Teoretyczną Informatykę w Indian Institute of Technology, Madras (IIT-M), Indie. Znam wielu teoretyków tam w IIT-M. Kiedy tam pojechałem, nie miałem pojęcia, czym była teoria, ale dzisiaj jestem z nią całkowicie zakochany.

Dzięki @Kate F dla wskaźnika, tak Hopcroft i Ullman to doskonałe miejsce do rozpoczęcia.

Jednak oto jak zacząłem,

  1. Przeczytaj wprowadzenie do algorytmów autorstwa Cormena. <\ Br> To doskonałe miejsce na rozpoczęcie. Podczas nauki staraj się zrozumieć każdy dowód tak długo, jak to możliwe. Jeśli dobrze rozumiesz dowód, spróbuj zakodować tę samą logikę w dowolnym wybranym języku. (Trwa to trochę dłużej, ale warto spróbować)

  2. Śledź najważniejsze konferencje w teorii, takie jak
    FOCS
    SODA
    STOC
    EC (Handel elektroniczny) - Algorytmiczna teoria gier
    COLT (Konferencja na temat teorii uczenia się) - Nauka teorii
    CRYPTO - Kryptografia
    SOCG (Sympozjum na temat geometrii obliczeniowej) - Geometria obliczeniowa
    CCC (Konferencja na temat Złożoność obliczeniowa) - teoria złożoności

Nawet jeśli nie rozumiesz zbyt wiele, staraj się czytać i MYŚLEĆ jak najwięcej. Musisz zrobić jak najwięcej dowodów.

  1. Jest to cudowne miejsce, w którym możesz się zastanowić, jeśli myślisz w szczególności o złożoności obliczeniowej ( pochodzi ze Stanford ).
  2. Śledź prof. Sanjeev Arora, Boaz Barak, Jelani Nelson, Madhu Sudan
  3. Oto zestaw zsyntetyzowanych informacji w dziedzinie złożoności obliczeniowej
Jaugust
źródło