Informace ke kursu Vyčíslitelnost a složitost (LS 2005/2006)

(přednášející: doc. Petr Jančar (A1024), Petr.Jancar@vsb.cz , cvičící: Ing. Zdeněk Sawa, Zdenek.Sawa@vsb.cz )

Aktualni informace:

Studijní opora:

Zakladni studijni pomuckou ke kursu je pracovni text, jenz je zde ulozen jako jako pdf-soubor (rozsah: 67 stran, ale vzdy 2 stranky textu na jedne strane A4):
vycsloz-2p.pdf .
Tento materiál je součástí textu "P.Jančar: Studijní opora k předmětům teoretické informatiky" odkazovaný na stránkách kursu
Teoretická informatika .
Tam rovněž naleznete odkaz na pracovní text doc. Hliněného k Úvodu do teoretické informatiky, který také doporučuji (v našem případě tedy speciálně část věnovanou vyčíslitelnosti a složitosti.)

Jen procteni textu nestaci k zvladnuti obsahu kursu, nicmene je z nej mozne ziskat podrobnejsi predstavu o naplni jednotlivych prednasek a mj. nam take usetri nudne opisovani technickych definic apod. (ty pak budou na prednaskach jen promitany s tim, ze se predpoklada, ze posluchac je ma k dispozici prave diky pracovnimu textu, a díky slidům přikládaným k přednáškám, jak je zmíněno níže).

Samozrejme uvitam jakekoli poznamky k textu, specialne upozorneni na chyby, preklepy a nejasnosti (zaslane treba emailem na Petr.Jancar@vsb.cz ).

Prehled kursu:

