Algoritmy a datové struktury: Porovnání verzí

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(Požadavky ke zkoušce)
Řádka 5: Řádka 5:
 
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š]].
 
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]
+
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://www.algovision.org Stránka s Algovision]
  
 
== Požadavky ke zkoušce ==
 
== Požadavky ke zkoušce ==

Verze z 24. 5. 2010, 12:10

Algoritmy a datové struktury
Kód předmětu: NTIN060
Přednáší: Luděk Kučera

Základní informace

Předměty Algoritmy a datové struktury I (TIN060) a Algoritmy a datové struktury II (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ů. 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

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

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í

Studijní materiály, odkazy