[NDMI010] Grafove algoritmy
Napsal: 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.
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.