Algoritmy a datové struktury

Z ωικι.matfyz.cz
Verze z 12. 5. 2008, 13:40, kterou vytvořil 85.207.168.2 (diskuse) (Základní informace)

Přejít na: navigace, hledání
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

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