Editace stránky Algoritmy a datové struktury

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Varování: Nejste přihlášen(a). Pokud uložíte jakoukoli editaci, bude vaše IP adresa zveřejněna v historii této stránky. Pokud se přihlásíte nebo si vytvoříte účet, budou vaše editace připsány vašemu uživatelskému jménu a získáte i další výhody.

Editace může být zrušena. Zkontrolujte a pak potvrďte změny zobrazené níže.
Aktuální verze Váš text
Řádka 1: Řádka 1:
HY9HFX , [url=http://bsoocgeuzqdf.com/]bsoocgeuzqdf[/url], [link=http://vgfihjewvaci.com/]vgfihjewvaci[/link], http://umkkzezxrdso.com/
+
{{Předmět|Algoritmy a datové struktury|Luděk Kučera|TIN060}}
 +
 
 +
== Základní informace ==
 +
 
 +
Předměty '''Algoritmy a datové struktury I''' ({{SISPředmět|TIN060}}) a '''Algoritmy a datové struktury II''' ({{SISPředmět|TIN061}}) 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ů. [http://kam.mff.cuni.cz/~ludek/Algovision/Algovision.html Stránka s Algovision]
 +
 
 +
== Požadavky ke zkoušce ==
 +
 
 +
Požadavky se mohou mírně lišit u jednotlivých přednášejících
 +
 
 +
=== 1. semestr ===
 +
 
 +
 
 +
=== 2. semestr ===
 +
 
 +
* 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í
 +
 
 +
== Studijní materiály, odkazy ==
 +
 
 +
* [http://kam.mff.cuni.cz/~ludek/TIN060.html Studijni texty k 1. části] (Kučera)
 +
* [http://kam.mff.cuni.cz/~ludek/TIN061.html Studijní texty k 2. části] (Kučera)
 +
* [http://ktiml.mff.cuni.cz/~cepek/vyuka.html Slajdy od p. Čepka]
 +
* [http://download.matfyz.info/special/algoritmy/ Zápisky I] (Jan Procházka)
 +
* [http://download.matfyz.info/special/algoritmy2/ Zápisky II] (Jan Procházka)
 +
* [http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm Bitonické třídění] (anglicky)
 +
* [http://forum.matfyz.info/viewtopic.php?t=1802 Přepis přednášek p. Hrice k 1. části]
 +
* [http://www.sendme.cz/sklad/fourier/matematika/fourier_matematika.html Fourierova transformace] (pro ortodoxní matematiky)
 +
* [http://www.karlin.mff.cuni.cz/~tuma/2002/NLinalg12.pdf Fourierova transformace] (část skript p. Tůmy pro Lineární algebru)
 +
* [http://apfyz.upol.cz/ucebnice/down/mini/fourtrans.pdf Fourierova transformace] (Univerzita Palackého v Olomouci)
 +
* [http://www-igm.univ-mlv.fr/~lecroq/string/index.html Algoritmy pro vyhledávání v textech] - zdrojové kódy, vizualizace (anglicky)
 +
* [http://www.cs.vsb.cz/hlineny/vyuka/UTI-slides/UTI-text05.pdf Úvod do teoretické informatiky] - obsahuje NP-úplnost (Technická univerzita Ostrava)
 +
* [http://www.cs.vsb.cz/jancar/TEORET-INF/ANIMACE/Novak/ Animace k převoditelnosti] - 3-SAT, nezávislé množiny, barvení grafu, hamiltonovské kružnice, obchodní cestující (Technická univerzita Ostrava)
 +
* [http://forum.matfyz.info/viewtopic.php?t=1125 Starší studijní texty p. Kučery]
 +
* [http://tuetschek.wz.cz/schule/ads2.htm Stručné poznámky z II] (Tuetschek)
 +
* [http://mj.ucw.cz/vyuka/0607/ga/ Grafové algoritmy] - Skriptíčka k přednášce M. Mareše, která navazuje na ADS II (obsahuje Ford-Fulkersona a Dinice).
 +
* [http://www.osklivy-sup.cz/mff/dok/prednasky-kucera-zapisky.pdf Zápisky z přednášek o eVe (Kučera)]
 +
* [http://mff.modry.cz/datovky/zapisky/Lenka/ Zápisky z přednášek - Lenka]
 +
* [http://lucy.troja.mff.cuni.cz/labtf/poznamky/algoritmy.zip Zápisky z přednášek] (ZIP, 13 MB)
 +
* [http://www.mpi-sb.mpg.de/~mehlhorn/DatAlgbooks.html Mehlhorn: Data Structures and Algorithms] - 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ě)

Kliknutím na Save page

  • Potvrzujete, že vložené změny jsou vaším dílem, nebo jste oprávněni je zveřejnit a licencovat podle pravidel této stránky.
  • Potvrzujete, že smluvní podmínky níže uvedených licencí znáte a chápete, nebo se s nimi v nejbližší době seznámite.
  • Souhlasíte se zveřejněním svých změn podle licence MatfyzKing copyright
  • Souhlasíte se zveřejněním svých změn podle licence Creative Commons BY-NC-SA 2.0
  • Souhlasíte se zveřejněním svých změn podle licence GNU GFDL

Nevkládejte cizí díla bez prokazatelného souhlasu autora nebo držitelů práv!

Storno | Pomoc při editování (otevře se v novém okně)