Informace ke kursu "Teoretická informatika" ("Theoretical Computer Science") (LS 2012/2013)

Přednášející: prof. Petr Jančar (A1046), Petr.Jancar@vsb.cz ,
cvičící: doc. Petr Šaloun Petr.Saloun@vsb.cz , Ing. Martin Kot Martin.Kot@vsb.cz , Ing. Zdeněk Sawa Zdenek.Sawa@vsb.cz ,

KOMBINOVANÉ STUDIUM:
Vede Ing. Martin Kot, PhD.
Požadavky na studenty kombinované formy jsou v zásadě stejné jako požadavky na studenty prezenční formy studia; níže uvedené informace jsou tedy v mnohém relevantní i pro ně. Pro specifika týkající se studentů v kombinované formě studia je zřízena tato stránka:

• komb-studium.htm .

Aktuální důležité informace (v obráceném chronologickém pořadí):

• 14.6.2013. Informace i k dalším termínům prohlížení opravených písemek apod. se mohou objevit v aktualitách na stránce M. Kota.
• 29.5.2013. Případné aktuální informace ke zkoušce konané 31.5.2013 a termínu prohlížení opravených písemek se mohou objevit v aktualitách na stránce M. Kota. (PJ: Nebudu teď reagovat ani na případné emaily; směřujte na M. Kota.)
• 16.5.2013. Opravené zkouškové písemky z 15.5. budou k nahlédnutí 17.5. v 13.30 na A1024 . Opravný termín pro referáty (za 1 bod, jak vysvětleno v podmínkách níže) je 27.5. v 13.15 na B5 ; tento termín je určen i jako náhradní termín pro ty studenty, kteří byli řádně omluveni z řádného termínu.
• 7.5.2013. V Edisonu jsou vypsány termíny zkoušek v řádném zkouškovém období. (Pokud by náhodou v daný den byla naplněna kapacita, ozvěte se mi mailem.) Na 20.5.2013 je vypsán i náhradní termín zápočtové písemky pro ty, kteří byli řádně omluveni u řádného termínu. Zároveň se jedná i o opravný termín pro ty, kteří nedosáhli 8 bodů, ale kvalitním referátem doložili, že jsou schopni výpadek dohnat. (Jak je psáno v podmínkách níže, u opravného termínu je nutné získat alespoň 12 bodů, ale zapíšeme jen 8 bodů.)
• 19.4.2013. Výsledky zápočtové písemky se objeví v Edisonu v následujícím týdnu. K nahlédnutí pak budou písemky na cvičeních.
• 12.4.2013. Studenti, kteří půjdou v červnu 2013 k SZZ, mají možnost splnit úkol referát v pátek 10.5. 2013 ve 13.15 na C2. Výhradně pro tyto studenty (tedy pro ty, kteří se hlásí k SZZ v 6/2013) bude vypsán speciální zkouškový termín, a sice ve středu 15.5.2013 v 16.00 na C3 . (Po odevzdání diplomových prací se tito studenti ohlásí mailem pí Geletičové, která nám oprávněnost účasti na uvedených mimořádných termínech potvrdí.)
• 12.4.2013. Zápočtová písemka (18.4.2013) byla vypsána v Edisonu a posluchačům byla zaslána zpráva.
• 8.3.2013. Na zápočtovou písemku (konanou 18.4.2013) bude nutný zápis v Edisonu. (Vypíšeme později.)
• 11.2.2013. Čtvrteční přednáška byla v Edisonu změněna na sudý týden
  P1/01 Sudý Čt 14:15 - 15:45 2 PORB5
  První čtvrteční přednáška se tedy koná 21.2.2013 (tedy v 8.týdnu roku).
• 8.2.2013. Čtvrteční přednáška
  P1/01 Lichý Čt 14:15 - 15:45 2 PorB5
  je doplňující přednáška (konající se co dva týdny, první tedy 14.2., jelikož je to 7. (a tedy lichý) týden v roce) určená pro studenty s hlubším zájmem, kteří také aspirují na lepší hodnocení v předmětu; bude určitým způsobem navazovat na pondělní třetí hodinu.

Studijní opora

