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

Tento článek má několik problémů. Prosím pomozte zlepšit to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Seznam důležitých publikací v teoretické informatice"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Února 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek případně obsahuje původní výzkum. Prosím zlepšit to podle ověřování vznesené nároky a přidání vložené citace. Výroky sestávající pouze z původního výzkumu by měly být odstraněny. (Února 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) Tento článek může vyžadovat vyčištění setkat se s Wikipedií standardy kvality. Specifický problém je: seznam prezentuje položku za položkou bez objektivní publikované podpory, včetně výběru článků z primární literatury nepodporovaných zdrojem, který stanoví jejich důležitost (tedy tvoří WP: NEBO) Prosím pomozte vylepšit tento článek jestli můžeš. (Února 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Toto je seznam důležitých publikací v teoretická informatika, organizované podle oboru.

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

• Tvůrce 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 výrazný dopad na výuku teoretické informatiky.

Vyčíslitelnost

Cutland's 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 (v Recenze společnosti pro průmyslovou a aplikovanou matematiku),^[1] uvádí, že tento text s „vhodnou kombinací intuice a přísnosti ... v expozici 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 tomu, nedostatek materiálu pro RT aplikace do této oblasti).^[1]

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

• Michael O. Rabin
• Transakce Americké matematické společnosti, sv. 141, s. 1–35, 1969

Popis: Příspěvek představil stromový automat, rozšíření automaty. Stromový automat měl na důkazy řadu aplikací správnost programů.

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

• Michael O. Rabin a Dana S. Scott
• IBM Journal of Research and Development, sv. 3, str. 114–125, 1959
• Online verze

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

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

• John E. Hopcroft, Jeffrey D. Ullman, a Rajeev Motwani
• Addison-Wesley, 2001, ISBN  0-201-02988-X

Popis: Populární učebnice.

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

• Chomsky, N. (1959). „O určitých formálních vlastnostech gramatik“. Informace a kontrola. 2 (2): 137–167. doi:10.1016 / S0019-9958 (59) 90362-6.

Popis: Tento článek představil to, co je nyní známé jako Chomského hierarchie, a hierarchie omezení tříd formální gramatiky které generují formální jazyky.

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

• Alan Turing
• Proceedings of the London Mathematical Society, Série 2, sv. 42, s. 230–265, 1937, doi:10.1112 / plms / s2-42.1.230.
  Errata se objevila ve sv. 43, s. 544–546, 1938, doi:10,1112 / plms / s2-43,6,544.
• HTML verze, PDF verze

Popis: Tento článek stanoví limity počítačové vědy. Definovalo to Turingův stroj, model pro všechny výpočty. Na druhé straně to prokázalo nerozhodnutelnost zastavení problému a Entscheidungsproblem a tím našel limity možného výpočtu.

Rekurzivní funkce

• Péter, Rózsa (1951). Rekurzivní funkce. Akademický tisk. ISBN  9780125526500.

První učebnice o teorie rekurzivních funkcí. Kniha prošla mnoha vydáními a získala Péter Kossuthova cena z maďarský vláda.^[2] Recenze od Raphael M. Robinson a Stephen Kleene ocenil knihu za poskytnutí účinného základního úvodu pro studenty.^[3]

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

• S. C. Kleene
• Memorandum o projektu amerického letectva Rand Research Memorandum RM-704, 1951
• Online verze
• publikováno v: Shannon, Claude; McCarthy, Johne, eds. (1956). Studie automatů. OCLC  564148.

Popis: tento článek představen konečné automaty, regulární výrazy, a běžné jazyky a navázali spojení.

Teorie výpočetní složitosti

Arora & Barak's Výpočetní složitost a Goldreichovy 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 nejnovější texty, jsou velmi pozitivně hodnoceny Zprávy ACM SIGACT Daniel Apon z University of Arkansas,^[4] kdo je identifikuje jako „učebnice pro kurz teorie složitosti, zaměřené na začínající absolventy… nebo ... pokročilé vysokoškoláky… [s] četnými, jedinečnými silnými stránkami a velmi málo slabostmi“, a uvádí, že obě 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ýzkumníků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 jejich vynikající příspěvky. “^[4]

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

