[NDMI010] Grafove algoritmy

Co se jinam nevejde

[NDMI010] Grafove algoritmy

Příspěvekod Davpe » 14. 1. 2013 18:39

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.
Uživatelský avatar
Davpe
Matfyz(ák|ačka) level II
 
Příspěvky: 98
Registrován: 22. 9. 2010 15:07
Typ studia: Informatika Bc.
Login do SIS: pegrimed

Zpět na Ostatní

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron