Jakie książki każdy powinien przeczytać?

[ Oś czasu ]

To pytanie ma ten sam duch, co artykuły powinny przeczytać wszyscy i jakie filmy wszyscy powinni oglądać . Prosi o niezwykłe książki z różnych dziedzin informatyki teoretycznej.

Książki mogą być zorientowane na matematykę, ale mogą się okazać przydatne dla informatyków. Przykłady:

• Prawdopodobieństwo
• Nierówności
• Logika
• Teoria grafów
• Kombinatoryka
• Projektowanie i analiza algorytmu
• Teoria obliczeń / Teoria złożoności obliczeniowej

Proszę poświęcić każdą odpowiedź na książki o tym samym temacie (np. Książki o kombinatoryce).

Uwaga: tytuł może wprowadzać w błąd. Oto wyjaśnienie: Niech X i Y będą dwiema dziedzinami informatyki. Są książki, które wszyscy

• w polu X należy przeczytać.
• w polu Y należy przeczytać.
• w obu polach należy przeczytać.

To pytanie dotyczy wszystkich 3 przypadków. Innymi słowy, NIE jest on specyficzny dla tego ostatniego przypadku.

Edycja: Zgodnie z sugestią Dai Le , proszę również wskazać powód, dla którego lubisz książkę.

Powiązane tematy:

• Referencje dla technik proofingu TCS
• Książki z teorii automatów do samodzielnego studiowania
• Książki dla prawdopodobieństwa
• Ulubiona popularna książka matematyczna
• Przewodnik dla początkujących dotyczący derandomizacji
• Referencje dotyczące dolnych granic obwodu
• Artykuł w ankiecie na temat teorii funkcji rekurencyjnych
• Książki na temat programowania semantyki języka
• Jakie są najnowsze książki TCS, których wersje robocze są dostępne online
• Książki o prawdopodobieństwie

Złożoność obliczeniowa:

Jeśli szukasz najnowszych podręczników o złożoności. Muszą mieć następujące dwa.

• Złożoność obliczeniowa: nowoczesne podejście Sanjeeva Arory i Boaza Baraka ( strona główna podręcznika )

• Złożoność obliczeniowa: perspektywa koncepcyjna Oded Goldreich ( strona główna podręcznika )

Większość treści między tymi dwiema książkami jest porównywalna. Istnieją jednak pewne kluczowe różnice: Goldreich poświęca więcej miejsca na badanie konceptualnych i filozoficznych podstaw teorii złożoności, podczas gdy Arora / Barak obejmuje szerszy wybór tematów, w tym konkretne modele złożoności, obliczenia kwantowe i dolne granice obwodu, które są w większości nieobecne od pierwszego.

Inną opcją jest starszy, ale ponadczasowy, złożony podręcznik:

• Złożoność obliczeniowa Christosa Papadimitriou

Książka Papadimitriou jest godna uwagi w rozdziałach obejmujących logikę pierwszego rzędu, a także w klasach SNP, MaxSNP i APX (teoretyczne podstawy twardości aproksymacji), których brakuje w bardziej współczesnych tekstach.$_0$

Kolejny (stosunkowo) stary, ale dość znaczący klasyk to:

• Wprowadzenie do teorii obliczeń Michaela Sipsera

Jest to jeden z niewielu / pierwszych podręczników, który wyraźnie zawiera „Pomysł dowodowy:” pomiędzy „Twierdzeniem:” i „Dowód:” i jest jednym z najlepiej napisanych podręczników matematycznych na dowolny temat. Z drugiej strony jest to tylko wstęp do złożoności, poświęcając tylko jeden 50-stronicowy rozdział „zaawansowanym tematom” (w tym przybliżeniu, algorytmom probabilistycznym, IP = PSPACE i kryptografii). Jako pierwsza książka o złożoności lub jako przykład naprawdę doskonałego pisania, ta książka jest świetna .

• The Nature of Computation - Cristopher Moore i Stephan Mertens

