Graafialgoritmit -97

[ Yleistä ] [ Opetusajat ] [ Luennot ] [ Viikkoharjoitukset ] [ Tenttitulokset ]
 

Koneharjoitustöitä varten on koodia saatavilla.

Opetuksen eteneminen (luennot) on nyt päivitetty kurssin loppuun asti.


Yleistä

Tämän sivun kautta voit seurata Graafialgoritmit-kurssin uutisia vuonna -97. Tämän sivun kautta tulet löytämään tiedot mm. luento- ja harjoitusajoista, viikkoharjoituksista, ym.

Kurssin pitää Jyrki Nummenmaa. Häneen voit parhaiten ottaa yhteyttä sähköpostitse: jyrki@cs.uta.fi

Voit myös halutessasi lukea kurssimainoksen, joka on myös nähtävissä laitoksen ilmoitustaululla.


Luennot

Luennoilla on käsitelty seuraavat Evenin kirjan luvut:
1.1, 1.2, 1.3, 1.5,
2.1, 2.2,
3.1, 3.2, 3.3, 3.4
5.1, 5.2 (ei MPM-algoritmia), 5.3
6.5,
7.1 (ei Kuratowskin lausetta), 7.2, 7.3, 7.4 (lähinnä vain duaalisuuden määritelmä).
8.1 ja 8.2

Lisäksi on jaettu muuta materiaalia, joita on käsitelty seuraavasti:

Zerlingin ja Mäkisen artikkelit binääripuiden generoinnista poislukien Zerlingin loppuosa

Nummenmaa: graafien suorista tasoesityksistä (jaetut sivut on käsitelty)

Nummenmaa: Constructing compact rectilinear

Hopcroftin ja Tarjanin alkuperäisartikkeli jaettiin lähinnä oheislukemistoksi

Mäkisen luennon yhteydessä jaettiin muutaman sivun moniste verkon paksuudesta

Readin artikkelista hypättiin yli kohta 2 (The basic algorithm).

Approksimointialgoritmeja NP-täydellisille ongelmille koskeva moniste.


Viikkoharjoitukset

Ensimmäiset harjoitukset pidetään perjantaina 19.9. klo 14.
Tehtäväksi tulevat Evenin kirjasta s.18-19 tehtävät 1.1,1.2, 1.3, 1.5 a ja b, 1.6.

Toiset viikkoharjoitukset pidetään perjantaina 26.6. klo 14.
Tehtävät:  Evenin kirja 1.1, Evenin kirja 1.5 a, Evenin kirja 1.5 b, Evenin kirja 2.2, Evenin kirja 3.2

Kolmannet viikkoharjoitukset pidetään tiistaina 7.10.
Tehtävät
1. Evenin kirja 3.2.
2. Jäljitä Mäkisen enumerate-aliohjelman toimintaa, kun n=4. Piirrä vastaavat puut.
3.  Mäkisen artikkelissa s.167 puhutaan algoritmista, joka laskee etäisyydet vasemmasta käsivarresta.
 Algoritmi on yksinkertaisena jätetty pois artikkelista. Muotoile algoritmi.
4. Zerlingin artikkelissa annetaan tulos, joka kertoo, millaiset koodit vastaavat täysiä binääripuita.
  Mäkisen artikkelissa asiaa ei ole tutkittu. Siis: millaiset Mäkisen koodit vastaavat täysiä binääripuita.
 
Neljännet viikkoharjoitukset pidetään tiistaina 14.10.
Tehtävät Evenin kirjasta: 3.4, 3.5, 3.6, 5.1

Viidennet viikkoharjoitukset pidetään keskiviikkona 22.10.
Tehtävät Evenin kirjasta:
1. Evenin kirja 5.4 a-b,
2. Evenin kirja 5.4 c-d,
3. Evenin kirja 5.5
4. Evenin kirja 6.11 (Algoritmia voi toki soveltaa annetuun esimerkkiin käsin)

Kuudennet viikkoharjoitukset pidetään perjantaina 14.11. klo 12-14.
Tehtävät
1. Evenin kirja 5.5 a-b
2. Evenin kirja 5.5. e
3. Evenin kirja 5.5. g
4. Otetaan tarkasteltavaksi sivun 161 kuvan 7.10 graafi ja sen vasemmanpuoleinen tasoesitys.
Maksimalisoi graafi lisäämällä kaaria siten että saadaan maksimaalinen tasograafi. Laske
graafille kanoninen numerointi käyttäen jaetun monisteen (Nummenmaa) algoritmia.
5. Jatkona edelliseen tehtävään muodosta graafin suora tasoesitys käyttäen monisteen lauseen 3.6 menetelmää.
6. Suunnittele algoritmi, joka maksimalisoi annetun tasograafin, kun graafinen topologinen tasoesitys on annettu.
 

