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

Zhrnutie prednášky

Prednáška sa venuje téme dolných odhadov časovej zložitosti, teda dokazovaniu, že daný problém sa nedá vyriešiť rýchlejšie, čo je v informatike podstatne ťažšie ako dokazovanie horných odhadov. Krátko sa spomína problém P vs NP a NP-ťažké problémy (splniteľnosť booleovskej formuly, hamiltonovská cesta, obchodný cestujúci) ako príklady, kde netriviálne dolné odhady chýbajú. Hlavnou časťou je dôkaz, že vyhľadávanie v usporiadanom poli pomocou porovnávaní vyžaduje aspoň logaritmický počet krokov, ukázaný tromi ekvivalentnými spôsobmi - rozhodovacím stromom kandidátov, počítaním možných priebehov deterministického algoritmu a informačno-teoretickým argumentom o bitoch informácie. Tento prístup sa následne zovšeobecní na dôkaz, že akýkoľvek algoritmus triediaci porovnávaním musí mať v najhoršom prípade zložitosť aspoň n krát logaritmus n, pričom problém triedenia sa prevedie na hľadanie správnej permutácie spomedzi n faktoriál možností. Na záver sa naznačuje, že countsort dokáže tento dolný odhad prekonať využitím dodatočnej informácie o malých celočíselných kľúčoch, napríklad veku človeka.

• Rozdiel medzi hornými a dolnými odhadmi zložitosti
• P vs NP a NP-ťažké problémy (SAT, Hamiltonovská cesta, obchodný cestujúci)
• Dolný odhad pre vyhľadávanie v usporiadanom poli cez rozhodovací strom
• Argument počtu možných priebehov deterministického algoritmu
• Informačno-teoretický argument s bitmi informácie
• Zovšeobecnenie na dolný odhad n log n pre triedenie porovnávaním
• Optimálnosť Mergesortu a Heapsortu
• Úvod do countsortu ako spôsobu prekonania dolného odhadu

Zhrnutie pripravené s pomocou AI z prepisu videa.