[NDMI010] Grafove algoritmy

Co se jinam nevejde
Uživatelský avatar
Davpe
Matfyz(ák|ačka) level II
Příspěvky: 98
Registrován: 22. 9. 2010 16:07
Typ studia: Informatika Bc.
Kontaktovat uživatele:

[NDMI010] Grafove algoritmy

Příspěvek od Davpe »

MJ se zeptal, co se mi na přednášce líbilo, řekl jsem že minimální kostry a první úloha tak byla zaměřena na ně.

1) Algoritmus na minimální kostru pro graf nakreslený na toru bez křížení hran + jeho složitost
2) Suffixové stromy

ad 1) Borůvkův algoritmus s kontrakcemi. Všimneme si, že grafy na toru bez křížení jsou uzavřená minorová třída, díky čemuž odhadneme složitost algoritmu na O(n)
ad 2) Napsal jsem pseudokód Ukonnena a nějaké povídání k tomu, přečetl si prvně pseudokód, ten byl dobře, na to povídání se podíval jen letmo a řekl že ok.
Odpovědět

Zpět na „Ostatní“