FI:IV003 Algorithms II - Informace o předmětu

IV003 Algorithms and Data Structures II

Rozsah

2/2/0. 3 kr. (plus ukončení). Ukončení: zk.
Vyučováno kontaktně

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)
RNDr. Nikola Beneš, Ph.D. (cvičící)
RNDr. Martin Jonáš, Ph.D. (cvičící)
Mgr. Martin Kurečka (cvičící)
doc. RNDr. Petr Novotný, Ph.D. (cvičící)
RNDr. David Klaška (pomocník)

Garance

prof. RNDr. Ivana Černá, CSc.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Předpoklady

IB002 Algoritmy a datové struktury || PROGRAM(1431:N-MA)
The course expands on courses IB002 Algorithms and Data Structures I.

Omezení zápisu do předmětu

Předmět je nabízen i studentům mimo mateřské obory.
Předmět si smí zapsat nejvýše 99 stud.
Momentální stav registrace a zápisu: zapsáno: 0/99, pouze zareg.: 49/99, pouze zareg. s předností (mateřské obory): 45/99

Mateřské obory/plány

• Analýza a zpracování obrazu (program FI, N-VIZ)
• Bioinformatika a systémová biologie (program FI, N-UIZD)
• Computer Games Development (program FI, N-VIZ_A)
• Computer Graphics and Visualisation (program FI, N-VIZ_A)
• Computer Networks and Communications (program FI, N-PSKB_A)
• Cybersecurity Management (program FI, N-RSSS_A)
• Diskrétní algoritmy a modely (program FI, N-TEI)
• Formální analýza počítačových systémů (program FI, N-TEI)
• Grafický design (program FI, N-VIZ)
• Graphic Design (program FI, N-VIZ_A)
• Hardware Systems (program FI, N-PSKB_A)
• Hardwarové systémy (program FI, N-PSKB)
• Image Processing and Analysis (program FI, N-VIZ_A)
• Informační bezpečnost (program FI, N-PSKB)
• Informatika (program FI, B-INF) (2)
• Informatika ve vzdělávání (program FI, B-IVV) (2)
• Information Security (program FI, N-PSKB_A)
• Kvantové a jiné neklasické výpočetní modely (program FI, N-TEI)
• Počítačová grafika a vizualizace (program FI, N-VIZ)
• Počítačové sítě a komunikace (program FI, N-PSKB)
• Principy programovacích jazyků (program FI, N-TEI)
• Programování a vývoj aplikací (program FI, B-PVA)
• Řízení kyberbezpečnosti (program FI, N-RSSS)
• Řízení vývoje služeb (program FI, N-RSSS)
• Řízení vývoje softwarových systémů (program FI, N-RSSS)
• Services Development Management (program FI, N-RSSS_A)
• Software Systems Development Management (program FI, N-RSSS_A)
• Software Systems (program FI, N-PSKB_A)
• Softwarové systémy (program FI, N-PSKB)
• Strojové učení a umělá inteligence (program FI, N-UIZD)
• Učitel informatiky a správce sítě (program FI, N-UCI)
• Učitelství informatiky pro střední školy (program FI, N-UCI) (2)
• Vývoj počítačových her (program FI, N-VIZ)
• Zpracování a analýza rozsáhlých dat (program FI, N-UIZD)
• Zpracování přirozeného jazyka (program FI, N-UIZD)

Cíle předmětu

The course expands on the introductory course Algortihm Design I. It presents algorithmic concepts without their direct connection to any particular programming language. The aim is to introduce students into design and analysis of advanced algorithms. The course presents advanced techniques of algorithm analysis and a wide spectrum of strategies together with algorithms built up on these strategies. Students are introduced into new data structures which are displayed in a row with algorithms based on them.

Výstupy z učení

After enrolling the course students are able to:
- actively use and modify advanced graph and string algorithms,
- actively used advanced techniques for designing algorithms (dynamic programming, greedy techniques) for designing algorithms, expain their specific properties and limits,
- actively used and modify advanced dynamic data structures and use them for designing effective algorithsm,
- analyze time complexity and prove correctness of algorithms.

Osnova

• Advanced design and analysis techniques: dynamic programming, greedy strategies,backtracking. Amortized analysis.
• Advanced data structures: binomial and Fibonacci heaps, data structures for disjoint sets.
• Graph algorithms: Single-Source Shortest Paths (The Bellman-Ford algorithm). All-Pairs Shortest Paths (Shortest paths and matrix multiplication, The Floyd-Warshall algorithm, Johnson's algorithm for sparse graphs). Maximum Flow (The Ford-Fulkerson method, The Push-Relabel method). Maximum bipartite matching.
• String matching: the naive string-matching algorithm, Karp-Rabin algorithm, string matching with finite automata. The Knuth-Morris-Pratt algorithm.

Literatura

povinná literatura
• KLEINBERG, Jon a Éva TARDOS. Algorithm design. Boston: Pearson/Addison-Wesley, 2006, xxiii, 838. ISBN 0321372913. URL info

doporučená literatura
• DASGUPTA, Sanjoy, Christos Ch. PAPADIMITRIOU a Umesh Virkumar VAZIRANI. Algorithms. 1st ed. Boston: McGraw-Hill Companies, 2008, x, 320. ISBN 9780073523408. info
• CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989, xvii, 1028. ISBN 0070131430. info

Výukové metody

Lectures and seminars. Students are required to solve given algorithmic problems.

Metody hodnocení

The course has a form of a lecture with a seminar. During the term students separately solve sets of algorithmic problems. The course is concluded by the written exam. A student can attend the final exam providing she/he has acquired given number of points from problem sets. Přednášky a cvičení budou vedena v českém i anglickém jazyce. Student může odevzdávat svá řešení v českém i anglickém jazyku.

Vyučovací jazyk

Angličtina

Navazující předměty

• IA101 Algoritmika pro těžké problémy

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2023/IV003/index.qwarp

Další komentáře

Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Předmět byl dříve vypisován pod kódem IB108.

• Statistika zápisu (nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/jaro2025/IV003