Scott Aaronson pisze, że ta książka ma „zabawę z popularnej książki z intelektualną przewagą podręcznika”. Opowiada historie i podaje wiele zabawnych przykładów i odniesień (Game of Life oraz wiele innych przykładów maszyn z kompletem Turinga). Nie zagłębia się zbytnio w teorię złożoności, ale ma szeroki zasięg. Na szczególną uwagę zasługują jego związki z fizyką statystyczną.

Kompletność NP:

Cóż, myślę, że Garey i Johnson's Computers and Intractability: Przewodnik po teorii NP-Completeness znajdzie się wśród najlepszych książek na tej liście.

Projektowanie i analiza algorytmów:

Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest i Clifford Stein. Wprowadzenie do algorytmów.

R. Motwani, P. Raghavan. Algorytmy randomizowane.

Znalazłem tę książkę sugerowaną przez Ryana Williamsa w MathOverflow: Al Algorytm Design autorstwa Kleinberg & Tardos .

Kolejna doskonała książka Wprowadzenie do algorytmów: kreatywne podejście przez Udi Manber . Ta książka nie jest katalogiem algorytmów; stara się raczej zapewnić czytelnikowi intuicję, aby „rozpoznać strukturę matematyczną w abstrakcyjnych problemach”. (cytowany z recenzji)

Ogólna matematyka dla informatyki:

• Konkretna matematyka: podstawa informatyki Grahama, Knutha i Patashnika.

• The Princeton Companion to Mathematics autorstwa Gowers i in.

• Dowody z KSIĄŻKI Aignera i Zieglera.

Systemy typów i semantyka języka programowania:

Typy i języki programowania Benjamina Pierce'a oraz tom uzupełniający Tematy zaawansowane w typach i językach programowania . Zapewniają rzetelny, ale zrozumiały przegląd roli teorii typów w projektowaniu języka programowania, wraz z wykorzystaniem semantyki operacyjnej do wyrażania semantyki języka programowania.

Nierówności:

Kolejną cenną książką dla każdego informatyka, który kiedykolwiek chce związać dowolną ilość (a więc wszystkich!), Jest: Klasa mistrzowska Cauchy'ego-Schwarza: Wprowadzenie do sztuki nierówności matematycznych Michaela Steele'a.

Encyklopedyczna książka na ten temat to Słownik nierówności . Chociaż nie jest to książka do czytania od deski do deski, dobrze jest mieć ją do dyspozycji. Zobacz także dodatek do książki.

Ponadto Wikipedia ma doskonałą listę nierówności .

W przypadku konkretnych tematów możesz skonsultować:

• Nierówności probabilistyczne
• Nierówności macierzy
• Nierówności geometryczne
• Książka „A = B” Petkovseka, Wilfa i Zeilbergera

Ciekawy. Nikt nie wspomniał tomów Sztuka programowania przez Donald E. Knuth . Bardzo szczegółowe podejście do tematów z bardzo dobrymi ćwiczeniami.

W tej książce znalazłem klejnoty takie jak „pobieranie próbek resorvoir”, żeby wymienić tylko jeden przykład.

Jak już wspomniał Sylvain Peyronnet, logika jest ważną częścią teoretycznej informatyki. Jednak nie wystarczy uczyć się logiki z podręczników przygotowanych dla czystych matematyków. Innymi słowy, ważne jest również, aby uczyć się logiki z bardziej „informatycznej” perspektywy.

Teoria modeli skończonych

Chcemy nauczyć się technik dotyczących struktur skończonych. Dobrze wiadomo, że wiele tradycyjnych narzędzi z teorii modeli, np. Zwartość i twierdzenie Löwenheim-Skolem, nie ma zastosowania do modeli skończonych. To prowadzi nas do badania teorii modeli skończonych . W tym obszarze polecam następujące doskonałe książki:

• Leonid Libkin, Elementy teorii modeli skończonych . (podręcznik)
• Grädel i in., Teoria modeli skończonych i jej zastosowania . (artykuły i aplikacje ankiety)

Podobszarem teorii modeli skończonych jest złożoność opisowa , w której chcemy scharakteryzować klasy złożoności według rodzaju logiki potrzebnej do zdefiniowania języków. Ostateczne odniesienie do złożoności opisowej to:

