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

Algorithms for Engineering Informatics

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
E371526 Z,ZK 4 2+1
Přednášející:
Josef Kokeš (gar.), Vladimír Hlaváč
Cvičící:
Josef Kokeš (gar.), Vladimír Hlaváč
Předmět zajišťuje:
ústav přístrojové a řídící techniky
Anotace:

Big-O notation. Algorithms with numbers - Cryptography, Universal hashing, Divide-and-conquer algorithms, Recurrence relations, the fast Fourier transform. Sorting algorithms - Mergesort, Insert sort, Selection sort, Heap sort, Quick sort. Graphs - Depth-fit search in undirected graph, Depth-fit search in directed graphs, Strongly connected components. Paths in graphs - Distances, Breadth-first search, Lengths on edges, Dijkstra's algorithm, Priority queue implementations, Shortest paths in the presence of negative edges, Shortest paths in dags. Greedy algorithms - Minimum spanning trees, Huffman encoding, Horn formulas.

Požadavky:

Předmět nezbytně předpokládá předběžné znalosti na úrovni předmětu Algoritmy 1.

Ke zkoušce jsou předepsány znalosti v rozsahu přednášek. Zkouška je praktická a ústní. Praktická část zkoušky - napsat a odladit jednoduchý program z odpřednášeného učiva.

Na cvičení studenti obdrží zadání 3 příkladů k vypracování.

Osnova přednášek:

Teorie algoritmů, Složitost algoritmu

Matematické algoritmy

Násobení dvou matic

Největší společný dělitel

Nejmenší společný násobek (lcm), Euklidův algoritmus

Faktoriál, Rekurze, Faktorizace

Fibonacciho posloupnost

Fisher-Yatesův algoritmus

Grafy a grafové algoritmy

Terminologie, zápis, teorie

Prohledávání do šířky, BFS

Prohledávání do hloubky, DFS

Minimální kostra grafu

Topologické uspořádání, Floydův algoritmus

Hledání v textu

Terminologie, Hammingova vzdálenost

Triviální algoritmus

KMP

Kryptografie

Historické šifry

Hledání prvočísel, Faktorizace

Symetrické šifry

Kvantová kryptografie

Osnova cvičení:

Spouštění programů v učebně, konta a zadání úloh

Jednoduchý program

Číselné proměnné

Podmíněný příkaz. Timer.

Pole, cyklus, konstanty (i typované)

Texty, opendialog, a ...

Cykly, náhodné proměnné, třídění.

Druhé okno programu, další komponenty.

OnMouseMove, Canvas.

Canvas - psaní textů, obdélníky, graf funkce.

Tisk z programů v Javě.

Dynamické datové struktury. Úspora místa, zásobník, fronta, řetěz, tabulka, strom.

Cíle studia:

Předmět seznamuje s pokročilými algoritmy.

Výuka je zaměřena spíše prakticky, na aplikaci algoritmů při řešení inženýrských úloh. Příklady jsou prezentovány v jazyce Java.

Studijní materiály:

Doporučené studijní materiály jsou uvedeny v sylabech, které jsou k dispozici na ????? v sekci „Téma 01“

Poznámka:

Platí od ZS 2014/15

Další informace:
???? katedrální stránka předmětu http://www.compileonline.com
Rozvrh na zimní semestr 2018/2019:
Rozvrh není připraven
Rozvrh na letní semestr 2018/2019:
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
Čt
místnost T4:C1-308
Hlaváč V.
17:45–19:15
(přednášková par. 1)
Dejvice
Laboratoř 12110.3 - 308
místnost T4:C1-308
Hlaváč V.
19:30–20:15
(přednášková par. 1
paralelka 1)

Dejvice
Laboratoř 12110.3 - 308

Předmět je součástí následujících studijních plánů:
Platnost dat k 16. 2. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet2096906.html