• Základní studijní text, P. Jančar: Teoretická informatika, VŠB-TU Ostrava 2007 (2010) je zde uložen jako pdf-soubor (rozsah 336 stran):
  • ti-text.2010-01-20.pdf
• Animace, které by vám měly pomoci osvětlit některé části textu, byste měli nalézt zde:
  • http://www.cs.vsb.cz/kot/animace.php.

Požadavky k zápočtu a způsob zkoušky:

• 1. Na přednášce určené (s předstihem) níže v části "Průběh výuky" se bude psát 45-minutová zápočtová písemka. Formálně bude rozdělena na dvě části, z každé z nich je možné získat až 12 bodů (celkově tedy 24 bodů). Nutnou podmínkou k získání zápočtu je zisk celkově alespoň 8 bodů.
     Je zde jen jeden pokus, který v zásadě není možné opakovat. Nemůže-li se někdo z vážného důvodu zúčastnit, musí se bez zbytečného prodlení (což většinou znamená předem) omluvit [např. cvičícímu emailem] a posléze onen vážný důvod doložit. Pro tyto případy by byl uspořádán výjimečný náhradní termín. Pro ty, kteří by nedosáhli 8 bodů, ale např. kvalitním referátem (viz níže) by doložili, že jsou schopni výpadek dohnat, bychom pravděpodobně uspořádali na konci semestru opravný termín, při němž by bylo nutné získat alespoň 12 bodů, ale zapsali bychom jen 8 bodů.
     Ukázka (struktury) zápočtové písemky je zde: 2010-ti-zap-uk.pdf . (Je možné, že dojde ke změnám, ale ne zásadního rázu.)
  2. Další nezbytnou podmínkou k získání zápočtu je úspěšné zvládnutí referátu (v opačném případě zápočet udělen nebude). Zadání se zde objeví do poloviny března a posluchačům bude číslo referátu přiděleno emailem; tento email nepotvrzujte, jen ten, kdo do 15.3. žádný email se zadáním nebude mít, nechť se ohlásí (emailem) cvičícímu. Rychlé prověření podkladů k referátu s otestováním skutečného porozumění proběhne v termínu ke konci semestru (bude určen v Průběhu výuky níže). Zisk bodů za referát je 5-11. Ukáže-li se, že referující tématu ve skutečnosti nerozumí a/nebo nemá rozumné podklady pro 15 minutový referát, úkol nesplní a na zápočet nemá nárok. (Je možné, že dáme v takovém případě možnost mimořádné opravy, pak už ale jen za 1 bod.)
     Zadání referátů: (stejné jako loni, budou přiděleny automaticky, dostanete email do 15.3.) 2011-referaty.pdf .
• Při nesplnění některé nutné podmínky student zápočet nedostane. (Za udělený zápočet tedy student získá minimálně 8 + 1 = 9 bodů, maximálně pak 24 + 11 = 35 bodů.)

Zkouška: písemná (90-minutová), podle potřeby doplněná ústní částí:
(max. zisk 65 bodů ; minimální zisk k uznanému absolvování: 25 bodů)
Ke zkoušce je možné jít jen po splnění požadavků k zápočtu.
Ukázka dávající přibližnou představu o závěrečné zkoušce je zde: 2008-ti-zk-uk.pdf

Možnost konzultací:

Průběh výuky (v LS 2012/13):

• Zde budou postupně přibývat informace o průběhu výuky po jednotlivých týdnech. Budu se snažit dávat plán dopředu, jak obsah přednášky, tak příklady na cvičení . Budou přiloženy i dříve použité slidy z přednášky, byť v současném běhu kurzu používány nebudou. Uvedené informace by měly být užitečné i pro studenty kombinovaného studia (pro získání rámcového přehledu). (Odkazujeme se k výše uvedenému studijnímu textu, pokud není uvedeno jinak.)
  Kdo si chce dopředu udělat rámcovou představu o celém průběhu kurzu, může se podívat např. sem:
  TI 2010/11 .