• Blum, Manuel (1967). „Strojově nezávislá teorie složitosti rekurzivních funkcí“ (PDF). Deník ACM. 14 (2): 322–336. doi:10.1145/321386.321395.

Popis: The Blumovy axiomy.

Algebraické metody pro interaktivní kontrolní systémy

• Lund, C.; Fortnow, L.; Karloff, H .; Nisan, N. (1992). "Algebraické metody pro interaktivní kontrolní systémy". Deník ACM. 39 (4): 859–868. CiteSeerX  10.1.1.41.9477. doi:10.1145/146585.146605.

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

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

• Cook, Stephen A. (1971). „Složitost postupů prokazujících věty“ (PDF). Proceedings of the 3rd Annual ACM Symposium on Theory of Computing: 151–158. CiteSeerX  10.1.1.406.395. doi:10.1145/800157.805047.

Popis: Tento příspěvek představil koncept NP-úplnost a dokázal to Booleovský problém uspokojivosti (SAT) je NP-Complete. Všimněte si, že podobné myšlenky vyvinul nezávisle o něco později Leonid Levin at "Levin, Universal Search Problems. Problemy Peredachi Informatsii 9 (3): 265–266, 1973".

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

• Garey, Michael R.; Johnson, David S. (1979). Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti. New York: Freeman. ISBN  978-0-7167-1045-5.

Popis: Hlavní význam této knihy je dán jejím rozsáhlým seznamem více než 300 NP-Complete problémy. 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

• Rabin, Michael O. (1960). "Stupeň obtížnosti výpočtu funkce a částečné řazení rekurzivních množin" (PDF). Technická zpráva č. 2. Jeruzalém: Hebrejská univerzita.

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

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 (Proceedings of the Third Symposium on Nerovnosti konané na University of California, Los Angeles, Kalifornie, 1. - 9. září 1969, věnovaná památce Theodora S. Motzkina). New York-Londýn: Academic Press. str. 159–175. PAN  0332165.CS1 maint: ref = harv (odkaz)

Popis: Zkonstruoval dimenzi „Klee – Mintyova kostka“D, jehož 2^D rohy navštěvuje každý Dantzig je simplexní algoritmus pro lineární optimalizace.

Jak postavit náhodné funkce

• Goldreich, O.; Goldwasser, S.; Micali, S. (1986). "Jak postavit náhodné funkce" (PDF). Deník ACM. 33 (4): 792–807. doi:10.1145/6490.6503.

Popis: Tento dokument ukázal, že existence jednosměrné funkce vede k výpočetní náhodnost.

IP = PSPACE

• Shamir, A. (1992). "IP = PSPACE". Deník ACM. 39 (4): 869–877. doi:10.1145/146585.146609.

Popis: IP je třída složitosti, jejíž charakterizace (na základě interaktivní kontrolní systémy ) 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 to ukázal 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

• R. M. Karp
• V editorech R. E. Miller a J. W. Thatcher, Složitost počítačových výpočtů, Plenum Press, New York, NY, 1972, s. 85–103

Popis: Tento dokument to ukázal 21 různých problémů jsou NP-Complete a ukázal důležitost konceptu.

Znalostní složitost interaktivních zkušebních systémů

• Goldwasser, S.; Micali, S.; Rackoff, C. (1989). „Znalostní složitost interaktivních zkušebních systémů“ (PDF). SIAM J. Comput. 18 (1): 186–208. doi:10.1137/0218012.

Popis: Tento příspěvek představil koncept nulové znalosti.^[6]

Dopis od Gödela von Neumannovi

• Kurt Gödel
• Dopis od Gödel na John von Neumann, 20. března 1956
• Online verze

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

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

• Hartmanis, Juris; Stearns, Richarde (1965). „O výpočetní složitosti algoritmů“. Transakce Americké matematické společnosti. 117: 285–306. doi:10.1090 / s0002-9947-1965-0170805-7.

