|
|
|||||||||||||||||
Opinto-opas 2010-2011
MAT-41190 Graafiteoria, 6 op
|
Vastuuhenkilö
Keijo Ruohonen
Opetus
| Opetusmuoto | P1 | P2 | P3 | P4 | Kesä | Toteutuskerrat | Luentoajat ja -paikat |
|
|
|
|
|
|
|
|
|
Suoritusvaatimukset
Hyväksytysti suoritettu kirjallinen tentti.
Osasuoritusten pitää liittyä samaan toteutuskertaan
Opetukseen ja oppimiseen liittyvät periaatteet ja lähtökohdat
-
Osaamistavoitteet
Opintojakson suoritettuaan opiskelija tunnistaa graafi- ja verkkorakenteen mallinnustilanteessa. Opiskelija osaa graafien ja verkkojen peruskäsitteet, -nimikkeistön, -työkalut sekä -ominaisuudet ja pystyy ottamaan ne käyttöön yksinkertaisissa mallinnustilanteissa. Opiskelija myös osaa graafiteoreettiset perusalgoritmit ja pystyy toteuttamaan ne yksinkertaisissa esimerkkitapauksissa ja sovelluksissa. Osaamistavoitteet saavutettuaan opiskelijalla on edellytykset mallintaa ja analysoida mallinsa graafi- ja verkkoteoreettisin menetelmin. Kyseiset menetelmät muodostavat tätä nykyä ehkä yleisimmän mallinnustyökalun diskreetissä matematiikassa ja algoritmiikassa, eikä yhden opinjakson puitteissa ole mahdollista ottaa mukaan koko alueen osaamistavoitteita täysin kattavasti. Opintojakson suoritettuaan opiskelijalla on edellytykset myös laajentaa taitojaan ja omaksua muutakin.
Sisältö
| Sisältö | Ydinaines | Täydentävä tietämys | Erityistietämys |
| 1. | Graafien ja suunnattujen graafien peruskäsitteet ja -ominaisuudet. Graafin ja suunnatun graafin matriisiesitykset. Perusirrotusjoukot ja peruspiirit omaisuuksineen ja matriiseineen. | Esitettyjen peruskäsitteiden, -ominaisuuksien ja esitysten soveltaminen graafien ja suunnattujen graafien analysoinnissa. | |
| 2. | Puut ja suunnatut puut ja niiden peruskarakterisaatiot. Virittävät puut ja metsät. Kvasiyhtenäiset ja asykliset suunnatut graafit. | Puiden ja asyklisten suunnattujen graafien käyttö mallinnuksen perustyökaluna. Stationaariset lineaariset verkot. | |
| 3. | Graafiteoreettiset perusalgoritmit ja niiden soveltaminen yksinkertaisissa esimerkkitilanteissa ja sovelluksissa. | Graafialgoritmien perusparadigmat ja niihin liittyvät algoritmit muunnelmineen: Dijkstran algoritmi, Floyd-Warshall-algoritmi, Kruskalin algoritmi, etsintäalgoritmit, hehkutusmenetelmä | |
| 4. | Geometrista graafiteoriaa. Tasograafit ja tasottuvat graafit peruskäsitteineen, -ominaisuuksineen ja -algoritmeineen. Graafien piirtäminen. Matroiditeorian alkeita. | Esitettyjen peruskäsitteiden ja -ominaisuuksien soveltaminen tasottuvien graafien analysoinnissa. | Matroidit ja ahneet algoritmit. |
Opintojakson arvostelu
Arvosana määräytyy harjoitusten ja tentin perusteella. Läpipääsyyn vaaditaan hyväksytysti suoritettu tentti. Hyväksymisraja tentissä on maksimista puolet tai alempi. Tentissä saatuja, hyväksymisrajan ylittäneitä pisteitä voi parantaa harjoituksissa aktiivisesta osallistumisesta etukäteen saaduilla pisteillä eri taulukon mukaan. Ydinaineksen hallitseminen hyvin riittää opintojakson läpäisemiseen arvosanalla 3. Arvosanan 4 saavuttamiseksi on osattava myös täydentävän tietämyksen asioita. Arvosanaa 5 varten on osattava täydentävän tietämyksen asioita hyvin.
Arvosteluasteikko:
Opintojaksolla käytetään numeerista arviointiasteikkoa (1-5)
Osasuoritukset:
Oppimateriaali
| Tyyppi | Nimi | Tekijä | ISBN | URL | Painos,saatavuus... | Tenttimateriaali | Kieli |
| Kirja | Graph Theory and Its Applications | Gross, J. & Yellen, J. | Englanti | ||||
| Muu verkkomateriaali | Kurssisivu | Ruohonen, K. | Suomi | ||||
| Opintomoniste | Graafiteoria | Ruohonen, K. | Suomi |
Esitietovaatimukset
| Opintojakso | P/S | Selite |
| MAT-31090 Matriisilaskenta 1 | Suositeltava |
Esitietoketju (Vaatii kirjautumisen POPiin)
Vastaavuudet
| Opintojakso | Vastaa opintojaksoa | Selite |
|
|
|
Lisätiedot
Soveltuu jatko-opinnoiksi
Tarkempia tietoja toteutuskerroittain
| Toteutus | Kuvaus | Opetusmuodot | Toteutustapa |
| Graafiteorian luennot ja harjoitukset syksyllä 2010. |