IB000 Úvod do informatiky

Fakulta informatiky
podzim 2003
Rozsah
2/0. 2 kr. (plus ukončení). Ukončení: zk.
Vyučující
prof. RNDr. Antonín Kučera, Ph.D. (přednášející)
doc. RNDr. Tomáš Brázdil, Ph.D. (pomocník)
Mgr. Jan Holeček (pomocník)
RNDr. Pavel Šimeček, Ph.D. (pomocník)
Mgr. Jitka Žídková (pomocník)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování - Fakulta informatiky
Kontaktní osoba: prof. RNDr. Antonín Kučera, Ph.D.
Rozvrh
Po 10:00–11:50 TA (Aula Technická)
Předpoklady
! I000 Úvod do informatiky
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
V tomto předmětu se posluchači seznamí se základními matematickými konstrukcemi potřebnými pro popis sémantiky programů a formalizaci vztahů mezi intuitivními programovými konstrukcemi a jejich matematickým významem. Vytváří se tím pojmový základ pro řadu dalších předmětů, které patří k základní teoretické výbavě informatiků.
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í.
  • Výroková logika a predikátová logika 1.řádu (úvod).
  • 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ě.
Nachází se v prerekvizitách jiných předmětů
Předmět je zařazen také v obdobích podzim 2002, podzim 2004, podzim 2005, jaro 2006, podzim 2006, podzim 2007, jaro 2008, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019, podzim 2020, podzim 2021.