Popis: Tato práce dala výpočetní složitost jeho jméno a semeno.

Cesty, stromy a květiny

• Edmonds, J. (1965). "Cesty, stromy a květiny". Kanadský žurnál matematiky. 17: 449–467. doi:10.4153 / CJM-1965-045-4.

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žitost. Více informací viz [2].

Teorie a aplikace funkcí padacích dveří

• Yao, A. C. (1982). "Teorie a aplikace funkcí padacích dveří". 23. výroční sympozium o základech informatiky (SFCS 1982). 80–91. doi:10.1109 / SFCS.1982.45.

Popis: Tento příspěvek vytváří teoretický rámec pro funkce padacích dveří a popsali některé jejich aplikace, například v kryptografie. 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

• C.H. Papadimitriou
• Addison-Wesley, 1994, ISBN  0-201-53082-1

Popis: Úvod 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

• Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S.; Szegedy, M. (1996). „Interaktivní důkazy a tvrdost přibližných klik“. Deník ACM. 43 (2): 268–292. doi:10.1145/226643.226652.

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

• Arora, S.; Safra, S. (1998). "Pravděpodobnostní kontrola důkazů: nová charakteristika NP". Deník ACM. 45: 70–122. doi:10.1145/273865.273901.

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

• Arora, S.; Lund, C.; Motwani, R.; Súdán, M.; Szegedy, M. (1998). "Ověření důkazu a tvrdost problémů s aproximací". Deník ACM. 45 (3): 501–555. CiteSeerX  10.1.1.145.4652. doi:10.1145/278298.278306.

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í. Vidět Věta o PCP.

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

• Cobham, Alan (1964). „Skutečná výpočetní obtížnost funkcí“ (PDF). Proc. Z Mezinárodního kongresu logiky, metodologie a filozofie vědy z roku 1964: 24–30.

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“

• Davis, M.; Logemann, G .; Loveland, D. (1962). „Strojový program pro dokazování vět“ (PDF). Komunikace ACM. 5 (7): 394–397. doi:10.1145/368273.368557.

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

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

• Robinson, J. A. (1965). „Strojově orientovaná logika založená na principu rozlišení“. Deník ACM. 12: 23–41. doi:10.1145/321250.321253.

Popis: První popis rozlišení a unifikace použito v automatizované dokazování věty; použito v Prolog a logické programování.

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

• Držel, M.; Karp, R. M. (1970). „Problém obchodního cestujícího a minimální rozpětí stromů“. Operační výzkum. 18 (6): 1138–1162. doi:10.1287 / opre.18.6.1138.

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

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

• L. G. Khachiyan
• Sovětská matematika - Doklady, sv. 20, s. 191–194, 1979

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

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

• Rabin, M. (1980). Msgstr "Pravděpodobnostní algoritmus pro testování primality". Žurnál teorie čísel. 12 (1): 128–138. doi:10.1016 / 0022-314X (80) 90084-0.

Popis: Příspěvek představil Miller-Rabinov test primality a nastínil program randomizované algoritmy.

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

• Kirkpatrick, S.; Gelatt, C. D .; Vecchi, M. P. (1983). "Optimalizace pomocí simulovaného žíhání". Věda. 220 (4598): 671–680. Bibcode:1983Sci ... 220..671K. CiteSeerX  10.1.1.123.7607. doi:10.1126 / science.220.4598.671. PMID  17813860.

Popis: Tento článek je popsán simulované žíhání což je nyní velmi běžná heuristika pro NP-Complete problémy.

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

• Donald Knuth

Popis: Toto monografie má čtyři svazky pokrývající populární algoritmy. Algoritmy jsou psány v angličtině a SMĚS montážní jazyk (nebo MMIX montážní jazyk v novějších svazcích). Díky tomu jsou algoritmy srozumitelné a přesné. Použití a nízkoúrovňový programovací jazyk frustruje některé programátory, kteří více znají moderní strukturované programování jazyky.

