Algorithms for Engineering Informatics

Garant předmětu:

Přednášející:

Cvičící:

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

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů: