Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2020/2021

Pokročilá algoritmizace

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
F7PMIPAZ Z,ZK 5 2P+2C česky
Přednášející:
Pavel Smrčka (gar.)
Cvičící:
Pavel Smrčka (gar.)
Předmět zajišťuje:
katedra informačních a komunikačních technologií v lékařství
Anotace:

Cíl předmětu je seznámit studenty s problematikou algoritmizace a základů teoretické informatiky. Studenti se seznámí s metodami návrhů algoritmů, určení jejich složitosti, s grafovými a optimalizačními algoritmy. V předmětu budou popsány běžné využívané datové struktury a způsoby jejich implementace. Přednášky budou také věnované formálním jazykům a automatům. Důležitou součástí cvičení je samostatná implementace datových typů a algoritmů přednášky.

Požadavky:

Podmínky zápočtu jsou absolvování čtyř praktických testů s celkovým ziskem alespoň 50 % bodů a odevzdání zápočtové úlohy. Zkouška má písemnou část, která se skládá z převážně teoretických otázek s následním ústním dozkoušení v rozsahu odpřednášené a odcvičené látky.

Požadavky na studenty: Povinná účast na cvičeních (max. 2 absence).

Osnova přednášek:

1.Techniky algoritmizace - metoda top down, bottom-up, rozděl a panuj, žravý algoritmus, rekurze, dynamické programování. Výpočetní modely.

2.Abstraktní datové typy; agregace a systematizace znalostí. Zásobník, fronta, seznam atd. a jejich efektivní implementace. Zopakování základních metod řazení a vyhledávání.

3.Složitost algoritmů - časová a paměťová náročnost, asymptotická časová složitost, třídy složitosti.

4.Grafy. Základní pojmy, možnosti reprezentace pomocí datových struktur. Minimální kostra grafu, minimální cesta v grafu.

5.Algoritmy průchodů grafem - prohledávání do hloubky a do šířky, heuristické metody prohledávání.

6.Binární vyhledávací stromy. Základní pojmy a operace, vyhledávání, vkládání, rušení vrcholů, průchody stromem.

7.Vyvážené a vícecestné stromy. AVL-stromy, red-black stromy. B-stromy. Haldy.

8.Hešovací tabulka, řešení kolizí - zřetězení, otevřená adresace, perfektní hešování. Kešování. Asociativní pole.

9.Dynamická alokace paměti. Pointery, operátory reference, dereference, alokování a dealokování paměti. Fragmentace paměti.

10.Garbage collector, principy a srovnání základních algoritmů - reference counting algoritmy, tracing algoritmy.

11.Formální jazyky - základní pojmy (abeceda, slovo, jazyk). Operace na jazycích. Druhy gramatik. Konečné automaty. Deterministický a nedeterministický konečný automat. Turingův stroj.

12.Algoritmy numerické matematiky ? přehled a příklady aplikací.

13.Algoritmy optimalizace. Lineární programování. Formulace problému, přehled metod. Grafická metoda řešení, Simplexová metoda.

14.Dynamické programování. Bellmanův princip optimality. Souvislost s rekurzí, příklady užití, Floydův-Warshallův algoritmus.

Osnova cvičení:

Důležitou součástí cvičení je samostatná implementace datových typů a algoritmů přednášky.

Cíle studia:

Cíl předmětu je seznámit studenty s problematikou algoritmizace a základů teoretické informatiky. Studenti se seznámí s metodami návrhů algoritmů, určení jejich složitosti, s grafovými a optimalizačními algoritmy.

Studijní materiály:

Povinná literatura:

[1] SEDGEWICK, Robert. Algoritmy v C. Praha: SoftPress, 2003. ISBN 80-86497-56-9.

[2] WRÓBLEWSKI Piotr.: Algoritmy. Datové struktury a programovací techniky, Computer Press, Praha, druhé vydání 2015, ISBN 80-251-0343-9

Doporučená literatura:

[3] SKIENA, Steven S. The algorithm design manual. 2nd ed. London: Springer, c2008. ISBN 978-1-84800-069-8.

Poznámka:
Rozvrh na zimní semestr 2020/2021:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St
místnost AL:101
Smrčka P.
10:00–12:50
(přednášková par. 1)
Praha 2 - Albertov
Albertov - učebna
místnost AL:101
Smrčka P.
13:00–16:50
(přednášková par. 1
paralelka 1)

Praha 2 - Albertov
Albertov - učebna
Čt

Rozvrh na letní semestr 2020/2021:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 27. 9. 2020
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet5585906.html