MI-VYC
Katedra aplikované matematiky otevře v letním semestru 2014/15 nový předmět Vyčíslitelnost (MI-VYC, 2+2, Jan Starý).
Před osmdesáti lety stála rodící se informatika (a její starší sestra, matematická logika) před otázkou, kterou už nešlo odkládat: co přesně je algoritmus? Co přesně máme na mysli, když říkáme, že nějaké číslo, slovo, důkaz atd. lze získat mechanickým postupem? Jakou funkci můžeme považovat za mechanicky vyčíslitelnou, tj. takovou, že výpočet jejích hodnot lze svěřit nějakému (ideálnímu) stroji?
Taková otázka má dokonce filosofický přesah: do jaké míry může být rozum nahrazen strojem, a kde přesně leží hranice, za níž se neobejdeme bez rozumu? Během třicátých let vzniklo několik formalizací pojmu algoritmu: rekursivní funkce, Turingovy stroje, lambda kalkulus, Markovovy řetězce, register machines, a další. Postupně se ukázalo, že jejich výpočetní síla je stejná. Například rekursivní funkce je právě taková, kterou vyčísluje nějaký Turingův stroj. To vedlo ke všeobecně přijímané Chorchově tezi, podle které existuje jedna „správná“ představa algoritmu, kterou jen popisujeme různými způsoby.
V přednášce popíšeme rekursivní funkce a Turingovy stroje (podle času i další formalizace) a předvedeme jejich vzájemnou ekvivalenci. Popíšeme universální funkce a universální stroje.Zformulujeme Halting Problem a předvedeme jeho algoritmickou neřešitelnost.
Předvedeme souvislosti s logikou a aritmetikou: kódování jazyka a rekursivní axiomatisovatelnost. Zformulujeme a podle možností dokážeme Godelovy věty o nerozhodnutelnosti a neúplnosti.
MI-MSI
Katedra aplikované matematiky také nabízí v letním semestru 2014/15 předmět Matematické struktury v informatice (MI-MSI, 2+1, Jan Starý).
Jedná se o přehled matematických metod, které nalezly uplatnění při popisu základních pojmů informatiky. Cílem je získat důkladnější pochopení těchto metod v kontextu ostatní matematiky, ale i předvedení konkrétních aplikací na problémech.
Zdrojový kód programu je text v jakémsi formálním jazyce. Tak jako ostatní jazyky, ať už přirozené či umělé, mají i programovací jazyky svou syntax a svou sémantiku.
Zatímco syntax stanovuje gramatická pravidla, tj. popisuje, které řetězce považujeme vůbec za slova a věty (jména proměnných, příkazy, …), a jakými způsoby můžeme z jednoduchých výrazů skládat složitější, sémantika přiřazuje výrazům jazyka „význam“, resp. ptá se, co tyto výrazy „znamenají“. Co „znamená“ zdrojový kód programu?
Jedna možná odpověď se nabízí: „významem“ zdrojového kódu je právě a jen ta sada instrukcí, která vzejde z kompilace; tyto instrukce pak bude vykonávat nějaký (předem známý) procesor, na kterém každá z těchto instrukcí znamená jistou (předem známou) operaci v paměti či registrech. Tato přirozená úvaha je základem tzv. operační sémantiky programovacích jazyků.
Stejně přirozená je však i následující námitka: v takové sémantice je „význam“ kódu závislý na překladači, procesoru, a konkrétní reprezentaci dat v paměti. Existují ale přeci programy běžící na různých procesorech s různými instrukčními sadami, napsané v různých programovacích jazycích, které v nějakém dobrém smyslu „dělají totéž“ — přestože na nejnižší úrovni se jedná o jiné operace nad jinou reprezentací dat. Je přirozené požadovat, aby „význam“ takových programů byl tentýž. Takový požadavek znamená, že „význam“ kódu by neměl být závislý na překladači a architektuře, ba ani na jazyce. Popíšeme Scottovu denotační sémantiku, která je matematickým modelem takového „významu“.
Za tím účelem zavedeme základní algebraické a topologické pojmy potřebné k takovému popisu, popíšeme datové typy jako svazy opatřené jistou topologií, a procedury jakožto spojitá zobrazení mezi datovými typy.
Autor: Jan Starý