nechodím na prednáškyADŠ prednáška 01: Problém stabilných manželstiev
Preber si túto prednášku so svojou AI
Skopíruj pripravený podklad a vlož ho do ChatGPT, Claude alebo inej AI — bude ťa učiť alebo skúšať len z tejto prednášky.
Zhrnutie prednášky
Úvodná prednáška predmetu Algoritmy a dátové štruktúry predstavuje ciele kurzu: naučiť analyzovať algoritmy, porovnávať ich vhodnosť v praxi a samostatne riešiť jednoduché algoritmické problémy. Prednášajúci na ukážku zvolil problém stabilných manželstiev, v ktorom majú chlapci a dievčatá zoradené preferencie a treba ich popárovať tak, aby nevznikla dvojica, ktorá by si vzájomne uprednostnila jeden druhého pred súčasnými partnermi. Zdôrazňuje, že metafory slúžia len na zjednodušenie jazyka a techniky sa učia na jednoduchých problémoch. Ukazuje, ako sa problém abstrahuje pomocou ID čísel a vstupného súboru (inštancia problému), a že na rozdiel od matematických dôkazov záleží pri algoritmoch na počte krokov. Na záver naznačuje riešenie hrubou silou, teda skúšaním všetkých možných popárovaní.
- - Cieľom predmetu je naučiť analyzovať algoritmy a vyberať vhodné algoritmy a dátové štruktúry.
- - Metafory (chlapci, dievčatá) zjednodušujú formuláciu problému, nie sú to neužitočné hračky.
- - Problém stabilných manželstiev: popárovať podľa preferencií tak, aby žiadna dvojica nemala dôvod utiecť od svojich partnerov.
- - Abstrakcia: osoby sa očíslujú ID a preferencie sú postupnosti čísel, vstup tvorí inštanciu problému.
- - V informatike na rozdiel od matematických dôkazov rozhoduje aj počet krokov výpočtu.
- - Procesor zvládne miliardy jednoduchých krokov za sekundu, no mnohé funkcie rastú rýchlejšie.
- - Riešenie hrubou silou skúša všetky možné popárovania a každé kontroluje.
Zhrnutie pripravené s pomocou AI z prepisu videa.