Algoritmy + datové struktury = programy

• Niklaus Wirth
• Prentice Hall, 1976, ISBN  0-13-022418-9

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ů

• Alfred V. Aho, John E. Hopcroft, a Jeffrey D. Ullman
• Addison-Wesley, 1974, ISBN  0-201-00029-6

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

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

• Dromey, R. G. (1982). Jak to vyřešit počítačem. Prentice-Hall Mezinárodní. ISBN  978-0-13-434001-2.

Popis: Vysvětluje Pročalgoritmů a datových struktur. Vysvětluje Tvůrčí proces, Řád odůvodnění, Faktory návrhu za inovativními řešeními.

Algoritmy

• Robert Sedgewick
• Addison-Wesley, 1983, ISBN  0-201-06672-6

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ů

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, a Clifford Stein
• 3. vydání, MIT Press, 2009, ISBN  978-0-262-03384-8.

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“

• Kolmogorov, Andrej N. (1963). "Na tabulkách náhodných čísel". Sankhya Ser. A. 25: 369–375. PAN  0178484.
• Kolmogorov, Andrej N. (1963). "Na tabulkách náhodných čísel". Teoretická informatika. 207 (2): 387–395. doi:10.1016 / S0304-3975 (98) 00075-9. PAN  1643414.

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

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

• Ray Solomonoff
• Informace a kontrola, sv. 7, s. 1–22 a 224–254, 1964
• Online kopie: část I., část II

Popis: Byl to začátek roku teorie algoritmických informací a Kolmogorovova složitost. Všimněte si však, že Kolmogorovova složitost je pojmenován po Andrey Kolmogorov, řekl, že semena této myšlenky jsou způsobena Ray Solomonoff. Andrey Kolmogorov do této oblasti hodně přispěl, ale v dalších článcích.

"Algoritmická teorie informací"

• Chaitin, Gregory (1977). "Algoritmická teorie informací" (PDF). IBM Journal of Research and Development. 21 (4): 350–359. CiteSeerX  10.1.1.48.3094. doi:10.1147 / kolo 214.0350. Archivovány od originál (PDF) dne 2009-05-30.

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

Informační teorie

„Matematická teorie komunikace“

• Shannon, C.E. (1948). „Matematická teorie komunikace“. Technický deník Bell System. 27 (3): 379–423, 623–656. doi:10.1002 / j.1538-7305.1948.tb01338.x. hdl:10338.dmlcz / 101429.

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

„Kódy pro detekci a opravu chyb“

• Hamming, Richarde (1950). „Kódy pro detekci a opravu chyb“. Technický deník Bell System. 29 (2): 147–160. doi:10.1002 / j.1538-7305.1950.tb00463.x. hdl:10945/46756.

Popis: V tomto příspěvku představil Hamming myšlenku kód pro opravu chyb. Stvořil Hammingův kód a Hammingova vzdálenost a vyvinuli metody pro ověření optimality kódu.

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

• Huffman, D. (1952). „Metoda pro konstrukci kódů minimální redundance“ (PDF). Sborník IRE. 40 (9): 1098–1101. doi:10.1109 / JRPROC.1952.273898.

Popis: The Huffmanovo kódování.

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

• Ziv, J.; Lempel, A. (1977). "Univerzální algoritmus pro sekvenční kompresi dat". Transakce IEEE na teorii informací. 23 (3): 337–343. CiteSeerX  10.1.1.118.8921. doi:10.1109 / TIT.1977.1055714. hdl:10338.dmlcz / 142947. Archivovány od originál dne 04.12.2003.

Popis: The LZ77 kompresní algoritmus.

Základy teorie informace

• T. Cover; J. Thomas (1991). Základy teorie informace. str.38–42. ISBN  978-0-471-06259-2.

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

Formální ověření

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

• Floyd, Robert (1967). Přiřazení významu programům (PDF). Matematické aspekty informatiky. Sborník sympozií z aplikované matematiky. 19. 19–32. doi:10.1090 / psapm / 019/0235771. ISBN  9780821813195.

