Teknillinen korkeakoulu -Tietojenkäsittelyopin laboratorio.


Tik-76.123 Algoritmien suunnittelu ja analyysi - syksy 1998

Luentojen aihepiiri


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




4.9.1998, archie@cs.hut.fi