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

IA081 Lambda calculus

Rozsah

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

Vyučující

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

Garance

prof. RNDr. Jiří Zlatuška, 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

Út 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

• Analýza a zpracování obrazu (program FI, N-VIZ)
• 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 a systémová biologie (program FI, N-UIZD)
• Bioinformatika (program FI, N-AP)
• Computer Games Development (program FI, N-VIZ_A)
• Computer Graphics and Visualisation (program FI, N-VIZ_A)
• Computer Networks and Communications (program FI, N-PSKB_A)
• Cybersecurity Management (program FI, N-RSSS_A)
• Diskrétní algoritmy a modely (program FI, N-TEI)
• Formální analýza počítačových systémů (program FI, N-TEI)
• Grafický design (program FI, N-VIZ)
• Graphic Design (program FI, N-VIZ_A)
• Hardware Systems (program FI, N-PSKB_A)
• Hardwarové systémy (program FI, N-PSKB)
• Image Processing and Analysis (program FI, N-VIZ_A)
• Informační bezpečnost (program FI, N-PSKB)
• Informační systémy (program FI, N-IN)
• Information Security (program FI, N-PSKB_A)
• Kvantové a jiné neklasické výpočetní modely (program FI, N-TEI)
• Paralelní a distribuované systémy (program FI, N-IN)
• Počítačová grafika a vizualizace (program FI, N-VIZ)
• Počítačová grafika (program FI, N-IN)
• Počítačové sítě a komunikace (program FI, N-IN)
• Počítačové sítě a komunikace (program FI, N-PSKB)
• Počítačové systémy (program FI, N-IN)
• Principy programovacích jazyků (program FI, N-TEI)
• Programovatelné technické struktury (angl.) (program FI, N-IN)
• Programovatelné technické struktury (program FI, N-IN)
• Řízení kyberbezpečnosti (program FI, N-RSSS)
• Řízení vývoje služeb (program FI, N-RSSS)
• Řízení vývoje softwarových systémů (program FI, N-RSSS)
• Services Development Management (program FI, N-RSSS_A)
• 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)
• Software Systems Development Management (program FI, N-RSSS_A)
• Software Systems (program FI, N-PSKB_A)
• Softwarové systémy (program FI, N-PSKB)
• Strojové učení a umělá inteligence (program FI, N-UIZD)
• 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)
• Vývoj počítačových her (program FI, N-VIZ)
• Zpracování a analýza rozsáhlých dat (program FI, N-UIZD)
• Zpracování obrazu (program FI, N-AP)
• Zpracování přirozeného jazyka (program FI, N-UIZD)

Cíle předmětu

Cílem kurzu je seznámení se studentů s lambda-kalkulem a demonstrace vyjadřovací síly lambda-kalkulu na řadě obecných výpočetních konceptů.

Výstupy z učení

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žít 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 (nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/jaro2024/IA081