Seznam důležitých publikací v teoretické informatice - List of important publications in theoretical computer science

Toto je seznam důležitých publikací v teoretické informatice , organizovaných podle oblastí.

Některé důvody, proč lze určitou publikaci považovat za důležitou:

  • Autor tématu - Publikace, která vytvořila nové téma
  • Průlom - Publikace, která významně změnila vědecké znalosti
  • Vliv - Publikace, která významně ovlivnila svět nebo měla obrovský dopad na výuku teoretické informatiky.

Vyčíslitelnost

Cutlandova vypočítatelnost: Úvod do teorie rekurzivních funkcí (Cambridge)

  • Cutland, Nigel J. (1980). Vypočítatelnost: Úvod do teorie rekurzivních funkcí . Cambridge University Press . ISBN 978-0-521-29465-2.

Recenze tohoto raného textu Carla Smitha z Purdue University (ve Společnosti pro průmyslovou a aplikovanou matematickou recenzi ) uvádí, že jde o text s „vhodnou kombinací intuice a důslednosti… ve výkladu důkazů“, který představuje „základní výsledky klasické teorie rekurze [RT] ... ve stylu ... přístupném vysokoškolákům s minimálním matematickým pozadím ". I když prohlašuje, že „by byl vynikajícím úvodním textem pro úvodní kurz [RT] pro studenty matematiky“, navrhuje, že „instruktor musí být připraven podstatně rozšířit materiál…“, pokud je používán se studenty počítačových věd ( vzhledem k nedostatku materiálu o RT aplikacích v této oblasti).

Rozhodnutelnost teorií druhého řádu a automatů na nekonečných stromech

Popis: Příspěvek představil stromový automat , rozšíření automatů . Stromový automat měl četné aplikace k prokázání správnosti programů .

Konečné automaty a jejich rozhodovací problémy

Popis: Matematické zpracování automatů , důkaz základních vlastností a definice nedeterministického konečného automatu .

Úvod do teorie automatů, jazyků a výpočtu

Popis: Populární učebnice.

O určitých formálních vlastnostech gramatik

Popis: Tento článek představil takzvanou Chomského hierarchii , hierarchii omezení tříd formálních gramatik, které generují formální jazyky .

Na vypočítatelných číslech, s aplikací na Entscheidungsproblem

Popis: Tento článek stanoví limity počítačové vědy. Definoval Turingův stroj , model pro všechny výpočty. Na druhou stranu to dokázalo nerozhodnutelnost problému zastavení a Entscheidungsproblem a našlo tak limity možného výpočtu.

Rekurzivní funkce

První učebnice teorie rekurzivních funkcí . Kniha prošla mnoha vydáními a Péterovi vynesla Kossuthovu cenu od maďarské vlády. Recenze Raphaela M. Robinsona a Stephena Kleene ocenili knihu za poskytnutí účinného základního úvodu pro studenty.

Zastoupení událostí v nervových sítích a konečných automatech

Popis: tento článek představil konečné automaty , regulární výrazy a regulární jazyky a navázal jejich spojení.

Teorie výpočetní složitosti

Arora & Barakova výpočetní složitost a Goldreichova výpočetní složitost (oba Cambridge)

  • Sanjeev Arora a Boaz Barak, „Výpočetní složitost: moderní přístup“, Cambridge University Press, 2009, 579 stran, vázaná kniha
  • Oded Goldreich, „Výpočetní složitost: Konceptuální perspektiva, Cambridge University Press, 2008, 606 stran, vázaná kniha

Kromě odhadovatelného tisku, který přináší tyto nedávné texty, jsou velmi pozitivně hodnoceny ve zprávách ACM SIGACT News Danielem Aponem z University of Arkansas, který je identifikuje jako „učebnice pro kurz teorie složitosti, zaměřený na předčasné absolventy… nebo ... pokročilí vysokoškoláci… [s] četnými, jedinečnými silnými stránkami a velmi málo slabostmi, “a uvádí, že oba jsou:

„vynikající texty, které důkladně pokrývají jak šíři, tak hloubku teorie výpočetní složitosti ... [od] autorů ... každý [kteří] jsou obry v teorii výpočetní techniky [kde každý bude] ... výjimečný referenční text pro odborníky v pole… [a to] ... teoretikům, vědcům a instruktorům jakékoli myšlenkové školy bude každá kniha užitečná. “

Recenzent konstatuje, že v [Arora a Barak] existuje určitý pokus zahrnout velmi aktuální materiál, zatímco Goldreich se více zaměřuje na rozvoj kontextuálního a historického základu pro každý představený koncept, “a že„ tleská [s ] všichni… autoři za vynikající příspěvky. “

Strojově nezávislá teorie složitosti rekurzivních funkcí

Popis: Blumovy axiomy .

Algebraické metody pro interaktivní kontrolní systémy

Popis: Tento dokument ukázal, že PH je obsažen v IP .

Složitost postupů prokazování věty

Popis: Tento článek představil koncept NP-úplnosti a prokázal, že problém s booleovskou uspokojivostí (SAT) je NP-Complete . Všimněte si, že podobné myšlenky vyvinul nezávisle o něco později Leonid Levin na „Levin, Problémy univerzálního vyhledávání. Problemy Peredachi Informatsii 9 (3): 265–266, 1973“.

Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti

Popis: Hlavní význam této knihy je způsoben jejím rozsáhlým seznamem více než 300 problémů NP-Complete . Tento seznam se stal běžným odkazem a definicí. Ačkoli kniha vyšla jen několik let po definici konceptu, byl nalezen tak rozsáhlý seznam.

Stupeň obtížnosti výpočtu funkce a částečné uspořádání rekurzivních množin

Popis: Tato technická zpráva byla první publikací, která hovořila o tom, co bylo později přejmenováno na výpočetní složitost

Jak dobrá je simplexní metoda?

  • Victor Klee a George J. Minty
  • Klee, Victor ; Minty, George J. (1972). "Jak dobrý je simplexní algoritmus?". V Shisha, Oved (ed.). Nerovnosti III (Sborník ze třetího sympozia o nerovnostech konaného na Kalifornské univerzitě v Los Angeles v Kalifornii od 1. do 9. září 1969 věnovaný památce Theodora S. Motzkina) . New York-Londýn: Academic Press. str. 159–175. MR  0332165 .

Popis: Vyrobeno v „Klee-mátový krychle“ o rozměrech  D , jehož 2 D rohy jsou vzájemně navštěvují Dantzig ‚s simplex algoritmu pro lineární optimalizaci .

Jak postavit náhodné funkce

Popis: Tento článek ukázal, že existence jednosměrných funkcí vede k výpočetní náhodnosti .

IP = PSPACE

Popis: IP je třída složitosti, jejíž charakterizace (založená na interaktivních důkazních systémech ) se zcela liší od obvyklých výpočetních tříd ohraničených časem a prostorem. V tomto článku Shamir rozšířil techniku ​​předchozí práce Lunda et al., Aby ukázal, že PSPACE je obsažen v IP , a tedy IP = PSPACE, takže každý problém v jedné třídě složitosti je řešitelný v druhé.

Redukovatelnost mezi kombinatorickými problémy

  • RM Karp
  • V publikaci RE Miller a JW Thatcher, editors, Complexity of Computer Computations , Plenum Press, New York, NY, 1972, str. 85–103

Popis: Tento příspěvek ukázal, že 21 různých problémů je NP-Complete a ukázal důležitost konceptu.

Znalostní složitost systémů interaktivních důkazů

Popis: Tento příspěvek představil koncept nulových znalostí .

Dopis od Gödela von Neumannovi

Popis: Gödel pojednává o myšlence účinného univerzálního testeru vět.

O výpočetní složitosti algoritmů

Popis: Tento příspěvek dal výpočetní složitosti své jméno a semeno.

Cesty, stromy a květiny

Popis: Existuje polynomiální časový algoritmus k nalezení maximální shody v grafu, který není bipartitní, a další krok k myšlence výpočetní složitosti . Více informací viz [2] .

Teorie a aplikace funkcí padacích dveří

Popis: Tento příspěvek vytváří teoretický rámec pro funkce padacích dveří a popisuje některé jejich aplikace, například v kryptografii . Všimněte si, že koncept funkcí padacích dveří byl přinesen v „Nových směrech v kryptografii“ o šest let dříve (viz část V „Problémové vzájemné vztahy a trapové dveře.“).

Výpočetní složitost

Popis: V úvodu do teorie výpočetní složitosti kniha vysvětluje autorovu charakteristiku P-SPACE a další výsledky.

Interaktivní důkazy a tvrdost přibližných klik

Pravděpodobnostní kontrola důkazů: nová charakteristika NP

Důkazové ověření a tvrdost problémů aproximace

Popis: Tyto tři práce prokázaly překvapivou skutečnost, že určité problémy v NP zůstávají těžké, i když je vyžadováno pouze přibližné řešení. Viz teorém PCP .

Vnitřní výpočetní obtížnost funkcí

Popis: První definice třídy složitosti P. Jeden ze základních článků teorie složitosti.

Algoritmy

„Strojový program pro dokazování věty“

Popis: Algoritmus DPLL . Základní algoritmus pro SAT a další NP-Complete problémy.

„Strojově orientovaná logika založená na principu rozlišení“

Popis: První popis rozlišení a unifikace použitých při automatizovaném dokazování vět ; používá se v Prologu a logickém programování .

„Problém obchodního cestujícího a minimální kostry“

Popis: Použití algoritmu pro minimální kostru jako aproximačního algoritmu pro problém obchodního cestujícího NP-Complete . Aproximační algoritmy se staly běžnou metodou pro řešení problémů NP-Complete.

"Polynomiální algoritmus v lineárním programování"

Popis: Dlouho neexistoval prokazatelně polynomiální časový algoritmus pro problém lineárního programování . Khachiyan byl první, kdo poskytl algoritmus, který byl polynomiální (a nejen že byl dostatečně rychlý po většinu času jako předchozí algoritmy). Později Narendra Karmarkar představil rychlejší algoritmus na adrese: Narendra Karmarkar, „Nový polynomiální časový algoritmus pro lineární programování“, Combinatorica , svazek 4, č. 4. 4, s. 373–395, 1984.

"Pravděpodobnostní algoritmus pro testování primality"

Popis: Příspěvek představil Miller-Rabinův test primality a nastínil program randomizovaných algoritmů .

„Optimalizace simulovaným žíháním“

Popis: Tento článek popisuje simulované žíhání , které je nyní velmi běžnou heuristikou problémů NP-Complete .

Umění počítačového programování

Popis: Tato monografie má čtyři svazky pokrývající populární algoritmy. Algoritmy jsou psány jak v angličtině, tak v montážním jazyce MIX (nebo montážním jazyce MMIX v novějších svazcích). Díky tomu jsou algoritmy srozumitelné a přesné. Použití nízkoúrovňového programovacího jazyka však frustruje některé programátory, kteří jsou více obeznámeni s moderními strukturovanými programovacími jazyky .

Algoritmy + datové struktury = programy

Popis: Raná, vlivná kniha o algoritmech a datových strukturách s implementacemi v Pascalu.

Návrh a analýza počítačových algoritmů

Popis: Jeden ze standardních textů o algoritmech pro období přibližně 1975–1985.

Jak to vyřešit počítačem

Popis: Vysvětluje Proč s algoritmů a datových struktur. Vysvětluje tvůrčí proces , linii uvažování , faktory designu za inovativními řešeními.

Algoritmy

Popis: Velmi populární text o algoritmech na konci 80. let. Bylo přístupnější a čitelnější (ale elementárnější) než Aho, Hopcroft a Ullman. Existuje novějších vydání.

Úvod do algoritmů

Popis: Tato učebnice se stala tak populární, že je téměř de facto standardem pro výuku základních algoritmů. První vydání (s prvními třemi autory) vyšlo v roce 1990, druhé vydání v roce 2001 a třetí v roce 2009.

Algoritmická teorie informací

„Na tabulkách náhodných čísel“

Popis: Navrhl výpočetní a kombinatorický přístup k pravděpodobnosti.

„Formální teorie indukční inference“

Popis: To byl začátek algoritmické teorie informací a Kolmogorovovy složitosti . Všimněte si, že ačkoli Kolmogorovova složitost je pojmenována po Andrey Kolmogorovovi , řekl, že zárodky této myšlenky jsou způsobeny Rayem Solomonoffem . Andrey Kolmogorov do této oblasti hodně přispěl, ale v dalších článcích.

"Algoritmická teorie informací"

Popis: Úvod do algoritmické teorie informací jedním z důležitých osob v této oblasti.

Informační teorie

„Matematická teorie komunikace“

Popis: Tento příspěvek vytvořil pole teorie informací .

„Kódy pro detekci a opravu chyb“

Popis: V tomto příspěvku představil Hamming myšlenku kódu opravujícího chyby . Vytvořil Hammingův kód a Hammingovu vzdálenost a vyvinul metody pro ověření optimality kódu.

„Metoda pro konstrukci kódů minimální redundance“

Popis: Huffmanovo kódování .

"Univerzální algoritmus pro sekvenční kompresi dat"

Popis: Algoritmus komprese LZ77 .

Základy teorie informace

Popis: Populární úvod do teorie informací.

Formální ověření

Přiřazení významu programům

Popis: Mezník Robert Floyd Assigning Meanings to Programmes zavádí metodu indukčních tvrzení a popisuje, jak může být program s poznámkami s tvrzeními prvního řádu zobrazen tak, aby vyhovoval specifikaci před a po podmínce - článek také zavádí pojmy invariantní smyčky a ověřovací podmínka.

Axiomatický základ pro počítačové programování

Popis: Papír Tonyho Hoare Axiomatický základ pro počítačové programování popisuje soubor pravidel pro odvození (tj. Formální důkaz) pro fragmenty programovacího jazyka podobného Algolu popsaného v pojmech (nyní nazývaných) trojic.

Hlídané příkazy, neurčitost a formální odvozování programů

Popis: Papír Edsgera Dijkstra Strážené příkazy, neurčitost a formální odvozování programů (rozšířený o jeho učebnici postgraduálního studia A Disciplína programování z roku 1976) navrhuje, aby místo formálního ověření programu po jeho napsání (tj. Post facto) byly programy a jejich formální důkazy by měly být vyvinuty ruku v ruce (pomocí predikátových transformátorů k postupnému upřesnění nejslabších předpokladů), metoda známá jako programové (nebo formální) zpřesnění (nebo odvození) nebo někdy „správnost podle konstrukce“.

Prokazování tvrzení o paralelních programech

Popis: Článek, který představil důkazy invariance souběžných programů.

Axiomatická důkazní technika pro paralelní programy I

Popis: V tomto příspěvku, spolu se stejnými autorovými příspěvky „Ověření vlastností paralelních programů: Axiomatický přístup. Komun. ACM 19 (5): 279–285 (1976)“, byl představen axiomatický přístup k verifikaci paralelních programů.

Disciplína programování

Popis: Klasická postgraduální učebnice Edsgera Dijkstra A Disciplína programování rozšiřuje jeho dřívější práci Strážené příkazy, neurčitost a formální odvozování programů a pevně zakládá princip formálního odvození programů (a jejich důkazů) z jejich specifikace.

Denotační sémantika

Popis: Denotační sémantika Joe Stoyho je první (postgraduální úroveň) knižní expozicí matematického (nebo funkčního) přístupu k formální sémantice programovacích jazyků (na rozdíl od provozních a algebraických přístupů).

