RA0279 Diskrētā matemātika II

Kods RA0279
Nosaukums Diskrētā matemātika II
Statuss Obligātais/Ierobežotās izvēles
Līmenis un tips Pamatstudiju, Profesionālais
Tematiskā joma Matemātika un statistika
Struktūrvienība Rēzeknes akadēmija
Mācībspēks Ilmārs Kangro
Kredītpunkti 3.0
Daļas 1
Anotācija Studiju kursa programma paredz apgūt šādu tematiku: .
Būla funkcijas, loģikas algebras formulas, algoritmu formulas reducēšanai uz DNF, Būla funkciju minimizācija, Būla funkciju sistēmas bāze; grafu teorijas jautājumi: grafa saistības matrica, incidences matrica, maršruti grafos, Deikstras algoritms un Floida algoritms īsākā maršruta atrašanai, attālumi grafos, sakarīgi neorientēti grafi, planāri grafi, Eilera grafs, Hamiltona grafs, ”Tuvākā kaimiņa” algoritms suboptimālā atrisinājuma atrašanai Hamiltona grafā, koki, fundamentālie cikli, attālums grafā. .
Studiju kursa saturs
Saturs Pilna un nepilna laika klātienes studijas Nepilna laika neklātienes studijas
Kontaktstundas Patstāvīgais darbs Kontaktstundas Patstāvīgais darbs
Būla funkcijas: identiskā nulle, identiskais vieninieks, noliegums, konjunkcija, disjunkcija, implikācija, ekvivalence, Šefera svītra, Pīrsa bulta, gredzenveida summa. Loģikas algebras formulas, to likumi (iekavu likšana, attieksmes loģisko operāciju kopā). 2 3 0 0
Formulu ekvivalence. Formulu izpildāmība. Vienkārša konjunkcija. Konjunktīvā normālforma (KNF). Vienkārša disjunkcija. Disjunktīvā normālforma (DNF). Teorēma par formulas pārveidošanu uz tai ekvivalentu DNF vai KNF. Algoritms formulas reducēšanai uz DNF un uz KNF. 2 3 0 0
n – mainīgo vienības konstituente. Nulles konstituente. Piemēri. Izcilā disjunktīvā normālforma (IDNF). Piemēri. Izcilā konjunktīvā normālforma (IKNF). Piemēri. Teorēma par IDNF un IKNF eksistenci. Parādīt piemērā IDNF un IKNF atrašanu ar Būla funkcijas patiesuma vērtību tabulas palīdzību. Būla funkciju minimizācija ar Karno kartes palīdzību, ar Kvaina tabulas palīdzību. Funkcionālās shēmas (galvenie funkcionālie elementi: ‘’vai’’, ‘’ne’’, ‘’un’’, ‘’ne – un’’). 2 3 0 0
Dualitāte Būla funkcijām. Dualitātes princips. Būla funkciju sistēmas. Posta funkciju klases. Būla funkcijas pašdualitātes pārbaude. 2 3 0 0
Būla funkcijas monotonitātes pārbaude. Žegalkina teorēma. Būla funkcijas linearitātes pārbaude. Posta teorēma. Būla funkciju sistēmas bāze. Funkcionālā dekompozīcija. Vienkārša disjunktīva dekompozīcija. Salikta disjunktīva dekompozīcija. 2 3 0 0
Grafs kā algebriska sistēma. Orientēti un neorientēti grafi. Grafa saistības matrica. Grafa incidences matrica. Maršruti grafos: maršruta garums, maršruts – ķēde, maršruts – vienkārša ķēde; maršruts – cikls. Dotā grafa maršrutu garumu raksturošana ar grafa saistības matricas palīdzību. 2 4 0 0
Deikstras algoritms īsākā maršruta atrašanai. Floida algoritms īsākā maršruta atrašanai. 2 3 0 0
Grafa šķautnes kārta. Grafa virsotnes pakāpe. Izolēta virsotne. Nulles grafs. Piemēri. Teorēma par grafa virsotņu pakāpju skaitu. Teorēma par grafa nepāra virsotņu skaitu. Pilns grafs. Grafa papildinājums līdz pilnam grafam. Orientēta grafa virsotnes kārta. Orientēta grafa vairākkārtīgi loki (šķautnes). Piemērs. Orientēta grafa maršruts (ceļš), tā izveidošanas nosacījumi. 3 4 0 0
Maršruts neorientētā grafā. Maršruta garums. Noslēgts maršruts (cikls). Attālums starp divām virsotnēm. Sakarīgs neorientēts grafs. Vienkāršs cikls. Vienkārša cikla eksistences nepieciešamais un pietiekamais nosacījums sakarīgā grafā. Tilts sakarīgā grafā. Piemēri. 3 3 0 0
Pilns grafs. Grafa papildinājums līdz pilnam grafam. Orientēta grafa virsotnes kārta. Orientēta grafa vairākkārtīgi loki (šķautnes). Maršruts orientētā un neorientētā grafā. 2 3 0 0
Grafu izomorfisms. Planārs grafs. Piemēri. Eilera teorēma par plaknes sadalīšanu daļās ar planāra grafa palīdzību. Eilera cikls. Eilera grafs, teorēma par Eilera grafu. Algoritms Eilera cikla izveidošanai. Hamiltona cikls. Hamiltona grafs. Piemēri. ‘’Tuvākā kaimiņa ‘’ algoritms suboptimālā atrisinājuma atrašanai Hamiltona grafā. 3 3 0 0
Koki sakarīgā neorientēts grafā. Aciklisks grafs. Teorēma par neorientētiem grafiem. Grafa atlikums (karkass). Algoritms grafa karkasa konstruēšanai. Karkasa praktisko pielietojumu piemēri. Secinājumi no teorēmas par neorientētiem grafiem (sakarība starp grafa šķautņu, virsotņu un sakarīguma komponenšu (grafa daļu) skaitu). 3 4 0 0
Fundamentālie cikli neorientētā grafā, to attēlošana ar matricas palīdzību. Šķēlumi, fundamentālie šķēlumi, to attēlošana ar matricas palīdzību. Attālums grafā, attālumu matrica, grafa ekcentricitāte, rādiuss, diametrs, perifērā virsotne. 2 3 0 0
Šķēlumu, fundamentālo šķēlumu atrašana un attēlošana ar matricas palīdzību. Attālumu matricas sastādīšana, grafa ekcentricitātes, rādiusa, diametra, perifērās virsotnes atrašana. 2 4 0 0
Kopā: 32 46 0 0
Mērķis un uzdevumi, izteikti
kompetencēs un prasmēs 		Saskaņā ar kursā paredzēto tematiku, tā mērķis ir sniegt zināšanas kursā ”Diskrētā matemātikā II”, veidojot matemātisko jēdzienu un metožu sistēmu nosauktajā disciplīnā, arī, ilustrējot tematikas saistību ar citiem matemātikas kursiem, piemēram, ”Diskrētā matemātikā I”, tā ļaujot apskatāmā studiju kursa ietvaros risināt gan praktiska, gan teorētiska satura problēmas, izmantojot arī datorprogrammas (Excel, Wolfram-Alpha, Matlab), kā arī kalpotu par bāzi tālākai studiju turpināšanai un pašizglītībai. Definētajam kursa mērķim ir pakārtoti sekojoši galvenie uzdevumi: Dot matemātisko jēdzienu/objektu definīcijas, parādīt loģiskās saites starp atsevišķiem jēdzieniem/objektiem. Iepazīstināt studentus ar studiju kursa nodaļās aplūkotajiem matemātikas izpētes objektiem un to analīzes metodēm, veidot prasmi konstatēt un analizēt funkcionālās sakarības. Iemācīt atpazīt dažādu izpētes objektu izmaiņu likumsakarības un veidot prasmi tās formāli raksturot ar teorētisko zināšanu palīdzību.
Sasniedzamie studiju
rezultāti un to vērtēšana 		Zināšanas. 1. Izprot kursa ”Diskrētā matemātika II” saturu kā datorzinātnes teorētisko pamatu sastāvdaļu. 2. Izklāsta un izskaidro matemātikas jēdzienu un objektu definīcijas. 3. Apraksta un izskaidro matemātikas algoritmu darbības principus saistībā ar iepriekš definētajiem un apgūtajiem matemātikas jēdzieniem. - 1. Mājas darbi (rakstiskie pārbaudījumi; a) formālā vērtēšana, b) neformālā vērtēšana (studentu pašvērtējums savam mājas darbam); vērtēšanas kritēriji: a) precizitāte un atbilstība, b) loģiskā argumentācija un analīze). 2. Kontroldarbi (rakstiskie pārbaudījumi; formālā vērtēšana; vērtēšanas kritēriji: a) precizitāte un atbilstība, b) loģiskā argumentācija un analīze). 3. Testi (rakstiskie pārbaudījumi; formālā vērtēšana; vērtēšanas kritēriji: precizitāte un atbilstība). 4. Eksāmens (rakstiskais pārbaudījums; summatīvā vērtēšana; vērtēšanas kritēriji: a) precizitāte un atbilstība, b) loģiskā argumentācija un analīze).
Prasmes. 1. Kursa ”Diskrētā matemātika II” apgūtajos matemātikas jēdzienos nosaka (atpazīst) reālās dzīves procesu un parādību raksturotājus. 2. Praktiski izpilda teorētiskajās nostādnēs apgūtos un uz matemātikas pamatjēdzieniem balstītos matemātikas algoritmus. 3. Sekmīgi izpildītos matemātikas algoritmus iekļauj praktisko lietojumu sfērā (reālās dzīves situācijas, uzdevumi / problēmas tehnikā un zinātnē), analizē to lietojamības iespējas un robežas, izmantojot datorprogrammas Wolfram-Alpha, Matlab un analizē to izmantošanas lietderību dažādos aspektos. - 1. Mājas darbi (rakstiskie pārbaudījumi ar gatavību nepieciešamības gadījumā izklāstīt mutiski vai vizuāli uzdevumu risinājumus; formālā vērtēšana; vērtēšanas kritēriji: a) precizitāte un atbilstība, b) praktiskie pielietojumi, c) prezentācijas un komunikācijas prasmes). 2. Kontroldarbi (rakstiskie pārbaudījumi; formālā vērtēšana; vērtēšanas kritēriji: a) precizitāte un atbilstība, b) praktiskie pielietojumi). 3. Eksāmens (rakstiskais pārbaudījums; summatīvā vērtēšana; vērtēšanas kritēriji: a) precizitāte un atbilstība, b) praktiskie pielietojumi, c) loģiskā argumentācija un analīze).
Kompetences. 1. Balstoties uz studiju kursā ”Diskrētā matemātika II” iegūto zināšanu un prasmju kopumu, students spēj veikt matemātiska rakstura uzdevuma / problēmas paredzamā atrisinājuma prognozēšanu, iegūtā atrisinājuma izvērtēšanu: 1.1. Spēj novērtēt risināmā uzdevuma / problēmas rezultātus: A) Atrisinājuma atbilstība izvirzītajam mērķim; B) Atrisinājuma nozīmība: a) teorētiskā aspektā (esošo teorētisko zināšanu ilustrācija un nostiprināšana, jaunu teorētisko zināšanu ieguve); b) praktiskā aspektā (teorētisko zināšanu pārbaude praksē); 1.2. Spēj analizēt atrisinājuma lietojamības robežas: A) saistībā ar teorētiskajām atrisinājuma iegūšanas iespējām (piemēram, dažādu risināšanas metožu, algoritmu izmantošana); B) saistībā ar praktiskajām atrisinājuma iegūšanas iespējām (piemēram, analītiskā un skaitliskā atrisinājuma iegūšana, izmantojot dažādu programmatūru); - 1. Home works (practical examination - solving tasks (in written form, but with the readiness to present the solutions to the tasks orally or visually if necessary); formal assessment; assessment criteria: a) logical reasoning and analysis, b) practical applications, c) presentation and communication skills, d) creativity and originality.
Kompetences (turpinājums). 2. Spēj prezentēt darba rezultātus rakstiskā veidā (piemēram, ziņojums, referāts) un to publiski aizstāvēt par kursa ” tematiku un diskutēt ar kolēģiem par paveiktā darba un iegūto rezultātu personīgo nozīmīgumu un emocionālo piesātinātību. 3. Spēj pielietot dotajā studiju kursā iegūtās zināšanas un prasmes savā profesionālajā darbībā, piemēram, programmatūra izstrādē, u.c. - 2. Eksāmens (rakstiskais pārbaudījums; summatīvā vērtēšana; vērtēšanas kritēriji: a) loģiskā argumentācija un analīze, b) praktiskie pielietojumi, c) radošums un oriģinalitāte.
Studiju rezultātu vērtēšanas kritēriji
1.Semestra laikā studentiem paredzēti 2 individuālie mājas kontroldarbi, kopējais kontroldarbu vērtējums studentam maksimāli ir 2,5 balles pie galīgās atzīmes. - 25%
2. Semestra laikā studentiem paredzēts viens kontroldarbs, kuru izpilda patstāvīgi auditorijā, kopējais kontroldarba vērtējums studentam maksimāli ir 1,5 balles pie galīgās atzīmes. - 15%
3. Eksāmenā ir paredzēti 9 jautājumi (1 teorijas, 8 uzdevumi), maksimālais vērtējums par to ir 6 balles pie galīgās atzīmes. - 60%
Galīgā atzīme veidojas, saskaitot semestra laikā un eksāmena laikā iegūtās balles (maksimāli var iegūt 10 balles). - 0%
 
Priekšzināšanas Iepriekš apgūtās pamatzināšanas Diskrētajā matemātikā un Augstākajā matemātikā.
Studiju kursa plānojums
Daļa KP Stundas Pārbaudījumi
Lekcijas Prakt. d. Lab. Ieskaite Eksāmens Darbs
1 3.0 16.0 16.0 0.0 *
Pieteikties uz šo kursu
[Kursa apraksts PDF formātā]