|
|
An algorithmic approach to resolutions in representation theory
Ivánek, Adam ; Šťovíček, Jan (vedoucí práce) ; Růžička, Pavel (oponent)
V této práci popisujeme algoritmus na hledání projektivní resolventy a mi- nimální projektivní resolventy v teorie reprezentací konečně-dimenzionálních al- geber. V našem případě konečně-dimenzionální algebrou je KQ /I, kde KQ je algebra cest a I je přípustný ideál. Práce obsahuje implementaci minimalní pro- jektivní resolventy v balíku QPA. Používáme teorii Gröbnerových bazí pro KQ- moduly a článek Minimal Projective Resolutions autorů Green, Solberg a Zacha- ria [5]. Prvním krokem je vyjádření ⊕i∈Tn fn∗ i KQ = ⊕i∈Tn−1 fn−1 i KQ ∩ ⊕i∈Tn−2 fn−2 i I. Druhým krokem pro nalezení minimalní projektivní resolventy je z mno- žiny prvků fn∗ i odebrat všecky netriviálni K-lineární kombinace, které leží v ⊕i∈Tn−1 fn−1 i I + ⊕i∈Tn fn∗ i J. Výsledné moduly minimální projektivní resol- venty jsou ⊕i∈Tn fn i KQ / ⊕i∈Tn fn i I. 1
|
|
|
An algorithmic approach to resolutions in representation theory
Ivánek, Adam ; Šťovíček, Jan (vedoucí práce) ; Růžička, Pavel (oponent)
V této práci popisujeme algoritmus na hledání projektivní resolventy a mi- nimální projektivní resolventy v teorie reprezentací konečně-dimenzionálních al- geber. V našem případě konečně-dimenzionální algebrou je KQ /I, kde KQ je algebra cest a I je přípustný ideál. Práce obsahuje implementaci minimalní pro- jektivní resolventy v balíku QPA. Používáme teorii Gröbnerových bazí pro KQ- moduly a článek Minimal Projective Resolutions autorů Green, Solberg a Zacha- ria [5]. Prvním krokem je vyjádření ⊕i∈Tn fn∗ i KQ = ⊕i∈Tn−1 fn−1 i KQ ∩ ⊕i∈Tn−2 fn−2 i I. Druhým krokem pro nalezení minimalní projektivní resolventy je z mno- žiny prvků fn∗ i odebrat všecky netriviálni K-lineární kombinace, které leží v ⊕i∈Tn−1 fn−1 i I + ⊕i∈Tn fn∗ i J. Výsledné moduly minimální projektivní resol- venty jsou ⊕i∈Tn fn i KQ / ⊕i∈Tn fn i I. 1
|
|
|
Synchronizing automata
Ivánek, Adam ; Holub, Štěpán (vedoucí práce) ; Hojsík, Michal (oponent)
V této práci studujeme Trahtmanův důkaz Problému barvení cesty a sou- visející algoritmus. Pro každý silne souvislý orientovaný multigraf výstupně d s periodou 1 existuje synchronizující barvení. Béal a Perrin dokázali, že Trahtma- nův důkaz lze jednoduše zobecnit pro každou periodu a k-synchronizující barvení. Ukážeme dané zobecnění. Trahtmanův důkaz je konstruktivní a je založený na hledání barvení s netriviální stabilní dvojicí. Dokážeme, že pokud v Pα je právě jeden maximální strom, potom barvení má netriviální stabilní dvojici. Podgraf Pα obsahuje všechny hrany se stejnou barvou. Ukážeme jak také barvení na- lézt. Potom popíšeme algoritmy na nalezení k-synchronizujícího barvení. První je přímočarou aplikací tvrzení z Trahtmanova důkazu se složitostí O((n − k)dn2 ). Potom ukážeme Trahtmanovu redukci a Béalin a Perrinův algoritmus založený na Trahtmanově důkazu, ale se složitostí O((n − k)dn), kde n je počet vrcholů. 1
|
host ::
RSS.