2-AIN-205: ARTP: Algoritmické riešenie ťažkých problémov Leto 2022 Prednášky a poznámky |
Kontakt | Základné informácie | Domáce úlohy | Písomky a skúšky | Prednášky a poznámky | Predchádzajúce semestre
Na tejto stránke nájdete orientačný rozvrh semestra. Tento rozvrh bude aktualizovaný vždy po skončení príslušného týždňa prednášok, takisto budú pribúdať študijné materiály.
U prednášok uvádzame zoznam kapitol, ktoré najviac pokrývajú učivo. Prezentácia materiálu v rámci prednášok sa obvykle nezhoduje s prezentáciou v učebniciach. Uvedené kapitoly by mali hlavne slúžiť ako doplňujúci materiál pre samoštúdium.
Týždeň 14.-18.2.2022 | |
P: Úvod, prehľad semestra, motivácia. 2-aproximačný algoritmus pre metrické TSP
C: Príklady, kde 2-APX TSP dáva zlé výsledky, backtracking, Bellman-Held-Karp O(2^n.n^2) algoritmus, branch and bound algoritmus Literatúra: CLRS3:35,35.2 alebo Par2:2.1-2.2,5.2 |
|
Slajdy: | Poznámky a ďalšie materiály: |
---|---|
Administratíva, úvod (slajdy): [ PDF, 198 Kb ] Problém obchodného cestujúceho (video): [ linka ] |
Týždeň 21.2.-25.2.2022 | |
P: Úvod do aproximačných algoritmov. Vrcholové pokrytie (2-aproximácia). Pokrytie množinami (O(log n)-aproximácia). C: Dôkaz neaproximovateľnosti všeobecného TSP, redukcia všeob. TSP na metric TSP a prečo nezachováva aproximačný pomer, metrické Steinerové stromy 2-APX, 2-APX maximum matching Literatúra: CLRS3:35.1,35.3 alebo Par2:4.2.2,4.2.5 |
|
Slajdy: | Poznámky a ďalšie materiály: |
---|---|
Pokrývanie množinami (slajdy): [ PDF, 276 Kb ] Pokrývanie množinami (video): [ linka ] |
Cvičenie 2: [ PDF, 292 Kb ] |
Týždeň 28.2.-4.3.2022 | |
P: Polynomiálne aproximačné schémy. Problém batohu: 2-aproximačný algoritmus,
pseudo-polynomiálne dynamické programovanie, FPTAS. C: 2-APX minimum makespan scheduling, 2-APX maximum independent set of unit-height rectangles Literatúra: V:8.1,8.2 alebo Par2:4.2.4 |
|
Slajdy: | Poznámky a ďalšie materiály: |
---|---|
Problém batohu (slajdy): [ PDF, 92 Kb ] Problém batohu (video): [ linka ] |
Cvičenie 3: [ PDF, 276 Kb ] |
Týždeň 7.-11.3.2022 | |
P: Balenie do krabíc (bin packing). C: 4-APX 2D HP problem, 3/2-APX metric TSP, 2-APX k-centers Literatúra: V:9 |
|
Slajdy: | Poznámky a ďalšie materiály: |
---|---|
Balenie do krabíc (slajdy): [ PDF, 141 Kb ] Balenie do krabíc (video): [ linka ] |
kcenters: [ PDF, 99 Kb ] ILP - dámy: [ PDF, 114 Kb ] ILP - VC a TSP: [ PDF, 168 Kb ] ILP demo: [ zip, 20 Kb ] Solver SCIP: [ linka ] |
Týždeň 14.-18.3.2022 | |
P: Aproximačné algoritmy pomocou ILP relaxácie.
Váhované vrcholové pokrytie (2-aproximačný algoritmus).
MAX-SAT (očakávaný 3/4-aproximačný algoritmus). C: Lineárne programovanie, Triky pre písanie celočíselných lineárnych programov, ILP VC Literatúra: V:14; V:16.3-16.4 |
|
Slajdy: | Poznámky a ďalšie materiály: |
---|---|
Aproximačné algoritmy pomocou ILP (slajdy): [ PDF, 141 Kb ] Aproximačné algoritmy pomocou ILP (video): [ linka ] |
Triky pre písanie celočíselných lineárnych programov: [ PDF, 135 Kb ] |
Týždeň 21.-25.3.2022 | |
P: Zložitosť aproximačných algoritmov C: DU1, ILP VC, ILP TSP Literatúra: V:29.3,29.5 |
|
Slajdy: | Poznámky a ďalšie materiály: |
---|---|
Zložitosť aproximačných algoritmov: [ PDF, 168 Kb ] Zložitosť aproximačných algoritmov (video): [ linka ] |
Týždeň 29.3.-2.4.2021 | |
P: Pravdepodobnostné algoritmy. Problém výberu / hľadania mediánu: Lineárny a očakávaný lineárny algoritmus. Las Vegas algoritmy, čas behu Las Vegas algoritmu. C: Základy pravdepodobnosti, Stredné hodnoty, linearita strednej hodnoty. Literatúra: CLRS3:9 |
|
Slajdy: | Poznámky a ďalšie materiály: |
---|---|
Problém výberu (slajdy): [ PDF, 155 Kb ] Problém výberu (video): [ linka ] |
Týždeň 5.-9.4.2021 | |
P: Monte Carlo algoritmy. Rabin-Millerov algoritmus na testovanie prvočíselnosti. Generovanie náhodných veľkých prvočísel. C: Randomizované algoritmy, testovanie rovnosti súborov, Max-cut, Max-EkSAT Literatúra: CLRS3:31.8 alebo MR:14.6 |
|
Slajdy: | Poznámky a ďalšie materiály: |
---|---|
Testovanie prvočíselnosti (slajdy): [ PDF, 173 Kb ] Testovanie prvočíselnosti (video): [ linka ] |
Týždeň 25.-29.4.2022 | |
P: Vzťah Las Vegas a Monte Carlo algoritmov. Markovova nerovnosť. Náhodné
pochôdzky. Riešenie 2-SAT a 3-SAT pomocou pravdepodobnostného algoritmu. C: midterm, Hashovanie a univerzálne rodiny hashovacích funkcií. Literatúra: CLRS3:11 alebo MR:8.4-8.5; MR: 6.1 |
|
Slajdy: | Poznámky a ďalšie materiály: |
---|---|
2-SAT a 3-SAT (slajdy): [ PDF, 190 Kb ] 2-SAT a 3-SAT (video): [ linka ] |