PV109: Historie a vývojové trendy ve VT Historie teoretických základů informatiky a výpočetní techniky Eva Hladká Fakulta informatiky Masarykovy univerzity podzim 2014 Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 1 / 23 CZ.1.07/2.2.00/28.0041 Centrum interaktivních a multimediálních studijních opor pro inovaci výuky a efektivní učení !7n y evropský SOCiální ■ MINISTERSTVO ŠKOLSTVÍ, fond V CR EVROPSKÁ UNIE MLÁDEŽE A TĚLOVÝCHOVY 'XPřf INVESTICE DO ROZVOJE VZDĚLÁVÁNI Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 2/23 • Seznámení s historií výpočetní techniky a informatiky • Lepší porozumění: historie —> vývojové trendy —> predikce budoucího vývoje • Poučení z chyb minulých může zabránit jejich opakování Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 3/23 Od matematiky k informatice Základní kameny výpočetní techniky: • logika, • teorie jazyků, • teorie komunikace. • Teoretická informatika • Vyčíslitelnost a složitost • Teorie informací a kódování • Algoritmy a datové struktury • Teorie jazyků - automaty a gramatiky • Paralelismus a distribuované systémy • Databáze a dolování dat «... • Aplikovaná informatika • Umělá inteligence • Architektura a návrh počítačů • Počítačová grafika a vizualizace • Bezpečnost o Softwarové inženýrství Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT I podzim 2014 5 / 23 • Počítat museli i lovci mamutů (ať už na prstech, nebo na stěnu jeskyně) • Starověké Řecko • Mnoho významných matematiků a filosofů, v matematice se rozvíjela zejména geometrie. • Aristoteles ze Stageiry (4. stol. p. n. I.) • Položil základy logiky - aristotelovská logika • a formálního dokazování pravdivosti formulí - důkaz sporem, náznaky důkazu indukcí • Blízký východ • Kupci a obchodníci, přinesli arabská čísla do Evropy. • První počítadla se objevila již v 11. stol. p. n. I.) • Muhamad ibn Músa al Chwárizmí (8./9. stol. n. I.) • shrnul znalosti arabské matematiky v knize Al-džebr wa-b-maqábala (odtud algebra) • z jeho jména vznikl pojem algoritmus Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 6/23 • Z řeckého slova logos - slovo, smysl, rozum • výroková logika • predikátová logika • Úplné systémy logických spojek • Booleova algebra (operace AND, OR, negace) • ShefFerova algebra (operace NAND) • Piercova algebra (operace NOR) • Tyto operace tvoří základní členy v logických obvodech Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 7/23 • Pocházel z rodiny obchodníka, otec jej vedl k matematice již od raného dětství • Učil se z Newtonových Principií, ve 24 letech vydal první matematický článek • Ve 32 letech vydal knihu The Mathematical Analysis of Logic, která umožnila exaktně vyjádřit logické operace a formule. • Vycházel ze dvou poznatků: O Logika je počítání na dvouprvkové množině {True, Falše}. Q Logické operátory jsou v podstatě „početní" zdroj: http://en.nikipedia.org operace nad touto množinou. Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 8/23 • Brněnský rodák rakouské národnosti, nikdy neuměl česky. S rodinou emigrovali po anšlusu Rakouska do USA, kde se usadil v Princetonu. • Zcela rozvrátil dosavadní úvahy o axiomatizaci matematiky a její formální úplnosti. • První a druhá Gódelova věta o neúplnosti. • Těmito větami tak Godel položil, skrze teorii množin, pevné základy mj. pro teorii výpočetní složitosti či programování počítačů. • Více v předmětu MA015 - Matematická logika (prof. Kučera) Zdroj: http://en.wikipedia.org Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 9/23 • Množina konečných slov nad určitou abecedou. • Pojem formálni jazyk poprvé zmínil Gottlob Frege v knize Begriffsschrift v roce 1879. o Využití: • Programovací jazyky • Lexikálni analýza • Syntaktická analýza Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 10 / 23 • Britský matematik, logik a kryptoanalytik, který se podílel na prolomení Enigmy • Ovlivnil obor vyčíslitelnosti, definoval Turingův stroj • Během 2. světové války působil jako Člen týmu v Bletchley Park, UK. • Podílel se na prolomení Enigmy (jeden z důsledků bylo i významné zkrácení války). • 1950: Turingův test (opačný přístup je hojně využíván jako CAPTCHA) • Turingova cena - ocenění pro informatiky Zdroj: http://en.wikipedia.org Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 11 / 23 • Turingův stroj • teoretický model - tvoří jej konečný automat, program ve formě pravidel přechodové funkce a nekonečná páska (různé varianty) • Problém zastavení (1936) • Úloha z teorie vyčíslitelnosti • Lze rozhodnout, zda výpočet libovolného programu skončí v konečném čase, nebo nikoliv? • Random-Access Machine • další teoretický model, ekvivalentní s turingovým strojem (nezaměňovat s Random Access Memory) • RAM je tvořen speciálním registrem a potenciálně neomezenou pamětí, instrukční sada obsahuje základní aritmetické operace a metody přímé a nepřímé adresace paměti. • Dalším teoretickým turingovsky úplným modelem jsou např. WHILE-programy používané v teorii vyčíslitelnosti. Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 12 / 23 • Americký matematik a logik, který významně prispel v oblasti teorie vyčíslitelnosti a formálních jazyku. • Churchova-Turingova teze - původně dvě nezávislé teze, jejichž ekvivalenci dokázal v roce 1952 S. C. Kleene. • Teze: Ke každému algoritmu existuje ekvivalentní Turingův stroj • 1936: publikoval A-kalkul (spolu s Kleenem) • Základ funkcionálních programovacíh jazyků (např. LISP, Haskell) • Formální systém a výpočetní model, jež slouží prO Studium funkcí a rekurze Zdroj: http://en.vikipedia.org • Výpočetní silou je ekvivalentní Turingovu stroji Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 13 / 23 • Lingvista, filosof, logik původem z USA o V lingvistice se zabýva formálními jazyky, emeritní profesor, stále působí na MIT • 1956: Definoval Chomského hierarchii jazyků • Zadefinoval formálni jazyky a vztahy mezi nimi • Chomského hierarchie jazyků patří k základním stavebním kamenům informatiky • regulární C bezkontextové C kontextové C rekursivně spočetné jazyky Zdroj: http://en.wikipedia.org Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT I podzim 2014 14 / 23 Vztahy mezi vyčíslitelností, složitostí a formálními jazyky • Součást teorie vyčíslitelnosti a složitosti o Využívá se pro určení zdrojů (čas, prostor) potřebných pro běh algoritmu. • Asymptotická složitost (Big O notation) • Součást rozsáhlejší Bachmann-Landau notace, která vznikla již na počátku 19. století. • Původně určena pro zjišťování chování funkcí. Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 16 / 23 • Emeritní profesor na Stanford University • Bývá označován jako otec analýzy algoritmů • Zasadil se o využití asymptotické notace v analýze algoritmů, významně také přispěl v oblasti výpočetní složitosti. • Vedle teoretické informatiky je také autorem sázecího systému Tj=Xa autorem „programátorské bible" The Art of Computer Programming Zdroj: http://en.wikipedia.org Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 17 / 23 • Holandský informatik, který významně ovlivnil mnoho oblastí informatiky. • Za významný přínos v rozvoji programovacích jazyků získal v roce 1972 Turingovu cenu. • 1968: V článku A Case against the GO TO Statement prezentoval problémy používání příkazu GO TO. • Patřil mezi průkopníky distribuovaného počítání, zavedl pojem semaforu. • V teorii grafů je známý díky algoritmu pro hledání nejkraší cesty. Zdroj: http://en.wikipedia.org Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 18 / 23 • Odvětví informatiky, které se zabývá měřením, přenosem, kódováním, ukládáním a následným zpracováním informací. • Spojuje aplikovanou matematiku a elektrotechniku. • Praktickými výsledky jsou algoritmy pro ztrátovou a bezztrátovou kompresi dat a modulační techniky signálu. • Zakladatelem tohoto oboru je Claude Shannon. • Klíčovým pojmem je entropie (míra neurčitosti informace). Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 19 / 23 • Americký matematik, elektrotechnik a kryptograf • 1938: Využil poznatku booleovy algebry pro návrh přepínacích okruhu (založených na relé) • Během 2.SV se podílel jako kryptoanalytik i na rozluštění šifer používaných německými ponorkami. • 1948: Po válce ve svém článku A Mathematical Theory of Communication položil základy teorie informace. Dále se zaměřil na způsoby, jak co nejefektivněji zakódovat informace. • Claude E. Shannon Award (IEEE) - ocenění pro významné osobnosti v teorii informace Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT I podzim 2014 20 / 23 • Věda, která se zabývá principy řízení a přenosu informací v komplexních systémech (strojích, živých organismech a společenstvích). • K popisu procesů je použit matematický aparát • Norbert Wiener (1894 - 1964) - matematik, profesor na MIT, považován za zakladatele kybernetiky • 1948: kniha Kybernetika aneb Řízení a sdělování u organismů a strojů Zdroj: http://www.nap.edu Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 21 / 23 • Donald E. Knuth • viz výše • Nikiaus Wirth • navrhl několik programovacích jazyků (např. Pascal); nositel Turingovy ceny • Charles Bennett • jeden ze zakladatelů moderní teorie kvantové informace • Dines Bj0rner • Zabýval se oblastí formálních metod pro vývoj počítačových systémů, jeho stěžejním dílem je trojdílná publikace Software Engineering. • Javier Esparza • Zabývá se verifikací a formálními modely distribuovaných systémů • http://www.f i.muni.cz/about/cestne_doktoraty.xhtml Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT podzim 2014 22 / 23 • Významných osobností informatiky a výpočetní techniky je mnohem více a s dalšími jmény se zcela jistě potkáme ještě později v semestru či v jiných kurzech. • Žádná z uvedených osobností nepůsobila jen v rámci jedné podoblasti informatiky, ale měli daleko širší záběr i do jiných oborů (např. Godel). • Mnohé myšlenky byly natolik převratné, že zcela změnily další směrování výzkumu a vývoje v této oblasti. Eva Hladká (Fl MU) PV109: Historie a vývojové trendy ve VT I podzim 2014 23 / 23