Popis: Významný článek Roberta Floyda Assigning Meanings to Programs 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 - příspěvek také zavádí pojmy invariantní smyčky a ověřovací podmínka.

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

• Hoare, C. A. R. (Říjen 1969). „Axiomatický základ pro počítačové programování“ (PDF). Komunikace ACM. 12 (10): 576–580. doi:10.1145/363235.363259. Archivovány od originál (PDF) dne 04.03.2016.

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) Hoareových trojic.

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

• Dijkstra, E. W. (1975). „Hlídané příkazy, neurčitost a formální odvozování programů“. Komunikace ACM. 18 (8): 453–457. doi:10.1145/360933.360975.

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

• Edward A. Ashcroft
• J. Comput. Syst. Sci. 10 (1): 110–135 (1975) doi:10.1016 / s0022-0000 (75) 80018-3

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

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

• Susan S. Owicki, David Gries
• Acta Inform. 6: 319–340 (1976)

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í

• Edsger W. Dijkstra
• 1976

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

• Joe Stoy
• 1977

Popis: Denotační sémantika Joe Stoyho je první (postgraduální) 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ů

• Pnueli, A. (1977). Msgstr "Časová logika programů". 18. výroční sympozium o základech informatiky (SFCS 1977). IEEE. str. 46–57. doi:10.1109 / SFCS.1977.32.

Popis: Použití časová logika byla navržena jako metoda formálního ověření.

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

• E. Allen Emerson, Edmund M. Clarke
• V Proc. 7. mezinárodní kolokvium o jazycích a programování automatů, strany 169–181, 1980

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

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

• AUTO. Hoare
• 1978

Popis: Tony Hoare's (originál) komunikující sekvenční procesy Dokument (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ů

• Robin Milner
• 1980

Popis: Dokument Robin Milner A Calculus of Communicating Systems (CCS) popisuje procesní algebru, která umožňuje formální odůvodnění systémů souběžných procesů, 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

• Cliff Jones
• 1980

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 vylepšením (nebo reifikací) dat, kdy se algebraicky definované abstraktní datové typy formálně transformují do postupně „konkrétnějších“ reprezentací.

Věda o programování

• David Gries
• 1981

Popis: Učebnice Davida Griesa The Science of Programming popisuje Dijkstrovu nejslabší předpokladovou metodu derivace formálního programu, s výjimkou mnohem dostupnějšího způsobu než Dijkstrina 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)

• AUTO. Hoare
• 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)

• Girard, J.-Y (1987). "Lineární logika" (PDF). Teoretická informatika. 50 (1): 1–102. doi:10.1016/0304-3975(87)90045-4. Archivovány od originál (PDF) dne 29. 11. 2006.

Popis: Girard's lineární logika byl průlom v navrhování typovacích systémů pro sekvenční a souběžné výpočty, zejména pro typové systémy s vědomím zdrojů.

Kalkul mobilních procesů (1989)

• R. Milner J. Parrow, D. Walker
• 1989
• Online verze: Část 1 a Část 2

Popis: Tento článek představuje Pi-kalkul, 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

• Spivey, J. M. (1992). Z notace: Referenční příručka (2. vyd.). Prentice Hall International. ISBN  978-0-13-978529-0. Archivovány od originál dne 2016-06-20. Citováno 2009-08-24.

Popis: Klasická učebnice Mikea Spiveyho The Z Notation: A Reference Manual shrnuje formální specifikační jazyk Z notace který, i když pochází od Jean-Raymonda Abriala, se během předchozího desetiletí vyvinul (hlavně) na Oxfordské univerzitě.

Komunikace a souběžnost

• Robin Milner
• Prentice-Hall International, 1989

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 v CCS.

Praktická teorie programování

• Eric Hehner
• Springer, 1993, aktuální vydání online tady

Popis: aktuální verze aplikace Predikativní programování. Základ pro AUTO. Hoare UTP. Nejjednodušší a nejkomplexnější formální metody.

Reference