Algoritmy a dátové štruktúry prednáška 01

Zhrnutie prednášky

Úvodná prednáška predmetu Algoritmy a dátové štruktúry predstavuje na konkrétnom príklade úlohu stabilných manželstiev - párovanie n chlapcov a n dievčat na základe ich zoznamov preferencií tak, aby medzi nimi nevznikol konflikt (dvojica, ktorá by sa vzájomne uprednostnila pred svojimi súčasnými partnermi). Ukazuje sa naivné riešenie kontrolou všetkých dvojíc (rádovo n na druhú) aj hrubou silou cez n faktoriál možných párovaní a demonštruje sa, prečo jednoduché postupné odstraňovanie konfliktov nemusí nikdy skončiť. Následne sa opisuje Gale-Shapleyho algoritmus s postupnými pýtačkami chlapcov za dievčatami, dokazuje sa jeho korektnosť, konečnosť aj časová zložitosť rádovo n na druhú a poukazuje sa na jeho reálne využitie (napríklad prideľovanie rezidentov nemocniciam) aj na to, že výsledné párovanie závisí od toho, ktorá strana robí pýtačky. Druhá časť prednášky motivuje potrebu efektívnych algoritmov aj napriek rastúcemu výkonu počítačov (Moorov zákon) na príklade vývoja počítačového šachu (alfa-beta orezávanie, hĺbka prehľadávania, neskôr neurónové siete) a zavádza rozdiel medzi algoritmom (jednorazové spracovanie dát) a dátovou štruktúrou (dlhodobo používaná schránka na dáta), spolu s náčrtom obsahu semestra.

• Úloha stabilných manželstiev a jej metafora s chlapcami a dievčatami
• Definícia konfliktu a stability párovania
• Naivné riešenia - kontrola všetkých dvojíc O(n²) a hrubá sila n!
• Neúspešný postup odstraňovania konfliktov (cyklenie)
• Gale-Shapleyho algoritmus a dôkaz jeho korektnosti a konečnosti
• Časová zložitosť O(n²) a nejednoznačnosť výsledného riešenia
• Motivácia efektívnych algoritmov - Moorov zákon a počítačový šach
• Rozdiel medzi algoritmom a dátovou štruktúrou

Zhrnutie pripravené s pomocou AI z prepisu videa.