Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35 Matfiz : Složitost
Přihlášení:  Heslo:  
Matfiz: Složitost ...
Hlavní Stránka | Seznam Stránek | Poslední Změny | Poslední Komentované | Uživatelé | Registrace |

Složitost I


Vyučující: Ondřej Čepek (web se slajdy)


Předmět má za cíl «naučit základy z teorie složitosti algoritmů, včetně NP-úplnosti a převoditelnosti». Jedná se o přednášku se cvičeními ob týden.

Info z první přednášky

Cvičení jsou od druhého týdne.

Materiály

Staré (kompletní) slajdy na webu se neshodují se současným sylabem a budou průběžně aktualizované. Při zobrazení v OpenOffice.org jsou navíc poměrně velké části některých současných slajdů prázdné, přednášející slíbíl, že tam umístí i PDF. Update: V OOo 3.1.1 už je to v pořádku, jen je třeba mít správný (resp. špatný) font Symbol (takový co odpovídá Microsoftímu), aby se Vám zobrazily všechny symboly. Tak pozor na to.

Přehled NP-úplných úloh

Jestli máte občas trochu zmatek, jak přesně vypadá zadání které z běžných NP-úplných úloh, popletete jednu s druhou nebo nemáte spojené české a anglické názvy, pomůže vám tento přehled (používám v něm stejné legrační zkratky jako Čepek):



Pozor: Je to jen velmi orientační. Míchám optimalizační verze a rozhodovací verze a bylo by dobré pro úplnost popsat přesně vše a doplnit další souvislosti a vlastnosti problémů (asi v tabulce). Klidně se toho můžete někdo zhostit:).


 
Na stránce nejsou žádné soubory. [Zobrazit soubory (formulář)]
Komentáře [Skrýt komentáře (formulář)]