PLA-12200 Diskreetti matematiikka, 3 op
Discrete Mathematics
Vastuuhenkilö
Juha Tanttu, Timo Ranta, Frank Cameron
Opetus
Toteutuskerta 1: PLA-12200 2015-01
| Opetusmuoto | P1 | P2 | P3 | P4 | P5 |
|
|
|
|
|
|
Suoritusvaatimukset
2 vaihtoehtoa: 1.hyväksytysti suoritetut kokeet ja mahdollisesti harjoitustyöt tai 2.lopputentti.
Tarkat pisterajat ilmoitetaan erillisessä kurssikuvauksessa.
Osasuoritusten pitää liittyä samaan toteutuskertaan
Osaamistavoitteet
Kun kurssi on suoritettu, opiskelija ymmärtää ja osaa soveltaa seuraavia asioita: - funktioon liittyvät käsitteet: määrittelyjoukko, mallijoukko, arvojoukko, injektio, surjektio, käänteisfunktio - seuraavat lukufunktiot: katto, pohja, mod, div, max ja min - seuraavat listafunktiot: head, tail, cons, cat, seq, pairs, - seuraavat funktiot: map, insert - listoja käsitelevien ei-rekursiivisten ja rekursiivisten funktioiden laskeminen ja muodostaminen - listoja käsitelevien ei-rekursiivisten ja rekursiivisten pseudokoodiproseduurien laskeminen ja muodostaminen - graafeja käsitelevien ei-rekursiivisten ja rekursiivisten pseudokoodiproseduurien laskeminen ja muodostaminen - binääripuita käsitelevien ei-rekursiivisten ja rekursiivisten pseudokoodiproseduurien laskeminen ja muodostaminen - binääripuita käsitelevien rekursiivisten pseudokoodiproseduurien laskeminen ja muodostaminen - graafin läpikulku syvyys ensin (depth-first) periaatteella - graafin läpikulku leveys ensin (breadth-first) periaatteella - lyhimmän polun löytäminen Dijkstran menetelmällä - kevyimmän virittävän puun muodostaminen Primin menetelmällä - binäärihakupuuhun liittyviä tehtäviä, esim. alkion lisääminen, annetun alkion etsiminen, maksimialkion etsiminen, jne - miten todistetaan lause induktion avulla - miten sovelletaan inkluusio-ekskluusioperiate - miten lasketaan kahden kokonaisluvun suurin yhteinen tekijä
Sisältö
| Sisältö | Ydinsisältö | Täydentävä tietämys | Erityistietämys |
| 1. | Funtiot - funktioiden rakentaminen - rekursiiviset funktiot - proseduuri | ||
| 2. | Graafi ja graafifunktioita - graafin läpikulku - lyhyimmän polun tehtävä - pienin virittävä puu | ||
| 3. | Puu ja puufunktioita - binäärihakupuu - binääripuu ja Huffman-koodaus | ||
| 4. | Induktio | ||
| 5. | Inkluusio-eksluusio periaate | ||
| 6. | Jaollisuus -suurin yhteinen tekijä |
Oppimateriaali
| Tyyppi | Nimi | Tekijä | ISBN | URL | Lisätiedot | Tenttimateriaali |
| Opintomoniste | Diskreettimatematiikan paloja | Frank Cameron | Kyllä |
Esitietovaatimukset
| Opintojakso | P/S | Selite |
| PLA-12100 Algoritmimatematiikka | Suositeltava |
Vastaavuudet
| Opintojakso | Vastaa opintojaksoa | Selite |
| PLA-12200 Diskreetti matematiikka, 3 op | MATP-2200 Diskreetti matematiikka, 3 op |