Algoritmy a datové struktury 2 - NTIX061

• Anglický název: Algorithms and Data Structures 2
• Zajišťuje: Studijní oddělení (32-STUD)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: zimní
• E-Kredity: 6
• Rozsah, examinace: zimní s.:2/2, 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
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Je zajišťováno předmětem: NTIN061
• Garant: Mgr. Martin Mareš, Ph.D.; prof. RNDr. Ondřej Čepek, Ph.D.; doc. Mgr. Jan Hubička, Ph.D.
• Třída: Informatika Bc.
• Kategorizace předmětu: Informatika > Teoretická informatika
• Prerekvizity : {NXXX015, NXXX018, NXXX022, NXXX023, NXXX024, NXXX025, NXXX030, NXXX031, NXXX033, NXXX065}
• Neslučitelnost : NTIN061
• Záměnnost : NTIN061
• Je neslučitelnost pro: NTIN061
• Je záměnnost pro: NTIN061

Anotace

čeština

Přednáška o různých typech algoritmů a jejich časové složitosti (navazuje na NTIN060 Algoritmy a datové struktury 1).

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

angličtina

Lecture about various types of algorithms and their time complexity (follows NTIN060 Algorithms and data structures 1).

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

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

Je třeba získat zápočet a složit zkoušku (v libovolném pořadí).

Pro zápočet je třeba získat 100 bodů z alespoň 150 možných udělovaných průběžně za řešení domácích úloh, písemné testy a další aktivity. Z průběžné povahy kontroly neplyne nárok na vypisování opravných termínů testů ani zadání náhradních domácích úloh.

V důvodných případech (dlouhodobá nemoc, pobyt v zahraničí, apod.) může cvičící stanovit individuální podmínky na udělení zápočtu.

Zkouška může být písemná, ústní nebo kombinovaná. Zkouška může mít kontaktní nebo distanční formu. Formu zkoušky určuje vyučující.

Poslední úprava: Mareš Martin, Mgr., Ph.D. (26.09.2023)

Literatura

čeština

A.Koubková, J.Pavelka : Úvod do teoretické informatiky, Matfyzpress 1999

Aho, Hopcroft, Ullman : The design and analysis of computer algorithms, Addison-Wesley 1976

T.Cormen, Ch.Leiserson, R. Rivest, C. Stein : Introduction to Algorithms (2nd Edition), McGraw-Hill 2001

L.Kučera : Kombinatorické algoritmy, SNTL Praha 1983

L.Kučera, J. Nešetřil : Algebraické metody diskretní matematiky, SNTL Praha 1989

M.Mareš, T.Valla : Průvodce labyrintem algoritmů, CZ.NIC z.s.p.o. Praha 2017, 978-80-88168-19-5, http://pruvodce.ucw.cz/

http://kam.mff.cuni.cz/~ludek

Poslední úprava: Hric Jan, RNDr. (03.10.2017)

angličtina

Aho, Hopcroft, Ullman : The design and analysis of computer algorithms, Addison-Wesley 1976

T.Cormen, Ch.Leiserson, R. Rivest, C. Stein : Introduction to Algorithms (2nd Edition), McGraw-Hill 2001

http://kam.mff.cuni.cz/~ludek

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (22.11.2012)

Požadavky ke zkoušce

Je třeba rozumět teorii z přednášky a být schopen ji aplikovat na řešení algoritmických úloh.

Poslední úprava: Mareš Martin, Mgr., Ph.D. (11.10.2017)

Sylabus

čeština

Volitelná témata v hranatých závorkách, zbytek je povinný.

1. Vyhledávání v textu

• algoritmus Knuth-Morris-Pratt

• algoritmus Aho-Corasicková

• [algoritmus Rabin-Karp]

2. Toky v sítích

• algoritmus zlepšující cesty

• Dinicův algoritmus

• Goldbergův algoritmus

• párování v bipartitním grafu

• [hledání maximálního toku minimální ceny]

3. Algebraické algoritmy

• diskrétní Fourierova transformace, její motivace a aplikace

• algoritmus FFT a jeho implementace obvodem „butterfly“

• [příbuzné transformace (kosinová - JPEG komprese)]

4. Paralelní aritmetické algoritmy

• třídící sítě (implementace jednoho třídícího algoritmu - buď merge-sort nebo bitonic-sort)

• carry look-ahead algoritmus pro sčítání čísel

5. Základní geometrické algoritmy v rovině

• konvexní obal

• princip zametání roviny řízeného událostmi

• [Voroného diagram a Delaunayova triangulace (Fortunův algoritmus)]

6. Převoditelnost problémů a třídy časové složitosti

• polynomiální transformace a redukce mezi rozhodovacími problémy

• nedeterministické algoritmy, třídy P a NP

• NP-úplnost

7. Aproximační algoritmy

• použití aproximačních algoritmů, poměrová a relativní chyba

• jeden až dva jednoduché příklady aproximačních algoritmů (knapsack, bin-packing, rozvrhování na paralelních strojích) včetně horního odhadu pro jejich poměrovou (nebo relativní) chybu

• aproximační schéma: princip a příklad

8. Pravděpodobnostní algoritmy a kryptografie

• algoritmy typu Monte Carlo (Rabinův-Millerův test prvočíselnosti)

• šifrování s veřejným klíčem (algoritmus RSA)

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

angličtina

Optional topics in square brackets, the rest is mandatory.

1. Searching in text

• Knuth-Morris-Pratt algorithm

• Aho-Corasick algorithm

• [Rabin-Karp algorithm]

2. Flows in networks

• augmenting path algorithm

• Dinic's algorithm

• Goldberg's algorithm

• matching in bipartite graph

• [search for maximum flow of minimum price]

3. Algebraic algorithms

• discrete Fourier transformation, its motivation and application

• the FFT algorithm and its implementation by the "butterfly"

• [related transformations (cosine transformation - JPEG compression)]

4. Parallel arithmetic algorithms

• sorting networks (implementation of one sorting algorithm - either merge-sort or bitonic-sort)

• carry look-ahead algorithm for addition

5. Basic geometric algorithms in a plane

• convex hull

• the principle of plane sweeping driven by events

• [Voronoi diagram and Delaunay triangulation (Fortune's algorithm)]

6. Transferability of problems and classes of time complexity

• polynomial transformation and reduction between decision problems

• non-deterministic algorithms, Class P and NP

• NP-completeness

7. Approximation algorithms

• use of approximation algorithms, ratio and relative error

• one or two simple examples of approximation algorithms (knapsack, bin-packing, scheduling on parallel machines) including an upper estimate for their ratio (or relative) error

• approximation scheme: principle and example

8. Probabilistic algorithms and cryptography

• Monte Carlo algorithms (Rabin-Miller's Primality Test)

• public key cryptography (RSA algorithm)

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