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
E371014 Z,ZK 5 2+2
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:

Basic introduction into Java (tasks can be solved in any language). Algorithms with numbers - Divide-and-conquer algorithms, Recurrence relations, the fast Fourier transform. Big-O notation. 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.

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:

Introduction into Java programming (all examples in Java).

Theory of algorithms. Complexity of algorithms. Big-O notation.

Mathematical algorithms - multiplication of two matrices, the greatest common divisor, the least common multiple ( LCM ) , Euclid's algorithm.

Factorial, recursion, factorization.

Divide-and-conquer algorithms, recurrence relations, the fast Fourier transform.

Sorting algorithms - bubble sort, combo sort, insert sort, selection sort, heap sort, quick sort, mergesort. Counting sort.

Data structures, linked lists (stack, circular queue), trees (binary, AVL, red-black; B-trees).

Graphs and graph algorithms - terminology, notation , theory, breadth-first search , BFS, depth-first search , DFS, minimum spanning tree.

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.

Cryptography - historical ciphers, search primes, factorization, symmetric ciphers.

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:
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 20. 6. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1066206.html