Seitsemännet viikkoharjoitukset pidetään tostaina 27.11.
Tehtävät:

Käsitellään yksinkertaista graafia G, jonka solmujen joukko on {a,b,c,d,e,f} ja kaarten
joukko on {(a,b),(a,c),(a,d),(a,f),(b,c),(b,d),(c,e),(e,f)}. Graafin pitäisi olla tasograafi :)
1. Muodosta graafin G (periaatteellinen) tasoesitys Hopcrof-Tarjanin algoritmin tyyliin - ok,
jos et ole varma, niin tee se niinkuin kuvittelisit Hopcroft-Tarjanin algoritmin sen tekevän.
2. Maksimalisoi tasograafi (esim. Reidin algoritmin mukaisesti).
3. Laske graafin kanoninen numerointi. Käytä artikkelin "Constructing ..." mukaista algoritmia 3.3.
4. Muodosta graafin suora tasoesitys käyttäen monisteen lauseen 3.6 menetelmää.
 
Kahdeksannet viikkoharjoitukset pidetään tiistaina 9.12. Harjoitusten jälkeen jatkamme luennolla,
jos aikaa jää.
Tehtävät:

Käsitellään yksinkertaista graafia G, jonka solmujen joukko on {a,b,c,d,e,f} ja kaarten
joukko on {(a,b),(a,c),(a,d),(a,f),(b,c),(b,d),(c,e),(e,f)}. Graafi on tasograafi.
Tehtävät ovat jatkoa edellisen kerran tehtäviin.

1. Lähtien maksimalisoidusta tasograafista G (viime kerran kohta 2), muodosta graafin
horvert-esitys käyttäen jaetun artikkelin  "Constructing ..." lauseen 4.1 menettelyä.
2. Lähtien maksimalisoidusta tasograafista G (viime kerran kohta 2), muodosta graafin
horvert-esitys käyttäen jaetun artikkelin  "Constructing ..." algoritmin 4.2 menettelyä.
 


Opetusajat

Opetukseen on varattu seuraavat ajat ja paikat:
- ti 12-14, Tullik. 6, rh. 410
- ti 14-16, Tullik. 6, rh. 411  <- tästä ajasta luovuttiin, koska se ei sopinut kuulijoille
- ke 11-13, Pinni 2112
- pe 12-16, Pinni 2111

Luentoja on yhteensä 52 t ja harjoituksia 26 t.
Mm. luennoitsijan työmatkoista johtuen kaikkia aikoja ei käytetä joka viikko.

Opetuspäivät 12.11. saakka:
ti 9.9.
ke 10.9.
pe 19.9.
ti 23.9.
ke 24.9.
pe 26.9.
ti 30.9.
ke 1.10.
ti 7.10.
ke 8.10.
pe 10.10.
ti 14.10.
ke 15.10.
pe 17.10
ti 21.10
ke 22.10
ti 28.10.
---
pe 14.11. klo 10-12 Pinni 2098, klo 12-14 Pinni 2111

ti 18.11  klo 12-14 Tullik. h. 410
ke 19.11. klo 11-13 Pinni 2112
to 20.11.  klo 14-16 Pinni 1089
pe 21.11. klo 12-14 Pinni 2111

ti 25.11.  klo 12-14 Tullik. h. 410
ke 26.11 klo 11-13 Pinni 2112
to 27.11.  klo 14-16 Pinni 1089

ti 9.12. klo12-14 Tullik. h. 410
ke 10.12. klo 11-13 Pinni 2112
to 11.12. klo 14-16 Pinni 1089
pe 12.12. klo 10-12 Pinni 2098, klo 12-16 Pinni 2111
 
 


Tenttitulokset

Tenttitulokset 19.12. pidetystä tentistä
 
Nimi ja pisteet (ei sisällä harjoitushyvityksiä)
Heikki Hyyrö,  19
Juha Karvanen,  18
Marko Niinimäki, 16
Petra Pieskä,  14
Timo Poranen,  20
Heikki Rasimäki, 17
 
 
Pisteet/arvosanat:

10 1-
12  1
14  1+
15  2-
17  2
18  2+
20  3-
22  3

Harjoitushyvityksiä ei ole vielä laskettu.