Tik-76.123 Algoritmien suunnittelu ja analyysi - syksy 1998
Luentojen aihepiiri
- Perusteet
- Algoritmit
- Algoritmin vaatimus
- Yksinkertaisia tietorakenteita
- Puut ja verkot
- Algoritmien analysoinnista
- Keskimääräinen aikavaatimus
- Tasoitettu vaativuus
- Mukautuvat puut
- Algoritmien suunnittelutekniikoita
- Hajoita ja hallitse-menetelmä
- Tason pistejoukon konveksin peitteen etsiminen
- Lähimpänä toisiaan olevien tasopisteiden etsiminen
- Strassenin matriisikertolaskualgoritmi
- Karsintamenetelmä
- Valintaongelma
- Hyvän sarana-alkion valitseminen
- Kahden muuttujan lineaarinen ohjelma
- Pyyhkäisyviiva-algoritmit
- Janojen leikkausten etsiminen
- Pyyhkäisyviiva-algoritmi
- Dynaaminen ohjelmointi
- Konveksin monikulmion optimaalinen kolmiointi
- Optimointiongelmat
- Verkon minimaalisen virittävän puun laskeminen
- Primin algoritmi verkon minimaalisen virittävän puun laskemiseksi
- Binomikeot
- Fibonaccikeot
- Vasemmalle kallistuvat puut
- Primin algoritmin aikavaatimus
- Kruskalin algoritmi
- Union-Find rakenteet
- Joukon esitys isälinkitettynä puuna
- Operaatiot
- Peruuttava hakeminen
- Branch-and-bound-menetelmä
- Aproksimointimenetelmistä
- Verkkojen jako-ongelmia
- Suuntaamattoman verkon (yksinkertaisesti) yhtenäiset komponentit
- Suuntaamattoman verkon 2-yhtenäiset komponentit
- Suunnatun verkon vahvasti yhtenäiset komponentit
4.9.1998, archie@cs.hut.fi