FI:IA081 Lambda calculus - Informace o předmětu

IA081 Lambda calculus

Rozsah

2/0. 3 kr. (plus ukončení). Ukončení: zk.

Vyučující

prof. RNDr. Jiří Zlatuška, CSc. (přednášející)

Garance

prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Jiří Zlatuška, CSc.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

Po 10:00–11:50 B411

Omezení zápisu do předmětu

Předmět je nabízen i studentům mimo mateřské obory.

Mateřské obory/plány

• Aplikovaná informatika (program FI, N-AP)
• Bezpečnost informačních technologií (angl.) (program FI, N-IN)
• Bezpečnost informačních technologií (program FI, N-IN)
• Bioinformatika (program FI, N-AP)
• Informační systémy (program FI, N-IN)
• Paralelní a distribuované systémy (program FI, N-IN)
• Počítačová grafika (program FI, N-IN)
• Počítačové sítě a komunikace (program FI, N-IN)
• Počítačové systémy (program FI, N-IN)
• Programovatelné technické struktury (angl.) (program FI, N-IN)
• Programovatelné technické struktury (program FI, N-IN)
• Služby - výzkum, řízení a inovace (angl.) (program FI, N-AP)
• Služby - výzkum, řízení a inovace (program FI, N-AP)
• Sociální informatika (program FI, B-AP)
• Teoretická informatika (program FI, N-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, N-SS) (2)
• Umělá inteligence a zpracování přirozeného jazyka (program FI, N-IN)
• Zpracování obrazu (program FI, N-AP)

Cíle předmětu

Na konci tohoto kurzu buse student seznámen se základnimi pojmy, technikami a výsledky teorie sekvenčních funkcí v podobě lambda-kalkulu a kombinatorické logiky; seznámí se se základy typová i netypové varianty těchto formalismů; bude umět je použít pro formalizaci vyčíslitelnosti; seznámí se s principy konstrukce modelů lambda-kalkulu; zvládne užívání formalizace rekurzivních konstrukcí v programování i příslušných modelech; bude schopný použit ho jako referenčním formalismus vhodný pro řadu aplikací.

Osnova

• Čistý lambda-kalkul: lambda-termy, struktura termů, rovnostní teorie.
• Redukce: jednosměrné transformace, obecné redukce, beta-redukce.
• Lambda-kalkul a výpočty: kódování, rekurzívní definice, lambda-vyčíslitelnost, kombinátory pevného bodu, nerozhodnutelné vlastnosti.
• Modifikace teorie: kombinatorická logika, extenzionalita, éta-redukce.
• Typovaný lambda-kalkul: typy a termy, normální formy, množinové modely, silná normalizovatelnost, typy jako formule.
• Doménové modely: úplná částečná uspořádání, domény, nejmenší pevné body, parcialita.
• Konstrukce domén: složené domény, rekurzívní konstrukce domén, limitní domény.

Literatura

• ZLATUŠKA, Jiří. Lambda-kalkul. 1. vyd. Brno: Masarykova univerzita, 1993, 264 s. ISBN 8021008261. info
• BARENDREGT, H. P. Lambda calculus : its syntax and semantics. Rev. ed. Amsterdam: Elsevier, 1998, xv, 621 s. ISBN 0-444-86748-1. info
• HINDLEY, J. Roger a J. P. SELDIN. An Introduction to Combinators and the (lambda)-calculus. Cambridge: Cambridge University Press, 1986, 360 s. ISBN 0521318394. info
• AMADIO, Roberto M. a Pierre-Louis CURIEN. Domains and Lambda calculi. Cambridge: Cambridge University Press, 1998, xvi, 484. ISBN 0521622778. info

Výukové metody

přednášky

Metody hodnocení

samostatná písemná esej

Vyučovací jazyk

Angličtina

Informace učitele

Předmět je primárně určen pro vážné zájemce z řad doktorských a pokročilých magisterských studentů.

Další komentáře

Studijní materiály
Předmět je vyučován jednou za dva roky.

• Statistika zápisu (jaro 2017, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/jaro2017/IA081