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

Zhrnutie prednášky

Prednáška sa venuje technikám systematického riešenia problémov hrubou silou, teda vyskúšaním všetkých možností, keď efektívnejší algoritmus nie je k dispozícii alebo sa neoplatí hľadať. Na probléme batoha (knapsack) sa ukazuje, ako generovať všetky podmnožiny pomocou binárnej reprezentácie čísel od 0 po 2^n-1, kde každý bit určuje prítomnosť prvku, čím sa problém prevedie na jednoduchý iteratívny cyklus. Na probléme obchodného cestujúceho sa demonštruje generovanie všetkých permutácií pomocou funkcie next_permutation, ktorá nájde lexikograficky nasledujúcu permutáciu prehodením a otočením konca poľa, vrátane jej použitia v štandardnej knižnici C++ a v knižnici itertools v Pythone. Ukazuje sa aj technika výberu k-prvkových podmnožín pomocou permutácií poľa s opakovaním núl a jednotiek, využiteľná napríklad pri výbere športového tímu alebo vojenskej hliadky. Na záver sa analyzuje zefektívnenie pomocou Grayovho kódu, ktorý zrýchľuje generovanie všetkých podmnožín n-krát, a amortizovaná analýza next_permutation, ktorá znižuje celkovú zložitosť generovania všetkých permutácií z n krát n faktoriál na len n faktoriál.

• Generovanie všetkých podmnožín pomocou bitovej reprezentácie čísel 0 až 2^n-1
• Problém batoha (knapsack) ako ukážka riešenia hrubou silou
• Funkcia next_permutation a generovanie všetkých permutácií
• Problém obchodného cestujúceho riešený vyskúšaním všetkých permutácií
• Výber k-prvkových podmnožín pomocou permutácií poľa s opakovaním
• Grayov kód na efektívnejšie generovanie podmnožín
• Amortizovaná analýza zložitosti cyklu s next_permutation

Zhrnutie pripravené s pomocou AI z prepisu videa.