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:

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 - bubble sort, insert sort, selection sort, heap sort, quick sort, mergesort. Graphs - depth-first search in undirected graph, depth-first 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 (directed acyclic graphs). 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 Moodle 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ů: