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.
• Vyučující: Mgr. Tomáš Bílý; Adam Dingle, M.Sc.; doc. RNDr. Tomáš Dvořák, CSc.; RNDr. Tomáš Holan, Ph.D.; Mgr. Martin Mareš, Ph.D.; Mgr. Jakub Mestek; RNDr. František Mráz, CSc.; RNDr. Martin Pergel, Ph.D.; Mgr. Klára Pešková, Ph.D.; Mgr. Vít Šefl; Mgr. Jiří Šejnoha; RNDr. Michal Töpfer; doc. RNDr. Pavel Töpfer, CSc.
• Korekvizity : NPRG030
• Neslučitelnost : NMIN102, NMIN112
• Je korekvizitou pro: NPRG030
• Je neslučitelnost pro: NMIN112

Anotace

čeština

Ú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.

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

angličtina

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

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

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

čeština

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.

Zkouška je organizována společně pro posluchače v českých paralelkách, avšak odděleně od zkoušky pro posluchače anglického programu Bachelor of Computer Science.

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

angličtina

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. A student has three chances to pass the exam.

The exam is organized separately for students attending the lectures in Czech and in English. A student who is registered for one of the lectures in Czech may not take the exam in English.

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

Poslední úprava: Dingle Adam, M.Sc. (27.09.2024)

Literatura

čeština

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

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

angličtina

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

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

Sylabus

čeština

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.

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

angličtina

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.

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