I081 Lambda kalkul

Fakulta informatiky
jaro 2001
Rozsah
2/0. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k.
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.
Rozvrh
Po 9:00–10:50 B410
Předpoklady
( I007 Vyčíslitelnost || I008 Výpočtová logika )&& M009 Algebra II
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
Cíle předmětu
Č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.
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
Metody hodnocení
přednášky a samostané studium dle literatury zadané přednášejícím
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 stududentů
Další komentáře
Předmět je vyučován jednou za dva roky.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/jaro2001/I081