• Neil Immerman, złożoność opisowa .

Dowód złożoności

Innym ważnym obszarem logiki w informatyce jest Proof Complexity , badanie trójdrożnej zależności między klasami złożoności, słabymi systemami logicznymi i systemem dowodzenia zdań. Rozważane są następujące dwa powiązane aspekty: (i) złożoność dowodów wzorów zdań, oraz (ii) badanie słabych teorii arytmetyki, zwanych arytmetyką ograniczoną .

Aspekt (i) dotyczy następującego pytania: „Czy istnieje system dowodu zdaniowego, w którym każda tautologia ma dowód wielomianu wielkości tautologii?”

Aspekt (ii) bada systemy logiczne, które wykorzystują ograniczone rozumowanie oparte na pojęciach ze złożoności obliczeniowej. Innymi słowy, możemy przypisać do każdego klasa złożoności teoria logiczna , gdzie provably całkowite funkcje w są dokładnie takie funkcje w klasie złożoność . Jednym z najnowszych osiągnięć jest nowy program badawczy zwany „ograniczoną matematyką odwrotną” zaproponowany przez Stephena Cooka i Phuonga Nguyena, którego celem jest klasyfikacja twierdzeń (interesujących się informatyką) w oparciu o (minimalną) złożoność obliczeniową pojęć potrzebnych do ich udowodnienia. .V C V C $C$$VC$$VC$$C$

Aspekty (i) i (ii) są ściśle powiązane z pojęciem tłumaczenia zdań zaproponowanym w artykule Cooka z 1975 r. , Który wprowadził teorię równań dla funkcji czasu i pokazał, w jaki sposób można przełożyć twierdzenia z na rodziny tautologii, które mają wielomianowe proofy długości w rozszerzonym systemie Frege proof.P $\mathsf{PV}$$\mathsf{PV}$

Aby uzyskać doskonałe ankiety dotyczące złożoności dowodów, polecam następujące dwie książki:

• Stephen Cook i Phuong Nguyen, Logiczne podstawy dowodu złożoności . (projekt udostępniony tutaj )
• Jan Krajíček, Arytmetyka ograniczona, logika zdań i teoria złożoności .

Książka Cooka i Nguyena jest zasadniczo samowystarczalna, a całe niezbędne tło logiczne podano w rozdziałach 2 i 3. Rozdział 9 jest szczególnie interesujący, ponieważ autorzy wprowadzili niezwykle łatwą metodę definiowania własnej teorii dla dowolnych klas złożoności w . W tej metodzie musimy tylko dodać jeden dodatkowy aksjomat do podstawowej teorii , gdzie aksjomat po prostu stwierdza istnienie rozwiązania pełnego problemu klasy złożoności. Całkiem niesamowite!V $\mathsf{P}$$V_0$

Książka Krajíčka jest nieco trudniejsza, ponieważ założył, że czytelnicy znają już logikę matematyczną i teorię modeli (lub chętnie zapoznają się z niezbędnym tłem po drodze). Ale wiele się nauczysz czytając i rozumiejąc tę ​​książkę.

Algorytmy losowe:

Prawdopodobieństwo i obliczenia: randomizowane algorytmy i analiza probabilistyczna autorstwa Michaela Mitzenmachera i Eli Upfala.

Świetna książka do wyjaśnienia podstaw algorytmów losowych. Przykłady i dowody są wyjaśnione bardzo jasno i są łatwe do naśladowania. Ćwiczenia są również bardzo fajne.

(odpowiedział Marcos Villagra)

Analiza losowych algorytmów:

Każdy pracujący w algorytmach powinien mieć Koncentracja miary do analizy algorytmów randomizowanych , który jest również dostępny do pobrania w formacie PDF tutaj .

Kryptografia:

Dwotomowa książka „ Podstawy kryptografii” Odeda Goldreicha ( tom 1: podstawowe narzędzia i tom 2: podstawowe aplikacje ) to doskonała książka na ten temat. (Wczesne wersje dostępne na stronie głównej autora ). Dostępna jest również skrócona wersja tej książki.

