Algoritmy a datové struktury
From ωικι.matfyz.cz
| Algoritmy a datové struktury | ||||
|
| Table of contents |
[edit]
Základní informace
Předměty Algoritmy a datové struktury I (TIN060 (http://is.cuni.cz/studium/predmety/index.php?do=predmet&kod=NTIN060)) a Algoritmy a datové struktury II (TIN061 (http://is.cuni.cz/studium/predmety/index.php?do=predmet&kod=NTIN061)) vyučují Luděk Kučera, Jan Hric, Ondřej Čepek a Martin Mareš.
Zásadní pomůckou při studiu těchto předmětů je sada Java appletů Algovision, což je grantový projekt realizovaný profesorem Kučerou. Jedná se o hezkou vizualizaci většiny probíraných algoritmů. Stránka s Algovision (http://www.algovision.org)
[edit]
Požadavky ke zkoušce
Požadavky se mohou mírně lišit u jednotlivých přednášejících
[edit]
Algoritmy a datové struktury I
- popis složitosti algoritmů a operací nad datovými strukturami:
- měření velikosti dat, počet kroků algoritmu jako funkce velikosti dat
- asymptotická notace
- Stromové datové struktury:
- binární vyhledávací stromy
- AVL stromy
- červeno-černé stromy
- třídění:
- analýza průměrného případu pro Quicksort, randomizovaný Quicksort
- dolní odhad složitosti porovnávacích třídících algoritmů (rozhodovací stromy)
- třídění v lineárním čase na základě adresování pomocí klíčů (víceprůchodové pro znakové klíče)
- základní grafové algoritmy:
- DFS, BFS
- hledaní komponent souvislosti
- prohledávání do hloubky na orientovaném grafu, tranzitivní uzávěr, topologické číslování
- cesty v grafech:
- cesty v DAG
- Dijkstra
- Bellman-Ford
- minimální kostra grafu:
- Borůvka-Kruskal
- Jarník-Prim
- hashování:
- popis jednoduchých strategií řešení kolizí
- analýza časové složitosti vyhledávání v průměrném případě
- algoritmy rozděl a panuj:
- substituční metoda řešení rekurentních rovnic, master theorem
- binární vyhledávání a mergersort
- Strassenovo násobení matic
- algoritmy lineární algebry:
- Euklidův algoritmus
- LUP dekompozice matic
[edit]
Algoritmy a datové struktury II
- sčítání (carry look-ahead)
- vyhledávání řetězců
- Knuth-Morris-Pratt
- Aho-Corasick
- Rabin-Karp
- toky v sítích
- Ford-Fulkerson
- Dinitz
- Goldberg (preflow-push)
- Fourierova transformace
- diskrétní (DFT)
- rychlá (FFT) - přímá i inverzní
- konvexní obal v 2D
- Voronoi diagram v 2D
- třídící sítě
- převoditelnost problému, P a NP úlohy
- 3-SAT - splnitelnost formule
- 3-barevnost grafu
- nezávislá množina grafu
- pravděpodobnostní algoritmy
- algoritmy typu Monte Carlo
- algoritmy typu Las Vegas
- kryptografie, asymetrické šifrování, RSA
- aproximační algoritmy
- dynamické programování
[edit]
Studijní materiály, odkazy
- Java applety (http://people.ksp.sk/~kuko/bak/big/) - AVL stromy, Červeno-černé stromy, BVS, ...
- Studijni texty k 1. části (http://kam.mff.cuni.cz/~ludek/TIN060.html) (Kučera)
- Studijní texty k 2. části (http://kam.mff.cuni.cz/~ludek/TIN061.html) (Kučera)
- Slajdy od p. Čepka (http://ktiml.mff.cuni.cz/~cepek/vyuka.html)
- Zápisky I (http://download.matfyz.info/special/algoritmy/) (Jan Procházka)
- Zápisky II (http://download.matfyz.info/special/algoritmy2/) (Jan Procházka)
- Bitonické třídění (http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm) (anglicky)
- Přepis přednášek p. Hrice k 1. části (http://forum.matfyz.info/viewtopic.php?t=1802)
- Fourierova transformace (http://www.sendme.cz/sklad/fourier/matematika/fourier_matematika.html) (pro ortodoxní matematiky)
- Fourierova transformace (http://www.karlin.mff.cuni.cz/~tuma/2002/NLinalg12.pdf) (část skript p. Tůmy pro Lineární algebru)
- Fourierova transformace (http://apfyz.upol.cz/ucebnice/down/mini/fourtrans.pdf) (Univerzita Palackého v Olomouci)
- Algoritmy pro vyhledávání v textech (http://www-igm.univ-mlv.fr/~lecroq/string/index.html) - zdrojové kódy, vizualizace (anglicky)
- Úvod do teoretické informatiky (http://www.cs.vsb.cz/hlineny/vyuka/UTI-slides/UTI-text05.pdf) - obsahuje NP-úplnost (Technická univerzita Ostrava)
- Animace k převoditelnosti (http://www.cs.vsb.cz/jancar/TEORET-INF/ANIMACE/Novak/) - 3-SAT, nezávislé množiny, barvení grafu, hamiltonovské kružnice, obchodní cestující (Technická univerzita Ostrava)
- Starší studijní texty p. Kučery (http://forum.matfyz.info/viewtopic.php?t=1125)
- Stručné poznámky z II (http://tuetschek.wz.cz/schule/ads2.htm) (Tuetschek)
- Grafové algoritmy (http://mj.ucw.cz/vyuka/0607/ga/) - Skriptíčka k přednášce M. Mareše, která navazuje na ADS II (obsahuje Ford-Fulkersona a Dinice).
- Zápisky z přednášek o eVe (Kučera) (http://www.osklivy-sup.cz/mff/dok/prednasky-kucera-zapisky.pdf)
- Zápisky z přednášek - Lenka (http://mff.modry.cz/datovky/zapisky/Lenka/)
- Zápisky z přednášek (http://lucy.troja.mff.cuni.cz/labtf/poznamky/algoritmy.zip) (ZIP, 13 MB)
- Mehlhorn: Data Structures and Algorithms (http://www.mpi-sb.mpg.de/~mehlhorn/DatAlgbooks.html) - V druhém díle Mehlhorna (ke stažení) je dokázována NP-úplnost pro celou řadu problémů (mělo by to být někde ve druhé polovině, v elektronické verzi jsem to ale nemohl najít, na MS je jedna kopie v knihovně)
- Základní grafové algoritmy (Jakub Černý) (http://kam.mff.cuni.cz/~kuba/ka)
