Algoritmizace - NPRG062

• Anglický název: Introduction to Algorithms
• Zajišťuje: Katedra softwaru a výuky informatiky (32-KSVI)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• Semestr: zimní
• E-Kredity: 4
• Rozsah, examinace: zimní s.:2/1, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: doc. RNDr. Tomáš Dvořák, CSc.; doc. RNDr. Pavel Töpfer, CSc.; Adam Dingle, M.Sc.
• Korekvizity : NPRG030
• Neslučitelnost : NMIN102, NMIN112
• Je korekvizitou pro: NPRG030
• Je neslučitelnost pro: NMIN112

Anotace

čeština

Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (30.10.2019)

Úvodní kurz základních algoritmů, složitosti algoritmů a datových struktur pro posluchače prvního ročníku bakalářského studia informatiky a učitelství informatiky.

angličtina

Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (30.10.2019)

An introductory course on fundamental algorithms, algorithmic complexity and data structures for first-year students of computer science and computer science education.

Podmínky zakončení předmětu

čeština

Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (17.09.2019)

Předmět je zakončen zápočtem a zkouškou. Podmínkou pro přihlášení ke zkoušce je předchozí získání zápočtu.

K získání zápočtu se požaduje aktivní účast na cvičeních a úspěšné vyřešení úkolů v termínech stanovených cvičícím. Povaha tohoto požadavku neumožňuje vypsat opravné termíny. Vyučující může stanovit podmínky, za nichž student může nahradit chybějící domácí úkoly.

Zkouška má písemnou a ústní část. Na zkoušku je jeden řádný a dva opravné termíny.

angličtina

Poslední úprava: RNDr. Tomáš Holan, Ph.D. (20.10.2022)

The course is concluded with a credit and a final exam. Obtaining a credit is a necessary prerequisite for an enrollment for the final exam.

The credit is awarded upon successfully completing the following requirements:

• active participation in tutorials

• obtaining a required score from homework assignments submitted by the deadline specified by the instructor

Due to the nature of the requirements, a failed attempt cannot be repeated as is possible for exams. The instructor may specify conditions whereby a student can make up for missing homework assignments.

The final exam consists of a written and an oral part. The grade is based on results of both parts. Problems assigned in the written part correspond to the syllabus and the material covered in tutorials. Questions posed in the oral part explore the topics included in the syllabus to the extent that these topics are covered in lectures. A student has three chances to take the final exam.

Cheating on an exam or a homework assignment may result in automatically failing the course.

Literatura

čeština

Poslední úprava: doc. RNDr. Tomáš Dvořák, CSc. (11.09.2023)

Thomas H. Cormen,‎ Charles E. Leiserson,‎ Ronald L. Rivest,‎ Clifford Stein, Introduction to Algorithms, 4. vydání, MIT Press, Cambridge, MA 2022

Martin Mareš, Tomáš Valla, Průvodce labyrintem algoritmů, 2. vydání, CZ.NIC, Praha 2022, https://knihy.nic.cz

Pavel Töpfer, Algoritmy a programovací techniky, 2. vydání, Prometheus, Praha 2007

angličtina

Poslední úprava: doc. RNDr. Tomáš Dvořák, CSc. (29.09.2022)

Thomas H. Cormen,‎ Charles E. Leiserson,‎ Ronald L. Rivest,‎ Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, Cambridge, MA 2022

Sylabus

čeština

Poslední úprava: doc. RNDr. Tomáš Dvořák, CSc. (23.09.2019)

Algoritmy a jejich efektivita.

• Algoritmus - vlastnosti, důkaz správnosti, porovnávání kvality algoritmů.

• Časová a paměťová složitost algoritmů, asymptotická složitost, notace „velké O“.

• Složitost algoritmu v nejhorším, nejlepším a průměrném případě.

Základní algoritmy a techniky.

• Dělitelnost - Eukleidův algoritmus, prvočíselný rozklad.

• Prvočísla - test prvočíselnosti, Eratosthenovo síto.

• Rozklad čísla na cifry, převody mezi číselnými soustavami.

• „Dlouhá čísla“ - uložení, operace.

• Hornerovo schéma, rychlé umocňování.

Základní datové struktury.

• Vyhledávání v poli - sekvenční, binární.

• Abstraktní datové typy: zásobník, fronta, prioritní fronta, slovník.

• Hešovací tabulky - princip, řešení kolizí.

• Halda. Binární vyhledávací strom, princip vyvažování.

Třídění.

• Třídění čísel v poli - přímé metody (SelectSort, InsertSort, BubbleSort).

• Haldové třídění (HeapSort), QuickSort.

• Složitost problému vnitřního třídění.

• Přihrádkové třídění (CountingSort, BucketSort, RadixSort).

• Poznámka o vnějším třídění.

Rekurze.

• Rekurze - princip, příklady, efektivita.

• Binární strom - reprezentace, prohledávání, použití.

• Reprezentace aritmetického výrazu binárním stromem.

• Notace aritmetického výrazu (infix, prefix, postfix) - vyhodnocení, převody.

• Obecný strom - reprezentace, průchod, použití.

Prohledávání stavového prostoru.

• Rekurzivní algoritmy založené na zkoušení všech možností - backtracking.

• Prohledávání do hloubky a do šířky - princip, použití, realizace.

• Zrychlení pomocí ořezávání a heuristik.

• Strom hry, algoritmus minimaxu, alfa-beta prořezávání.

Základní grafové algoritmy.

• Reprezentace grafu.

• Prohledávání grafů do hloubky a do šířky a jejich aplikace.

Obecné metody návrhu algoritmů.

• Zrychlení předvýpočtem.

• Hladový algoritmus.

• Metoda „Rozděl a panuj“.

• Memoizace.

angličtina

Poslední úprava: doc. RNDr. Tomáš Dvořák, CSc. (23.09.2019)

Algorithms and their efficiency.

• Algorithm - properties, correctness, efficiency comparison.

• Time and space complexity, asymptotic complexity, Big O notation.

• Worst case, best case and average case analysis.

Basic algorithms and techniques.

• Divisibility - Euclid's algorithm, prime factorization.

• Prime numbers - primality testing, the sieve of Eratosthenes.

• Decomposing numbers into digits, numeral systems conversion.

• Higher-precision arithmetic ("long numbers").

• Horner's scheme, fast exponentiation.

Basic data structures.

• Array searching - sequential, binary.

• Abstract data types: stack, queue, priority queue, dictionary.

• Hash tables - principle, resolving collisions.

• Heap. Binary search tree, balancing principle.

Sorting.

• Internal sorting - direct methods (SelectSort, InsertSort, BubbleSort).

• HeapSort, QuickSort.

• Lower bounds for sorting.

• Sorting in linear time (CountingSort, BucketSort, RadixSort).

• Note about external sorting.

Recursion.

• Recursion - principle, examples, efficiency.

• Binary tree - representation, searching, applications.

• Representing arithmetic expressions through binary trees.

• Infix, prefix and postfix notations - evaluation, conversion.

• General trees - representation, traversal, applications.

State space search.

• Backtracking.

• Depth first search (DFS) and breadth first search (BFS) - principle, applications, implementation.

• Improving performace through pruning and heuristics.

• Game tree, minimax, alpha-beta pruning.

Basic graph algorithms.

• Representation of graphs.

• DFS, BFS and their applications.

General methods of algorithms design.

• Speeding by precomputation.

• Greedy algorithm.

• Divide and conquer.

• Memoization.