Časová logika programů

Popis: Jako metoda formálního ověření bylo navrženo použití časové logiky .

Charakterizace vlastností správnosti paralelních programů pomocí fixních bodů (1980)

Popis: Kontrola modelu byla zavedena jako postup kontroly správnosti souběžných programů.

Komunikující sekvenční procesy (1978)

Popis: Dokument Tonyho Hoare (původní) komunikující sekvenční procesy (CSP) zavádí myšlenku souběžných procesů (tj. Programů), které nesdílejí proměnné, ale místo toho spolupracují pouze výměnou synchronních zpráv.

Počet komunikačních systémů

Popis: Dokument Robin Milner A Calculus of Communicating Systems (CCS) popisuje procesní algebru umožňující formální zdůvodnění systémů souběžných procesů, něco, co u dřívějších modelů souběžnosti (semafory, kritické sekce, původní CSP) nebylo možné.

Vývoj softwaru: přísný přístup

Popis: Učebnice Cliffa Jonese Vývoj softwaru: Rigorózní přístup je první celovečerní expozicí metody Vienna Development Method (VDM), která se v minulém desetiletí vyvinula (hlavně) ve vídeňské výzkumné laboratoři IBM a kombinuje myšlenku programu upřesnění podle Dijkstra s upřesněním (nebo reifikací) dat, přičemž algebraicky definované abstraktní datové typy jsou formálně transformovány do postupně „konkrétnějších“ reprezentací.

Věda o programování

Popis: Učebnice Davida Griesa The Science of Programming popisuje Dijkstrovu nejslabší předpokladovou metodu odvozování formálního programu, s výjimkou mnohem dostupnějšího způsobu než Dijkstrův dřívější Disciplína programování .

Ukazuje, jak vytvořit programy, které fungují správně (bez chyb, kromě chyb při psaní). Dělá to tím, že ukazuje, jak používat předpokladové a postkondiční predikátové výrazy a techniky dokazování programů jako vodítko při vytváření programů.

Příklady v knize jsou všechny malého rozsahu a jasně akademické (na rozdíl od skutečného světa). Zdůrazňují základní algoritmy, jako je třídění a slučování a manipulace s řetězci. Subrutiny (funkce) jsou zahrnuty, ale objektově orientovaná a funkční programovací prostředí nejsou řešena.

Komunikující sekvenční procesy (1985)

Popis: Učebnice Tonyho Hoareho Communicating Sequential Processes (CSP) (v současné době třetí nejcitovanější reference na počítačové vědy všech dob) představuje aktualizovaný model CSP, ve kterém spolupracující procesy nemají ani programové proměnné a který stejně jako CCS umožňuje systémům procesů být formálně odůvodněn.

Lineární logika (1987)

Popis: Girardova lineární logika byla průlomem v navrhování typovacích systémů pro sekvenční a souběžné výpočty, zejména pro systémy typování založené na zdrojích.

Kalkul mobilních procesů (1989)

Popis: Tento článek představuje Pi-Calculus , zobecnění CCS, které umožňuje mobilitu procesů. Počet je extrémně jednoduchý a stal se dominantním paradigmatem v teoretickém studiu programovacích jazyků, typovacích systémů a programové logiky.

Z notace: Referenční příručka

Popis: Klasická učebnice Mikea Spiveyho The Z Notation: A Reference Manual shrnuje formální specifikační Z notaci , která, přestože ji vytvořil Jean-Raymond Abrial, se v minulém desetiletí vyvinula (hlavně) na Oxfordské univerzitě.

Komunikace a souběžnost

Popis: Učebnice Robina Milnera Komunikace a souběžnost je přístupnější, i když stále technicky vyspělou, expozicí jeho dřívější práce s CCS.

Praktická teorie programování

Popis: aktuální verze Predicative programování . Základ pro UTP společnosti CAR Hoare . Nejjednodušší a nejkomplexnější formální metody.

Reference