Algoritmy a programovací techniky

Datum vydání: 2011-03-01 11:58:13; aktualizováno: 2019-11-06 18:44:05

Ke knize jsou zdrojové soubory ke knize! Další materiály: Pavel Töpfer

Toto je základní literatura, podle které se probírá předmět Programování I - NPRG030 na Matematicko-fyzikální fakultě Univerzity Karlovy v Praze. I já jsem si kdysi touto literaturou prošla :).

Pavel Töpfer: Algoritmy a programovací techniky.

Obsah knihy

  1. Úvod
  2. Několik užitečných pojmů
  3. Složitost algoritmů
  4. Není číslo jako číslo
  5. Základní datové struktury
  6. Ukládání a vyhledávání údajů
  7. Seznamy prvků
  8. Prohledávání do hloubky a do šířky
  9. Práce s grafy
  10. Rozděl a panuj
  11. Třídění údajů
  12. Zpracování aritmetických výrazů
  13. Efektivita rekurzivních algoritmů
  14. Dynamické programování
  15. Techniky návrhu efektivních algoritmů
  16. Seznam programových ukázek
  17. Literatura
  18. Rejstřík

Podrobný obsah knihy:

  1. Úvod
  2. Několik užitečných pojmů
    • Množiny a posloupnosti
    • Stromy a grafy
    • Logaritmus
  3. Složitost algoritmů
    • Význam efektivity
    • Časová a paměťová složitost
    • Porovnávání algoritmů
    • Dodatky k otázce složitosti
  4. Není číslo jako číslo
    • Celá a reálná čísla
    • Zaokrouhlovací chyby
    • Ordinální datové typy
  5. Základní datové struktury
    • Pole, záznam, množina, řetězec
    • Vyhledávání v poli
    • Lineární spojový seznam
    • Dynamická reprezentace stromu a grafu
    • Objekty
  6. Ukládání a vyhledávání údajů
    • Pole příznaků
    • Seznamy prvků
    • Uspořádaný seznam prvků
    • Binární vyhledávací strom
    • Vyvážené binární stromy
    • 2-3-stromy
    • Hlada
    • Rozptýlené tabulky
  7. Seznamy prvků
    • Zásobník
    • Fronta
  8. Prohledávání do hloubky a do šířky
    • Procházení stromem a grafem
    • Procházení stavovým prostorem
    • Ořezávání a heuristiky
  9. Práce s grafy
    • Reprezentace grafu v programu
    • Komponenty souvislosti grafu
    • Topologické uspořádání
    • Hledání nejkratší cesty
    • Minimální kostra grafu
    • Bipartitní grafy
  10. Rozděl a panuj
    • Quicksort
    • Třídění sléváním
    • Hanojské věže
    • Vyhodnocení výrazu
  11. Třídění údajů
    • Algoritmy vnitřního třídění
    • Složitost vnitřního třídění
    • Přihrádkové třídění
    • Hledání K-tého nejmenšího prvku
    • Vnější třídění
  12. Zpracování aritmetických výrazů
    • Reprezentace aritmetického výrazu
    • Vyhodnocení aritmetického výrazu
    • Převody mezi aritmetickými notacemi
  13. Efektivita rekurzivních algoritmů
    • Fibonacciho čísla
    • Silniční daň
  14. Dynamické programování
    • Úloha o násobení matic
    • Úloha o triangulaci mnohoúhelníku
    • Úloha o cestování
  15. Techniky návrhu efektivních algoritmů
    • Odstranění opakovaných výpočtů
    • Přímé generování požadovaných údajů
    • Výpočet nové hodnoty na základě předchozí
    • Předzpracování vstupních dat
  16. Seznam programových ukázek
  17. Literatura
  18. Rejstřík