Her er en liste over viktige publikasjoner innen teoretisk informatikk , organisert etter felt.
Noen grunner til at et innlegg kan betraktes som viktig:
Beskrivelse: dette dokumentet presenterer treautomaten , en utvidelse av automaten . treautomaten har hatt mange applikasjoner i formell verifisering .
Beskrivelse: Denne artikkelen setter grensene for databehandling. Han definerte Turing-maskinen , en modell for alle beregninger. På den annen side beviste han at det var ubesluttsomt med dommen og Entscheidungsproblemet, og fant dermed mulige grenser for beregningen.
Beskrivelse: Den matematiske behandlingen av automatene , beviset på grunnleggende egenskaper og definisjonen av ikke-deterministisk endelig automat .
Beskrivelse: Denne artikkelen introduserer det som nå kalles Chomsky- hierarkiet , et hierarki av formelle grammatikklasser som genererer formelle språk .
Beskrivelse: En populær lærebok.
"Et bestemt forsøk med [Arora og Barak] å ta med oppdatert materiale, mens Goldreich fokuserer mer på å utvikle et kontekstuelt og historisk grunnlag for hvert konsept som presenteres," og han "applauderer alle ... forfattere for deres eksepsjonelle bidrag. ”
Beskrivelse: Aksiomene til Blum .
Beskrivelse: Dette dokumentet har vist at PH er inneholdt i IP .
Beskrivelse: Denne artikkelen introduserer begrepet NP-komplett problem og beviste at SAT-problemet er NP-komplett . Merk at lignende ideer ble utviklet uavhengig litt senere av Leonid Levin .
Beskrivelse: Hovedinteressen til denne boka skyldes den lange listen over over 300 NP-komplette problemer . Denne listen har blitt en vanlig referanse og definisjon.
Beskrivelse: Denne tekniske rapporten var den første publikasjonen som diskuterte hva som senere ble omdøpt til Complexity Theory ? '' 'UNIQ - nowiki-00000006-QINU' ''? 2 ? '"` UNIQ - nowiki-00000007-QINU` "'? ..
Beskrivelse: Konstruksjon av "Klee-Minty-kuben" i dimensjonen D , 2 D hjørner er studert av simpleksalgoritmen til Danzig for lineær optimalisering .
Beskrivelse: Dette dokumentet viser at eksistensen av en enveisfunksjon fører til beregnings tilfeldighet.
Beskrivelse: IP er en kompleksitetsklasse hvis karakterisering (basert på interaktive proof-systemer ) er ganske forskjellig fra beregningsklasser. I denne artikkelen utvidet Shamir teknikken til forrige artikkel av Lund, et al. , For å vise at PSPACE er inneholdt i IP, og derfor IP = PSPACE, for å sikre at hvert problem i en kompleksitetsklasse er løst i det andre.
Beskrivelse: Dette dokumentet har vist at 21 forskjellige problemer er NP-komplette og har vist viktigheten av dette konseptet.
Beskrivelse: Dette dokumentet introduserer begrepet null kunnskap .
Beskrivelse: Gödel diskuterer ideen om effektivitet i den universelle setningen.
Beskrivelse: Dette dokumentet ga beregningskompleksitet navn og frø.
Beskrivelse: Denne artikkelen har laget et teoretisk rammeverk for trapdoorfunksjoner og beskriver noen av deres applikasjoner, for eksempel i kryptografi . Vær oppmerksom på at konseptet med dørfunksjoner ble brakt til "Nye veiledninger i kryptografi" for seks år siden (se avsnitt V " Problemforhold og felle dører .").
Beskrivelse: En introduksjon til teorien om beregningskompleksitet, forklarer boken karakteriseringen av P-SPACE og andre resultater.
Beskrivelse: Disse tre dokumentene viser det overraskende faktum at noen NP-problemer fortsatt er vanskelige, selv når det bare er behov for en grov løsning. Se PCP-teoremet .
Beskrivelse: DPLL-algoritmen . Den grunnleggende algoritmen for SAT og andre NP-komplette problemer .
Beskrivelse: Første beskrivelse av oppløsningen og foreningen som brukes i det automatiske beviset på setninger ; brukt i Prolog .
Beskrivelse: Bruk av en algoritme med et minimumspennende tre som en tilnærmelsesalgoritme for NP-komplett problem med den reisende selgeren . Tilnærmelsesalgoritmer har blitt en vanlig metode for å håndtere NP-komplette problemer.
Beskrivelse: Dokumentet presenterer Miller-Rabin primality test og beskriver det sannsynlige algoritmeprogrammet .
Beskrivelse: Denne artikkelen beskriver simulert annealing som nå er en veldig vanlig heuristikk for NP-komplette problemer .
Beskrivelse: Denne monografien har tre populære algoritmebøker og et antall hefter . Algoritmene er skrevet på engelsk og på MIX- språk . Dette gjør algoritmene både forståelige og presise. Ved å bruke et programmeringsspråk på lavt nivå frustrerer imidlertid noen programmerere som er mer kjent med moderne strukturerte programmeringsspråk .
Beskrivelse: En bok påvirker algoritmer og datastrukturer.
Beskrivelse: En av referansetekstene om algoritmer i perioden 1975-1985.
Beskrivelse: Forklaring av hvorfor algoritmer og datastrukturer. Forklaring til skapelsesprosessen , argumentasjonslinjen og designfaktorene bak innovative løsninger.
Beskrivelse: En veldig populær tekst om algoritmer på slutten av 1980-tallet.
Beskrivelse: Denne håndboken har blitt så populær at den nesten er standarden for undervisning i grunnleggende algoritmer. Den 1 st utgaven ble utgitt i 1990, to th utgave i 2001, og tre e i 2009.
Beskrivelse: Prosjekt av en sannsynlighetsberegningstilnærming.
Beskrivelse: Dette var starten på Kolmogorovs algoritmiske teori om informasjon og kompleksitet . Merk at mens Kolmogorov-kompleksitet er oppkalt etter Andrey Kolmogorov , går ideen til Ray Solomonoff . Andrey Kolmogorov bidro mye på dette området, men med påfølgende artikler.
Beskrivelse: En introduksjon til algoritmisk informasjonsteori av en av de viktige personene i dette feltet.
Beskrivelse: Dette dokumentet opprettet felt for informasjonsteori .
Beskrivelse: I denne artikkelen introduserte Hamming ideen om en feilrettingskode . Han opprettet Hamming-koden og Hamming-avstanden .
Beskrivelse: Huffmans koding .
Beskrivelse: LZ77- komprimeringsalgoritmen .
Beskrivelse: En populær introduksjon til informasjonsteori.
Beskrivelse: Tony Hoares artikkel beskriver et sett av regler for slutning (dvs. formell bevis) for et programmeringsspråk som Algol .
Beskrivelse: Dette dokumentet foreslår at programmer og deres formelle bevis skal utvikles hånd i hånd, i stedet for å formelt verifisere et program etter at det er skrevet (dvs. post facto), en metode kjent som navneforbedring (eller avledning) av programmet.
Beskrivelse: Denne artikkelen presenterte bevisene for uforanderlighet i samtidige programmer.
Beskrivelse: I dette dokumentet presenteres den parallelle aksiomatiske tilnærmingen til programverifisering.
Beskrivelse: Første bok om den matematiske (eller funksjonelle) tilnærmingen til den formelle semantikken til programmeringsspråk (i motsetning til operasjonelle og algebraiske tilnærminger).
Beskrivelse: Bruk av tidslogikk er blitt foreslått som en formell verifiseringsmetode.
Beskrivelse: Verifiseringsmodellen ble presentert som en prosedyre for å verifisere nøyaktigheten til samtidige programmer.
Beskrivelse: Dette dokumentet viser hvordan du bygger programmer som fungerer som de skal (uten feil, bortsett fra skrivefeil).
Beskrivelse: Denne boken er for tiden den tredje mest siterte referansen innen databehandling.
Beskrivelse: Girards lineære logikk var et gjennombrudd i typesystemdesign for sekvensiell og samtidig beregning .
Beskrivelse: dette dokumentet introduserte Pi-Calculus , en generalisering av CCS. Beregning er ekstremt enkel og har blitt det dominerende paradigmet i den teoretiske studien av programmeringsspråk, typesystemer og programlogikk.
Beskrivelse: En referansehåndbok som oppsummerer den formelle Z-notasjonen .
Beskrivelse: Den oppdaterte versjonen av prediktiv programmering . Basen til CAR Hoares UTP . De enkleste og mest komplette formelle metodene.