|
|
|||||||||||||||||
Opinto-opas 2011-2012
MAT-21161 Algoritmimatematiikka, 4 op
|
Vastuuhenkilö
Terhi Kaarakka
Opetus
| Opetusmuoto | P1 | P2 | P3 | P4 | Kesä | Toteutuskerrat | Luentoajat ja -paikat |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Opetusmuoto | Tunteja | Aikaväli | Toteutuskerrat | Luentoajat ja -paikat |
|
|
|
| MAT-21161 2011-03 |
|
Suoritusvaatimukset
Hyväksytysti suoritettu tentti sekä hyväksytty harjoitussuoritus.
Osaamistavoitteet
Opintojakson suorittamisen jälkeen opiskelija pystyy selittämään, milloin joukot (relaatiot, funktiot) ovat samat, todistamaan samuuden ja käyttämään samuutta muokattaessa ja sievennettäessä joukkolausekkeita. Opiskelija tunnistaa relaatioista funktion, tunnistaa sen ominaisuuksia ja pystyy osoittamaan sen injektiivisyyden tai surjektiivisuuden sekä etsimään käänteisfunktion, jos sellainen on olemassa. Opiskelija tuntee logiikan konnektiivien merkityksen, pystyy osoittamaan loogiset lauseet samoiksi ja suorittamaan loogisten lausekkeiden sieventämistä ja muokkaamista. Opiskelija pystyy suorittamaan helpohkoa loogista päättelyä tunnettujen pätevien teorioiden avulla. Opiskelija osaa käyttää kvanttoreita ja ymmärtää esimerkiksi niiden järjestyksen merkityksen. Opiskelija pystyy lukemaan predikaattilogiikan päättelyitä ja tunnistaa niiden oikeellisuuden. Opiskelija pystyy muodostamaan helppoja induktiivisia joukkoja ja rekursiivisia funktioita. Opiskelija osaa todistaa induktiolla.
Sisältö
| Sisältö | Ydinaines | Täydentävä tietämys | Erityistietämys |
| 1. | TIETORAKENTEISTA: Todistusmenetelmiä, joukko-oppia, muita tietorakenteita | Äärellisten joukkojen mahtavuus | |
| 2. | RELAATIO JA FUNKTIO: Relaatioita ja niiden ominaisuuksia, ekvivalenssirelaatio, funktioita ja niiden ominaisuuksia (mm. injektio, surjektio, bijektio) | Sulkeumat, joukkojen mahtavuus (äärettömät joukot, numeroituvat ja ylinumeroituvat joukot), kasvunopeuksia ja aikavaativuuksia. | |
| 3. | LOGIIKKAA: Propositiologiikkaa, looginen päättely, predikaattilogiikkaa | Normaalimuodot, predikaattilogiikan päättely. | Propositiologiikan ekvivalenssien todistaminen |
| 4. | INDUKTIO ja REKURSIO: Induktiivisesti määritellyt joukot, rekursiivisesti määritellyt funktiot, matemaattinen induktio | Listat | |
| 5. | Boolen algebra |
Opintojakson arvostelu
Opintojakson suorittamiseen kuuluu pakolliset harjoitukset ja tentin suorittaminen. Ahkeralla harjoitusten tekemisellä opiskelija voi korottaa saman toteutuskerran hyväksyttyä arvosanaa bonuspisteillä (max. yhdellä arvosanalla) Jos opiskelija suoriutuu ydinainekseen kuuluvien lasku- ja todistustehtävien tekemisestä hyvin, niin se riittää opintojakson läpäisemiseen arvosanalla 3. Taitava suoriutuminen ja täydentävän tietämyksen hallinta oikeuttaa arvosanoihin 4 tai 5.
Arvosteluasteikko:
Opintojaksolla käytetään numeerista arviointiasteikkoa (1-5)
Oppimateriaali
| Tyyppi | Nimi | Tekijä | ISBN | URL | Painos,saatavuus... | Tenttimateriaali | Kieli |
| Kirja | Discrete Mathematics | Hein | Englanti | ||||
| Kirja | Johdatus diskreettiin matematiikkaan | Merikoski ym | Suomi | ||||
| Kirja | Logic and Discrete Mathematics:A Computer Science Perspective | Grassmann, Tremplay | Englanti |
Tietoa esitietovaatimuksista
Suositeltavana esitietona kurssi Insinöörimatematiikka (A/B/C/D/X) 1u
Esitietoketju (Vaatii kirjautumisen POPiin)
Vastaavuudet
| Opintojakso | Vastaa opintojaksoa | Selite |
|
|
|
Tarkempia tietoja toteutuskerroittain
| Toteutus | Kuvaus | Opetusmuodot | Toteutustapa |
|
Lähiopetus: 0 % Etäopetus: 0 % Itseopiskelu: 0 % |
|||
| Kurssin keskeinen tavoite on tarjota teoreettisia näkökulmia ja matemaattisia työvälineitä algoritmien suunnitteluun ja laatimiseen. Työskenellään muun muuassa seuraavien aiheiden parissa: joukot, relaatiot, funktiot, propositiologiikka, predikaattilogiikka, induktio ja rekursio. |