Kombinatorika a grafy 3 - NDMI073

• Anglický název: Combinatorics and Graph Theory 3
• Podoba výuky: přednáška+cvičení
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2025
• Počet semestrů výuky: 1
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Maximální kapacita předmětu: 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: angličtina, čeština
• Forma uskutečňování: prezenční
• Další informace: https://dl1.cuni.cz/course/view.php?id=18207
• Možnost opakovaného zápisu: 2 / 2 / 2 / 2
• Garant: prof. Mgr. Zdeněk Dvořák, Ph.D.; doc. RNDr. Vít Jelínek, Ph.D.
• Vyučující: Dinis Arsénio Nunes Vitorino, M.Sc.; prof. Mgr. Zdeněk Dvořák, Ph.D.; doc. Mgr. Robert Šámal, Ph.D.
• Třída: Informatika Mgr. - Diskrétní modely a algoritmy; M Mgr. MSTR; M Mgr. MSTR > Povinně volitelné
• Kategorizace předmětu: Informatika > Diskrétní matematika
• Je neslučitelnost pro: NDMX073
• Je záměnnost pro: NDMX073

Anotace

čeština

Přehledová přednáška o nových trendech v kombinatorice a teorii grafů. Přednáška je určena primárně pro studenty magisterského stupně, popř. studenty prvního ročníku doktorského studia. Přednáška navazuje na předmět NDMI012 Kombinatorika a grafy II a rozšiřuje ho, k jejímu absolvování jsou nutné znalosti na úrovni tohoto předmětu.

Poslední úprava: G_I (17.03.2011)

angličtina

The lecture extends NDMI012. An overview lecture on new trends in combinatorics and graph theory. The lecture is intended for master students or the first year PhD students.

Poslední úprava: T_KAM (20.04.2008)

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

čeština

Předmět je zakončen zápočtem a zkouškou. Zápočet bude udělen za aktivní účast na alespoň 9 ze cvičení (konkrétní interpretaci aktivní účasti stanoví cvičící příslušného kroužku). Až dvě chybějící účasti je možné nahradit vyřešením zadaných domácích úkolů, jejichž řešení student osobně odprezentuje cvičícímu. V odůvodněných případech (zejména kombinované studium) je možné touto formou nahradit i více účastí. Získání zápočtu je podmínkou pro konání zkoušky, kromě výjimek (předtermíny) stanovených vyučujícím.

Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (24.08.2026)

angličtina

Passing grade for tutorials (zápočet) is obtained on the basis active participation in at least 9 of the seminars (the specific definition of “active participation” is determined by the instructor of the respective seminar). Up to two absences may be made up by completing assigned homework, the solutions to which the student must personally present to the instructor. In justified cases (particularly for combined form students), it is possible to make up even more absences in this manner. Obtaining the credit is a prerequisite for taking the exam, except for exceptions (early exam dates) specified by the lecturer.

Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (24.08.2026)

Literatura

čeština

R. Diestel, Graph theory, 3rd edition, Springer, 2005.

S. Jukna, Extremal combinatorics with application in computer science, Springer, 2001.

Poslední úprava: T_KAM (20.04.2008)

Kontroly studia předmětu a podmínky pro jejich úspěšné vykonání, způsob hodnocení

čeština

Zkouška proběhne ústní formou, v rozsahu 2-3 otázek pokrytých látkou probranou na přednáškách.

Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (06.10.2017)

angličtina

Oral exam consisting of 2-3 questions on subjects covered by the lectures.

Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (06.10.2017)

Sylabus

čeština

Nové trendy v teorii grafů (grafové minory, Szemeredi Regularity Lemma, Removal Lemma), pokročilé výsledky z extremální kombinatoriky (Hales-Jewettova věta, Gallai-Wittova věta).

Poslední úprava: Šámal Robert, doc. Mgr., Ph.D. (08.10.2018)

angličtina

New trends in graph theory (graph minors, Szemeredi Regularity Lemma, Removal Lemma), advanced results from extremal combinatorics (theorems of Hales-Jewett and Gallai-Witt).

Poslední úprava: Šámal Robert, doc. Mgr., Ph.D. (08.10.2018)