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

Přednášející: prof. Petr Jančar (A1046), Petr.Jancar@vsb.cz ,
cvičící: doc. Petr Šaloun Petr.Saloun@vsb.cz , doc. Zdeněk Sawa Zdenek.Sawa@vsb.cz , Ing. Martin Kot Martin.Kot@vsb.cz , Ing. Ondřej Meca Ondrej.Meca@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í):

• 27.6.2014. Pro jistotu (a případné dotazující se) dodávám, že další zkouškové termíny už v nynějším zkouškovém období nebudou.
• 26.6.2014. Opravené zkouškové písemky z 26.6. budou k nahlédnutí 27.6. v době 15.30-16.30. Místo: EA414 (Jančar) . (V Edisonu by měly být výsledky 27.6. kolem poledne.)
• 12.6.2014. Opravené zkouškové písemky z 12.6. budou k nahlédnutí 16.6. v době 16-17. Místo: EA414 (Jančar) . (V Edisonu by měly být výsledky 13.6.večer.)
• 3.6.2014. Opravené zkouškové písemky z 29.5. budou k nahlédnutí dnes, 3.6. po 17. hod. (v době 17-18.30) , jak bylo avizováno při zkoušce. Místo: EA414 (Jančar) .
• 19.5.2014. Opravný termín pro referáty (za 1 bod, jak vysvětleno v podmínkách níže) je 29.5. ve 14.00 (s koncem v 15.30) na EA413 a EA414 ; tento termín je určen i jako náhradní termín pro ty studenty, kteří byli řádně omluveni z řádného termínu. (Tento termín je tedy dvě hodiny před prvním termínem zkoušky.)
• 9.5.2014. - V Edisonu jsou již vypsány termíny zkoušky ve zkouškovém období. Zapište se vždy co nejdříve, nejpozději dopoledne předchozího dne!
  - V Edisonu je také vypsán termín náhradní/opravné zápočtové písemky (19.5.).
  - Rozšiřující přednáška ve čtvrtek 15.5. již nebude. (Je možné, že se daný čas využije k prověřování referátů, nestihne-li se na cvičeních.)
• 9.5.2014. Jak bylo avízovano dříve, pro studenty, kteří se hlásí k SZZ v 6/2014, bude speciální zkouškový termín, a sice ve středu 14.5.2014, v 16.00 na C3. (V Edisonu tento termín není, studenti se tam na něj nepřihlašují, ale ohlásí se mailem pí Geletičové [nejpozději 12.5.], která nám oprávněnost účasti na uvedeném mimořádném termínu potvrdí.)
• 30.4.2014. Na konci zápočtového týdne nebo v prvním týdnu zkouškového období bude vypsán 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ů.)
• 22.4.2014. Referáty budou prověřovány na cvičeních v zápočtovém týdnu 12.-16.5.2014. Studenti, kteří půjdou v červnu 2014 k SZZ, mají možnost splnit úkol referát na cvičeních v pondělí 12.5. odpoledne (i když jejich řádné cvičení je v týdnu později). Výhradně pro tyto studenty (tedy pro ty, kteří se hlásí k SZZ v 6/2014) bude vypsán speciální zkouškový termín, a sice ve středu 14.5.2014 odpoledne (čas a místnost budou upřesněny později). (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í.)
• 14.3.2014. Zápočtová písemka proběhne 17.4.2014 (viz Průběh výuky). Bude nutný zápis v Edisonu. Konkrétní termíny k zápisu posluchačů budou vypsány v Edisonu do konce března.
• 13.3.2014. Níže bylo přidáno zadání referátů; studentům byl zaslán email, jak bylo také avízovano níže.
• 3.2.2014. Čtvrteční přednáška
  P/01 Sudý Čt 12:30 - 14:00 2 PORB5
  je doplňující přednáška (konající se v sudé týdny, první tedy 20.2., jelikož je to 8. (a tedy sudý) 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 2013/14):

• 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 2012/13 .

1. Týden od 10.2.: 01-tyden-2011.pdf , slidy-pr-01.pdf . (Jsou zde většinou uloženy zápisy z dřívějších běhů, pokud bude ve skutečnosti na přednášce něco výrazně nového/jiného, napíšu to zde přímo.)
2. Týden od 17.2.: 02-tyden-2011.pdf , slidy-pr-02-ho.pdf .
   Ve čtvrtek 20.2.2014 se koná první rozšiřující přednáška (12:30 - 14:00 B5). V té souvislosti je 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ů. Musí toto ovšem mít podloženo svým vlastním textem.
3. Týden od 24.2.: 03-tyden-2011.pdf , slidy-pr-03-ho.pdf .
4. Týden od 3.3.: 04-tyden-2011.pdf , slidy-pr-04-ho.pdf . Ve čtvrtek 6.3.2014 se koná další rozšiřující přednáška (12:30 - 14:00, B5). Možnost dalších 5 bonusových bodů (jako výše): 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 10.3.: 05-tyden-2011.pdf , slidy-pr-05-ho.pdf .
6. Týden od 17.3.: 06-tyden-2011.pdf , slidy-pr-06-ho.pdf . Ve čtvrtek 20.3.2014 se rozšiřující přednáška nekoná (děkanské volno, otevření nové budovy FEI).
7. Týden od 24.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 31.3.: Díky rektorskému volnu se v pondělí přednáška nekoná. Proto ve čtvrtek 3.4.2014 (12:30 - 14:00, B5) se místo rozšiřující přednášky koná standardní přednáška, věnovaná zejména modelu RAM.
   08-tyden-2011.pdf , slidy-pr-08-ho.pdf .
9. Týden od 7.4.: 09-tyden-2011.pdf , slidy-pr-09-ho.pdf .
10. Týden od 14.4.: 10-tyden-2011.pdf , slidy-pr-10-ho.pdf .
    Místo rozšiřující přednášky ve čtvrtek 17.4. (od 12.30) proběhne zápočtová (45-minutová) písemka. (Konkrétní termíny k zápisu posluchačů budou vypsány v Edisonu do konce března.)
11. Týden od 21.4.: (velikonoční pondělí) 11-tyden-2011.pdf , slidy-pr-13-ho.pdf . (Obsah zhruba odpovídá cvičení. Text i slidy zasahují i do dalších přednášek, mj. vzhledem k nekonání přednášky v tomto týdnu apod.)
12. Týden od 28.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 .
13. Týden od 5.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 12.5.: Budou využívány materiály uvedené výše.
    Na cvičeních proběhne prověření referátů.
    Rozšiřující přednáška ve čtvrtek 15.5. již nebude. (Je možné, že se daný čas využije k prověřování referátů, nestihne-li se na cvičeních.)