Kolejną doskonałą książką jest Wprowadzenie do współczesnej kryptografii: zasady i protokoły autorstwa Katza i Lindella.

Dla osób zainteresowanych matematycznym zapleczem kryptografii An Introduction to Mathematical Cryptography autorstwa Hoffsteina i in. jest naturalnym wyborem.

Inne doskonałe książki to:

• Handbook of Applied Cryptography autorstwa Menezes i in. (Rozdział jest dostępny online ).
• Kryptografia: teoria i praktyka Stinsona.

Tematy szczegółowe:

• Książki dotyczące zaawansowanego składu protokołów bezpieczeństwa:
  • Skład bezpiecznych protokołów wielostronnych: kompleksowe badanie przeprowadzone przez Lindell.
  • Jednoczesna wiedza zerowa autorstwa Rosen.
• Formalne dowody w protokołach bezpieczeństwa
  • Formalna poprawność protokołów bezpieczeństwa autorstwa Belli.
• [Matematyka kryptografii klucza publicznego] ( http://www.amazon.com/Mathematics-Public-Cryptography-Steven-Galbraith/dp/1107013925 ) autor: Galbraith

Programowanie funkcjonalne

• Czysto funkcjonalne struktury danych autorstwa Chrisa Okasaki . Większość książek o strukturach danych zakłada imperatywny język, taki jak C lub C ++. Jednak struktury danych dla tych języków nie zawsze dobrze tłumaczą się na języki funkcjonalne. Ta książka jest jedną z najlepszych prezentacji na temat implementacji struktur danych i algorytmów w funkcjonalnym języku.
• Programowanie funkcyjne: Praktyka i Teoria przez Bruce J. MacLennan . Pomimo swojej nazwy, ta książka jest bardziej zorientowana na teorię niż na praktykę. Ci, którzy czytają tę książkę, będą mieli znacznie lepszy pogląd na ten temat niż ci, którzy uczą się go poprzez programowanie ad hoc.
• Perły projektowania algorytmu funkcjonalnego autorstwa Richarda Birda . Zupełnie nowa ekspozycja na ten temat, która przyjmuje podejście oparte na rozwiązywaniu problemów i pokazuje piękno tej dziedziny, prezentując atrakcyjne pomysły w projektowaniu algorytmów funkcjonalnych.
• Certyfikowane programowanie z typami zależnymi od Adama Chlipali . Jest to jeden z najlepszych zasobów do nauki języka Coq i koncentruje się w szczególności na automatyzacji certyfikacji programów i dowodzenia twierdzeń przy użyciu systemów opartych na logice / regułach. Przykłady są obszerne i łatwe do naśladowania.

Algorytmy aproksymacyjne

Książka Algorytmy aproksymacyjne autorstwa Vazirani jest najlepszą książką na ten temat. Inną książką są Algorytmy aproksymacji problemów trudnych dla NP autorstwa Hochbauma.

Oto porównania dwóch recenzentów:

Wykorzystałem książkę Dorit Hochbaum na temat algorytmów aproksymacyjnych dla problemów NP-Hard jako wytyczne dla mojej pracy. Książka Hochbauma jest bez wątpienia wspaniała. Jednak format ankiety zagroził płynnemu przepływowi na rzecz zgromadzenia najlepszych ludzi w terenie. Książka Vazirani rozwiązuje ten problem, zachowując gładkość i elegancję od początku do końca. Doskonałe zestawy problemów, doskonałe wskazówki dla większości problemów, a na końcu książki znajduje się sekcja poświęcona otwartym problemom, co jest naprawdę fajną funkcją.

i

Szukałem książek związanych z rozwiązywaniem problemów NP-zupełnych i NP-trudnych. Jest jeszcze jedna książka Hochbauma i ja też ją mam. Niestety, ta książka jest bardziej książką zorientowaną na badania, ponieważ została napisana przez kilku badaczy. To jak czytanie kilku artykułów naukowych w dwóch twardych okładkach. Oznacza to, że trzeba mieć pewien poziom doświadczenia z algorytmami aproksymacyjnymi.

Najnowsza książka to Projektowanie algorytmów aproksymacyjnych autorstwa Williamsona i Shmoysa.

Kombinatoryka

Książki wprowadzające. Każda z poniższych książek może stanowić doskonałe wprowadzenie do tematu:

• Podręcznik matematyki dyskretnej i kombinatorycznej autorstwa Rosen.
• Matematyka dyskretna i kombinatoryczna: wprowadzenie stosowane przez Grimaldi. Zobacz także instrukcję rozwiązania .
• Spacer przez kombinatorykę i wprowadzenie do kombinatoryki wyliczeniowej i wprowadzenie do kombinatoryki wyliczeniowej autorstwa Bona. Pierwsza książka jest bardziej kompleksowa i klasyczna. Druga książka w znacznym stopniu pokrywa się z pierwszą, ale nacisk kładzie się bardziej na nowoczesne metody liczenia.
• Kurs kombinatoryki van Linta i Wilsona.
• Kombinatoryka: tematy, techniki, algorytmy Camerona. (Ta książka zawiera wiele fajnych ćwiczeń).
• Problemy kombinatoryczne i ćwiczenia László Lovásza (odpowiedział @Sazzad)

Bardziej zaawansowane teksty.

• Enumerative Combinatorics, Tom 1 i Tom 2 autorstwa Stanleya. Jest to po prostu arcydzieło na kombinatoryki wyliczeniowej; bardzo trudne, bardzo głębokie.
• Algorytmy kombinatoryczne: generowanie, wyliczanie i wyszukiwanie według Krehera i Stinsona. Bardziej nadaje się do zastosowań kombinatoryki w informatyce.
• Additive Combinatorics autorstwa Terence Tao i Van H. Vu. Bardzo przydatne odniesienie w obliczu problemu kombinatorycznego związanego z teorią liczb.

Kombinatoryka

Chcę zacytować Analytic Combinatorics , autor: Philippe Flajolet i Robert Sedgewick. Zapewnia silne zaplecze matematyczne do wyliczania i analizy algorytmów. Chcę również złożyć hołd Philippe Flajoletowi, który zmarł dwa dni temu i był wielkim matematykiem i informatykiem.

Weryfikacja programu

• Matematyczna teoria obliczeń Zohara Manny
• Zasady kontroli modeli autorstwa Christela Baiera i Joost-Pieter Katoen
• Model Checking : Edmund M. Clarke Jr., Orna Grumberg i Doron A. Peled
• Weryfikacja programów sekwencyjnych i współbieżnych przez Krzysztofa R. Apt, Franka S. de Boera i Ernsta-Rüdigera Olderoga
• Logika w informatyce: modelowanie i rozumowanie systemów przez M. Hutha i M. Ryana

Teoria informacji

Teoria informacji, wnioskowanie i algorytmy uczenia się David MacKay

Inne znane podręczniki z teorii informacji można znaleźć na Wikipedii .

Algorytmy rozproszone

Rozproszone algorytmy Nancy Lynch Jest to klasyczny tekst napisany przez pioniera przetwarzania rozproszonego;

Wprowadzenie do algorytmów rozproszonych autorstwa Gerarda Tel. Bardzo dobre wprowadzenie, odpowiednie również na studiach licencjackich; koncentruje się na modelu przekazywania wiadomości

Przetwarzanie rozproszone: podstawy, symulacje i zaawansowane tematy autorstwa Hagit Attiya i Jennifer Welch Zawiera zaawansowane materiały, odpowiednie na kursy doktoranckie; omówiono modele przekazywania wiadomości i pamięci współużytkowanej

Projektowanie i analiza algorytmów rozproszonych Autor: Nicola Santoro Książka stosunkowo niedawna, może być stosowana zarówno na poziomie licencjackim, jak i doktorskim; materiały są prezentowane z naciskiem na projekt protokołu

Obliczenia kwantowe

• Obliczanie i Quantum Quantum Information przez Nielsen i Chuang , jest doskonałym odniesienie książka, idealny dla tych, którzy chcą do badań w tej dziedzinie. Jednak na początek trudno jest się uczyć i zdecydowanie nie jest to dla osób uczących się samodzielnie. Ponieważ w książce brakuje przykładów, sugeruję następującą książkę:

  • Problemy i Rozwiązania Quantum Computing & Quantum Information by Steeb & Hardy . Ta książka zawiera wiele przykładów, ale nie jest jeszcze dla absolutnego początkującego. Na początek sugerowana jest następująca książka:

    • Zbliżając Quantum Computing przez Marinescu & Marinescu . Choć elementarne i łatwe do nauczenia, niektórzy uważają, że jest „pełen błędów”. Pod tym względem przydatna jest errata książki .

• Obliczenia kwantowe od czasów Demokryta , Scott Aaronson . Tour-de-force o wiele więcej niż informatyka kwantowa, powiązana z fizyką, filozofią itp.

Dwie inne doskonałe książki wprowadzające na ten temat to:

• Quantum Computing dla informatyków przez Yanofsky & Mannucci .
• Wprowadzenie do obliczeń kwantowych autorstwa Kaye, Laflamme i Mosca .

Optymalizacja

Podobał mi się film Paula Nahina When Least is Best.

Zasadniczo urocza historia optymalizacji poprzez problemy i osobowości. Jest ładna recenzja na stronach 32-36 w jednej z kolumn Billa Gasarcha.

$e^{i\pi} = -1$

Złożoność komunikacji:

To klasyczna i bardzo dobrze napisana książka. Chociaż jest już trochę stary, to wciąż najlepsza książka wprowadzająca do tej dziedziny. Ponadto ćwiczenia są niezwykle zabawne i są wykonywane dokładnie po wyjaśnieniu pojęć, aby można było naprawić to, czego się nauczyłeś.

Część losowej złożoności komunikacji należy uzupełnić fragmentami pierwszej książki.

Złożoność komunikacji i obliczenia równoległe Juraj Hromkovič.

Bardzo kompletny, choć czasem trochę trudny do odczytania. Intuicyjne wyjaśnienia są bardzo jasne i bardzo przyjemne. W drugiej części przedstawiono połączenia z obliczeniami równoległymi.

• Książki Matousek & Chazelle o Discrepancy są doskonałe.

  Prawie wszystkie książki Matouseka są do pewnego stopnia warte przeczytania.

• Książki Douglasa Westa na temat teorii grafów ( [1] i [2] ) są dobre.

• Alon & Spencer jest również doskonały.
• Pach i Agarwal są dobre dla dyskretnej geometrii, podobnie jak Sharir i Agarwal, jeśli lubisz sekwencje DS.
• Bardzo dobra jest także książka Brassa, Mosera i Pacha na temat otwartych problemów w dyskretnej geometrii.
• Vanderbei książka na LP jest bardzo dobra.
• Książki Schrijvera ( [1] i [2] ) są niesamowite.

Algebra obliczeniowa

Jak powiedział Shiva w tej odpowiedzi , literatura w tej dziedzinie jest rozproszona po całym świecie, bez wspólnych terminologii. Przydatne odniesienia można znaleźć, szukając „obliczeń symbolicznych”, „teorii złożoności algebraicznej”, „algebry komputerowej” lub „algebry obliczeniowej”. Jak sugerowano w odpowiedziach na to pytanie ,

• Współczesna algebra komputerowa Joachima von zura Gathena i Jürgena Gerharda.
• Teoria złożoności algebraicznej autorstwa Petera Bürgissera, Michaela Clausena, Mohammada A. Shokrollahi i T. Lickteiga.
• Algebra algorytmiczna autorstwa Bhubaneswar Mishra.
• Komputerowe wprowadzenie do teorii liczb i algebry autorstwa Victora Shoupa.

Analiza obliczeniowa

Interesujące jest także pole, które zajmuje się obliczeniami rzeczywistych funkcji. Znany również jako „analiza obliczalna” lub „rachunek obliczeniowy”.

• Analiza obliczeniowa Olivera Abertha.
• Analiza obliczeniowa: wprowadzenie Klausa Weihraucha.

Kombinatoryka

generowanie funkcji autorstwa Herberta S. Wilfa jest doskonałym wprowadzeniem do teorii funkcji generowania, napisanym płynnie i wypełnionym ćwiczeniami. Jeśli napisze wszystkie swoje książki w ten sposób, nie mogę się doczekać, aż zacznę pisać inną.

Enumerative Combinatorics autorstwa Richarda Stanleya jest świetnym odniesieniem (zaawansowane).

Kombinatoryka: tematy, techniki, algorytmy Petera Camerona i Zaproszenie do dyskretnej matematyki Matouseka i Nesetrila stanowią doskonałe wprowadzenie do kombinatoryki.

Applied Combinatorics autorstwa Robertsa i Tesmana to encyklopedyczne odniesienie do stosowanej kombinatoryki.

Logika:

To jest dosłownie moja odpowiedź na to pytanie .

Znajomość podstawowej logiki matematycznej jest moim zdaniem plusem. Możesz rzucić okiem na dwie książki Cori i Lascara.

Logika matematyczna: kurs z ćwiczeniami Część I

Logika matematyczna: kurs z ćwiczeniami Część II

Pisanie logiki / dowodu:

1. Jak to udowodnić: podejście strukturalne Daniela J. Vellemana

Teoria liczb

Znalazłem kilka książek często cytowanych w wielu artykułach. Są doskonałe w tym temacie, ale niektóre z nich są dość stare. Oto lista tego, co pamiętam:

• Wprowadzenie do teorii liczb Hardy i in. Hardy to znany brytyjski matematyk. Był mentorem indyjskiego matematyka Ramanujana . Jego wkład w dziedzinę teorii liczb jest niesamowity .
• Wprowadzenie do teorii liczb Niven, Zuckerman, Montgomery. Kolejne klasyczne wprowadzenie do tej dziedziny.
• Rozwiązane i nierozwiązane problemy teorii liczb według Shanksa. To książka dla tych, którzy szukają jeszcze-do-sprawdzone przypuszczenia w tej dziedzinie.
• Funkcja Zeta Riemanna autorstwa Edwardsa. Ważna część współczesnej teorii liczb, a także kilka algorytmów probabilistycznych dla zadań teoretycznych, opiera się na (rozszerzonej) hipotezie Riemanna, jak opisano w tej książce.

Hypergraphs

Niewiele jest książek poświęconych wyłącznie hipergraphom. Jedną z takich książek jest

Berge C. Hypergraphs: kombinatoryka zbiorów skończonych .

Teoria dowodowa

Książka Troelstry i Schwichtenberga Podstawowa teoria dowodów jest de facto tekstem na ten temat.

Girard, Taylor & LaFont's Proofs and Types to krótsza książka na ten temat, a jej wersja jest dostępna do pobrania pod adresem http://www.paultaylor.eu/stable/Proofs%2BTypes.html

Teoria grafów

Wprowadzenie do teorii grafów: Wprowadzenie do teorii grafów autorstwa Westa

Więcej informacji na temat teorii grafów: teoria grafów Bondy i Murty

Obszerna książka zawierająca nowe osiągnięcia, a także stare klasyczne wyniki w teorii grafów:

Teoria grafów: Reinhard Diestel .

W przypadku wykresów na powierzchniach z podejściem kombinatorycznym:

Wykresy na powierzchniach

A w przypadku digrafów:

Digraphs: Teoria, algorytmy i zastosowania

Projekt VLSI

Nie interesuje mnie sprzęt. Ponieważ jednak FAQ zawiera VLSI jako jedno z podrozdziałów TCS, zapytałem eksperta o znane książki z projektu VLSI. Tutaj są:

• Cyfrowe układy scalone
• Konstrukcja CMOS VLSI: perspektywa obwodów i systemów
• Nowoczesne wzornictwo VLSI: wzornictwo oparte na IP