Opinto-opas 2010-2011
Jatko

Perus Pori KV Jatko Avoin

|Tutkinnot|     |Opintokokonaisuudet|     |Opintojaksot|    

Opinto-opas 2010-2011

MAT-41190 Graafiteoria, 6 op
Graph Theory

Vastuuhenkilö

Keijo Ruohonen

Opetus

Opetusmuoto P1 P2 P3 P4 Kesä Toteutuskerrat Luentoajat ja -paikat
Luennot
Harjoitukset
 4 h/vko
 2 h/vko
+4 h/vko
+2 h/vko


 


 


 
MAT-41190 2010-01 Keskiviikko 12 - 14, TB223
Perjantai 10 - 12, TB223
Keskiviikko 12 - 14, TB224

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:

Osasuoritusten pitää liittyä samaan toteutuskertaan

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 
MAT-41190 Graafiteoria, 6 op 73119 Graafiteoria, 3 ov  

Lisätiedot

Soveltuu jatko-opinnoiksi

Tarkempia tietoja toteutuskerroittain

Toteutus Kuvaus Opetusmuodot Toteutustapa
MAT-41190 2010-01 Graafiteorian luennot ja harjoitukset syksyllä 2010.        

Viimeksi muokattu09.02.2010