1. Týden od 11.2.: 01-tyden-2011.pdf , slidy-pr-01.pdf .
2. Týden od 18.2.: 02-tyden-2011.pdf , slidy-pr-02-ho.pdf . Jak je vysvětleno výše, ve čtvrtek 21.2.2013 se koná první rozšiřující přednáška (14:15 - 15:45, B5). (Možnost zisku bonusových bodů: kdo se první přihlásí [např. předem emailem] a předvede srozumitelně a kompletně důkaz tvrzení, že jazyk je regulární právě tehdy, když množina jeho levých kvocientů podle všech slov je konečná, tak může získat 5 bonusových bodů.)
3. Týden od 25.2.: 03-tyden-2011.pdf , slidy-pr-03-ho.pdf .
4. Týden od 4.3.: 04-tyden-2011.pdf , slidy-pr-04-ho.pdf . Ve čtvrtek 7.3.2013 se koná další rozšiřující přednáška (14:15 - 15:45, B5). (Úkol pro možnost zisku bonusových bodů zde přidám v pondělí 4.3. večer.) Úkol je tedy: Představme si dvoucestný konečný automat, čtecí hlava se nemusí posunout vždy doprava, ale může jít i vlevo či zůstat na místě. Instrukce nejsou tedy typu (q,a) --> q', ale typu (q,a) --> (q',s), kde s (shift) je -1,0, nebo +1. Ukažte, že přijímané jazyky jsou regulární. (Důkaz můžete někde vyhledat, ale musíte ho přesvědčivě vysvětlit.)
5. Týden od 11.3.: 05-tyden-2011.pdf , slidy-pr-05-ho.pdf .
6. Týden od 18.3.: 06-tyden-2011.pdf , slidy-pr-06-ho.pdf . Ve čtvrtek 21.3.2013 se koná další rozšiřující přednáška (14:15 - 15:45, B5).
7. Týden od 25.3.: 07-tyden-2011.pdf (slidy nejsou). V přiloženém starším zápisu je, že jsme se k Turingovým strojům nedostali, letos se ale k nim chci v této přednášce dostat.
8. Týden od 1.4.: Díky velikonočnímu pondělí se pochopitelně pondělní přednáška nekoná. Proto ve čtvrtek 4.4.2013 (14:15 - 15:45, B5) se místo rozšiřující přednášky koná standardní přednáška.
   Obsah víceméně odpovídá přiloženému materiálu. 08-tyden-2011.pdf , slidy-pr-08-ho.pdf .
9. Týden od 8.4.: 09-tyden-2011.pdf , slidy-pr-09-ho.pdf .
   Zpráva ohledně zápisu na zápočtovou písemku v Edisonu bude studentům zaslána v průběhu týdne.
10. Týden od 15.4.: 10-tyden-2011.pdf , slidy-pr-10-ho.pdf .
    Místo rozšiřující přednášky ve čtvrtek 18.4. (14.15 - 15.45) proběhne zápočtová (45-minutová) písemka
11. Týden od 22.4.: 11-tyden-2011.pdf , slidy-pr-13-ho.pdf . (Slidy zasahují i do dalších přednášek.)
12. Týden od 29.4.: Vzhledem k nepřehledné narušenosti výuky díky rektorským volnům a svátkům zde dávám zápisy z dřívějších běhů, které budu využívat ve zbylých třech týdnech semestru; rovněž cvičící je budou používat podle vlastního uvážení. (Poznámky typu "velikonoční pondělí" ve starých zápisech pochopitelně neodpovídají letošnímu běhu, zápisy se mohou překrývat, apod.)
    12-tyden-2011.pdf
    13-tyden-2011.pdf
    13-tyden-2010.pdf
    slidy-pr-14-ho.pdf .
    Na čtvrteční přednášce (2.5. ve 14.15 na B5) se budeme více věnovat aproximačním a pravděpodobnostním algoritmům.
13. Týden od 6.5.: Budou využívány materiály uvedené výše. Na cvičeních se také předpokládá konzultace možných nejasností u závěrečné písemky (její struktura je uvedena výše).
14. Týden od 13.5.: Budou využívány materiály uvedené výše.
    Na cvičeních proběhne prověření referátů.
    Na čtvrteční přednášce (16.5. ve 14.15 na B5) budou také přiblíženy některé pokročilejší partie teoretické informatiky (které jsou mj. plánovány pro podzimní volitelný kurs Vybrané partie teoretické informatiky).