2-AIN-205: ARTP: Algoritmické riešenie ťažkých problémov Leto 2021 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ň 15.-19.2.2021 | |
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, 205 Kb ] Problém obchodného cestujúceho (video): [ linka ] |
Cvičenie 1: [ PDF, 404 Kb ] |
Týždeň 22.2.-26.2.2021 | |
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 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ň 1.-5.3.2021 | |
P: Polynomiálne aproximačné schémy. Problém batohu: 2-aproximačný algoritmus,
pseudo-polynomiálne dynamické programovanie, FPTAS. C: 2-APX maximum matching, 2-APX maximum independent set of unit-height rectangles, 2-APX minimum makespan scheduling 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ň 8.-12.3.2021 | |
P: Balenie do krabíc (bin packing). C: 2-APX k-centers problem, Celočíselné lineárne programovanie (ILP) - dámy, vrcholové pokrytie, obchodný cestujúci. 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ň 15.-19.3.2021 | |
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: Triky pre písanie celočíselných lineárnych programov 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ň 22.-26.3.2021 | |
P: Zložitosť aproximačných algoritmov C: Stredné hodnoty, linearita strednej hodnoty. Problém MAX-CUT. 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: Hashovanie a univerzálne rodiny hashovacích funkcií, testovanie rovnosti reťazcov. 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: Ukážka DU1, Rabin-Karp (rolling hash) algorithmus, Bloomov filter 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): pozri neskôr |
Týždeň 12.-16.4.2021 | |
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: Markovova nerovnosť, náhodné prechádzky, Markovové reťazce, S->T connectivity problém s O(log n) pamäťou 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 ] |
Týždeň 19.-23.4.2021 | |
P: Pravdepodobnostné dátové štruktúry - skip lists, treaps C: Študentská vedecká konferencia Literatúra: MR:8.2,8.3 |
|
Slajdy: | Poznámky a ďalšie materiály: |
---|---|
Pravdepodobnostné dátové štruktúry (slajdy): [ PDF, 216 Kb ] Pravdepodobnostné dátové štruktúry (video): [ linka ] |
Týždeň 26.-30.4.2021 | |
P: Najlacnejšia kostra v lineárnom očakávanom čase C: Ukážka DU2, NP-ťažkosť a redukcie Literatúra: MR:10.3 |
|
Slajdy: | Poznámky a ďalšie materiály: |
---|---|
Najlacnejšia kostra (slajdy): [ PDF, 162 Kb ] Najlacnejšia kostra (video): [ linka ] |
Cvičenie 10: [ PDF, 222 Kb ] |
Týždeň 3.-7.5.2021 | |
P: Zložitostné triedy pravdepodobnostných algoritmov.
Parametrická zložitosť. Problémy riešiteľné so zafixovaným parametrom (Fixed Parameter Tractable Algorithms).
Vrcholové pokrytie. Cesta s práve k vrcholmi.
Literatúra: BB:12.6, Par2:3.2 |
|
Slajdy: | Poznámky a ďalšie materiály: |
---|---|
Zložitostné triedy pravdepodobnostných algoritmov (slajdy): [ PDF, 86 Kb ] Zložitostné triedy pravdepodobnostných algoritmov (video): [ linka ] Problémy riešiteľné so zafixovateľným parametrom (slajdy): [ PDF, 110 Kb ] Problémy riešiteľné so zafixovateľným parametrom (video): [ linka ] |
Týždeň 10.-14.5.2021 | |
P: Zhrnutie semestra | |
Slajdy: | Poznámky a ďalšie materiály: |
---|---|
Zhrnutie semestra (slajdy): [ PDF, 179 Kb ] Zhrnutie semestra (video): [ linka ] |