Cile kursu se daji zhruba vyjadrit nasledovne. Absolvent má získat hlubší (teoretický) základ pro pojmy složitosti algoritmů a problémů, i pro jejich analýzu (odhady) u konkrétních případů -- mj. u algoritmů navrhovaných obecnými metodami (prohledávání, ``rozděl a panuj'', `greedy' přístup, dynamické programování). Dále má zvládnout klasifikaci typických (praktických) problémů vzhledem k základním třídám složitosti (PTIME, NPTIME, PSPACE, ...), včetně prokázání případné nerozhodnutelnosti problému. Rovněž má získat představu, podloženou pochopením konkrétních příkladů, o problematice aproximačních, pravděpodobnostních, paralelních a distribuovaných algoritmů. Obsah kursu je nastinen v nasledujicich bodech (podrobnejsi a presnejsi predstavu si ovsem lze udelat prohlednutim obsahu uvedeneho na zacatku pracovniho textu):
  1. Úvod ke kursu. Složitost algoritmu. Model RAM.
  2. Odhady složitosti. Nejhorší vs. průměrný případ. Analýza vybraných algoritmů. Metoda `rozděl a panuj'.
  3. Analýza dalších algoritmů. `Greedy' algoritmy. Metoda dynamického programování.
  4. Problémy, třídy složitosti problémů, horní a dolní odhady. Turingův stroj.
  5. Turingovy stroje a další výpočetní modely; jejich vzájemná `polynomiální' simulace.
  6. Třída P (=PTIME) jako aproximace třídy prakticky zvládnutelných problemů. Třída NP (=NPTIME). Polynomiální převeditelnost. NP-úplnost.
  7. NP-úplné problémy. Otevřená otázka, zda P=NP.
  8. Další třídy časové i prostorové složitosti a jejich vzájemné vztahy. Dokazatelně nezvládnutelné problémy.
  9. Church-Turingova teze. Rozhodnutelnost a částečná rozhodnutelnost problémů. Univerzální algoritmus (Turingův stroj). Rekurzivní a rekurzivně spočetné množiny (jazyky). Rekurzivní a částečně rekurzivní funkce.
  10. Metoda diagonalizace. Nerozhodnutelnost problému zastavení. Další nerozhodnutelné problémy. Riceova věta.
  11. Další témata teorie a praxe algoritmů. (Aproximační algoritmy, pravděpodobnostní algoritmy, paralelní algoritmy, distribuované algoritmy; nové výpočetní modely.)

Prubeh cviceni, referaty:

Rámcově si lze udělat předběžnou představu o průběhu cvičení prohlédnutím následujícího souboru

cvic-vycsloz-2p.pdf .

Cvičící ovšem konkrétní obsah jednotlivých cvičení upřesní podle aktuální potřeby. (viz take Prubeh semestru nize)

Predpoklada se, ze se posluchaci na cviceni snazi predem pripravit . Vyznamnou cast cviceni budou tvořit referáty studentů, jimz bude prislusny referat pridelen (viz nize).

Zapocet:

Podminkou k ziskani zapoctu je aktivni ucast na zpracovani referatu a na jeho prezentaci na prislusnem cviceni. To se tyka i studentu, kteri jiz meli zapocet udelen v drivejsich bezich kursu ! Referaty budou prideleny na prvnim cviceni v semestru, opozdilcum pak i v prubehu dvou dalsich tydnu. Kazdy posluchac se o referat musi aktivne prihlasit, jinak se ma zato, ze kurs nehodla absolvovat (byt je na nej zapsan). (V nezbytnem pripade musi cviciho kontaktovat alespon emailem.)

Jeden referat bude pridelen nekolika studentum zaroven (podle poctu studentu v prislusne skupine) k samostatnemu ci spolecnemu zpracovani a zreferovani (vysvetleni na cviceni). Referujici posluchaci musi cvicicimu (pri cviceni, kdy je na poradu jejich referat) odevzdat radne pisemne (vytistene) nekolikastrankove zpracovani tematu referatu - podepsane vsemi autory. Toto zpracovani musi byt ucelenym (samostatne citelnym) textem, ktery muze vyuzivat poskytnutych podkladu, ale nemuze byt pouhym jejich opisem ! Velmi zadouci (byt ne nezbytna) je take elektronicka forma referatu (u niz je preferovan TeX, byt opet neni nutnou podminkou) -- ta muze byt cvicicimu zaslana i dodatecne.

Vsichni autori musi pri referovani prokazat skutecne porozumeni tematu; v pripade problemu (vcetne opodstatnene neucasti jednoho z autoru, nemoc apod.) urci cvicici formu dodatecnych odstraneni nejasnosti.

Za (jednoznacne dostacujici) splneni uvedeneho ukolu, a tedy pri udeleni zapoctu, bude kazdemu posluchaci prideleno 20 bodu.

Referaty:
(je možné si stáhnout a využít přiložené podklady k referátům (kromě případu referátu 1); jedna se o kopie z knih uvedenych v seznamu literatury v pracovnim textu, neni-li uvedeno jinak)

  1. Naprogramujte hlavni jadro algoritmu Heapsort pro RAM a analyzujte jeho casovou slozitost.
  2. Analyza slozitosti algoritmu Quicksort v prumernem pripade. (Optimalni) dolni odhad pro problem trideni.
    ref2a.pdf (z knihy Matoušek, Nešetřil: Kapitoly z diskrétní matematiky)
    ref2b.pdf (z [Kuc83])
  3. Strassenuv algoritmus pro nasobeni matic.
    ref3.pdf (z [CLR90])
  4. Algoritmus (Cocke-Younger-Kasami) pro rozpoznavani bezkontextovych jazyku (aplikace metody dynamickeho programovani).
    ref4.pdf (z [HU79])
  5. Detailni vyklad vzajemne simulace Turingova stroje a stroje RAM.
    ref5.pdf (z knihy Gruska: Foundations of Computing)
  6. Polynomialni preveditelnost problemu nezavisle mnoziny na problem hamiltonovskeho cyklu.
    ref6.pdf (z [Kuc83])
  7. Detailni popis konstrukce v dukazu Cookovy vety.
    ref7-1.jpg , ref7-2.jpg (z [HU79])
  8. Podrobny popis konstrukce v dukazu Savitchovy vety.
    ref8.pdf (z [HU79])
  9. Konstrukce univerzalniho Turingova stroje.
    ref9.pdf (z [HU78])
  10. Konstrukce v dukazu preveditelnosti problemu zastaveni na Postuv korespondencni problem (cimz se prokaze nerozhodnutelnost PKP).
    ref10.pdf (z [HU78])

Zkouska:

Ve zkouskovem obdobi budou moci posluchaci s udelenym zapoctem napsat zaverecny test, ze ktereho bude mozne ziskat az 80 bodu (k onem 20 bodum za zapocet). Celkove hodnoceni je standardni (86-100 vyborne, 66-85 velmi dobre, 51-65 dobre, 0-50 nevyhovel).

Ilustracni test , ktery muze dat urcitou predstavu o tom, jak zhruba muze zaverecny test vypadat, najdete zde (skutecny bude vypadat samozrejme trochu jinak; napr. i v tom, ze bude mozne ziskat 80 bodu, nikoli 100):

ilust_00.pdf

Moznost konzultaci:

Zajemci se nejprirozeneji mohou domluvit s prednasejicim ci cvicicim po prednasce ci cviceni nebo jinak nejlepe emailovym kontaktem. Take je mozne vyuzit oficialnich konzultacnich hodin vyucujicich (i kdyz i to je lepsi po predchozi domluve).

Doporucena literatura (krome stud. textů uvedených výše):

Knihy v češtině a slovenštině pokrývající alespoň části přednášené látky jsou např. tyto

Partie z teorie složitosti (včetně konkrétních algoritmů a problémů) najdeme v knihách

Další partie (jako Turingovy stroje, problém zastavení, zavedení výpočtové složitosti aj.) jsou pokryty v knihách Dále např. 1.kapitola knihy Podstatně bohatší je literatura v angličtině. Z ní je možné doporučit např. (V pracovnim textu je uvedena i dalsi literatura.)

Průběh semestru (LS 2005/06)

V tomto akademickém roce je průběh výuky ovlivněn skutečností, že (každotýdenní dvouhodinová) přednáška je společná kursům "Vyčíslitelnost a složitost" a "Teoretická informatika" (TI). TI má přednášku čtyřhodinovou, přičemž vyčíslitelnosti a složitosti se týká vždy druhá dvouhodina (10.45 - 12.15); ta je právě určena i pro posluchače kursu "Vyčíslitelnost a složitost".

Přednášky

Vzhledem k výše uvedenému odkazuji pro přehled o přednáškách (včetně souborů se slidy) opět na
Teoretická informatika .

Cvičení

Průběh cvičení bude určovat cvičící; obsah bude rámcově odpovídat plánu uvedeném v příslušném výše uvedeném souboru.