NTIN090 Základy složitosti a vyčíslitelnosti

Úvodní kurz do složitosti a vyčíslitelnosti. Lze nahradit předměty Vyčíslitelnost I a Složitosti I. Na zkoušku se lze přihlásit pouze po úspěšném absolvování zápočtového testu. Ten se zpravidla píše na posledním cvičení, případně na kterékoliv zkoušce (na test se není nutné se hlásit předem, stačí přijít).

Zdroje

• Stránka předmětu

• Poznámky z cvičení

• Emulátor primitivně rekurzivních funkcí

• Johančiny pohádky z vyčíslitelnosti

Zápočtový test

• 4 příklady z látky probrané na cvičeních (obtížnost nebývá odlišná)

• pro úspěšné splnění je třeba mít aspoň 3 příklady správně z následujících okruhů

  • Konstrukce TS rozpoznávající nějaký jazyk

  • Konstrukce PRF z axiomů a odvozovacích pravidel

  • Úloha na s-m-n větu

  • Převod jedné úlohy na druhou

• je znám případ, kdy Kučera dovolil nahlédnutí do slajdů z přednášky

Minulé zápočtové testy

• 2011

  • Zápočet 10.1.2011

• 2010

  • Zápočet 13.1.2010

  • Zápočet 27.1.2010

  • Zápočet 28.1.2010

  • Zápočet 4.2.2010

  • Zápočet 8.2.2010

Zkouška

• zkouška probíhá písemně s následnou debatou nad řešením.

• v každé písemce je příklad na Riceovu větu

• všechny příklady na převody bere Kučera z doporučené literatury, konkrétně - Garey, Johnson: Computers and intractability - a guide to the theory of NPcompleteness, W.H. Freeman 1978. Bere pouze ty jednodušší ze začatku. Není problém zapůjčit tuto knihu v knihovně, je tam prý v několika výtiscích.