I000 Úvod do informatiky

Fakulta informatiky
podzim 2000
Rozsah
2/0. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
prof. RNDr. Jiří Zlatuška, CSc. (přednášející)
doc. RNDr. Vojtěch Řehák, Ph.D. (pomocník)
Mgr. Pavel Krčál (pomocník)
doc. Mgr. Radek Pelánek, Ph.D. (pomocník)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Jiří Zlatuška, CSc.
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
Osnova
  • Úvod do matematických konstrukcí relevantních ke studiu programů jako matematických objektů: indukce a rekurze v netriviálních doménách, vztah formálního jazyka k jeho sémantice, operační sémantika rekurzívních programů, univerzální stroj a problém zastavení.
  • Základní pojmy: funkce, grafy, relace ekvivalence, stromy.
  • Indukce a její aplikace: definice množin a funkcí pomocí indukce, parametrizace definic.
  • Matematické datové typy, typ seznamů a implementace obecných datových typů pomocí seznamů.
  • Jazyk nad datovými typy a jejich sémantika: termy, podmíněné příkazy, podprogramy; sémantika volání jménem a volání hodnotou.
  • Programování pomocí indukce, důkazy správnosti rekurzívních programů.
  • Univerzální stroj pro jazyk rekurzívních programů, nerozhodnutelnost problému zastavení.
Literatura
  • WAND, Mitchell. Induction, recursion, and programming. New York: North Holland, 1980, 202 s. ISBN 0444003223. info
Další komentáře
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích zima 1995, zima 1996, zima 1997, podzim 1998, podzim 1999, podzim 2001.