Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Kursus Diskreetne matemaatika

Diskreetne matemaatika


Kursuse juhendaja: Jan Willemson
Kursuse toimumisaeg: kevadsemester 1997
Kursuse maht: 32t loenguid + 32t praktikume, lõpeb eksamiga, annab 3 AP
Eeldusaine: Diskreetse matemaatika elemendid

Kordamisküsimusi diskreetse matemaatika kursuse kohta

  1. Graafiteooria põhimõisted: tipp, serv, kordsed servad, silmus, lihtgraaf, valents, orienteeritud graaf, selle alusgraaf, nõrk ja tugev sidusus, orienteeritav graaf, sisend- ja väljundvalents, tee, tsükkel, sidusus, tippudevaheline kaugus, alamgraaf, indutseeritud alamgraaf, sidususkomponent, puu, mets, intsidentsus, isomorfism, graafide märgendamine, kaaslusmaatriks, intsidentsusmaatriks, graafide eriliigid (tühi graaf, täielik graaf, nullgraaf, platoonilised graafid, tsükkel, ahel, ratas, kuupgraaf), regulaarne graaf, kahealuseline graaf, n-aluseline graaf, täielik n-aluseline graaf, graafi täiendgraaf, graafi servgraaf.
  2. Euleri graafid: Königsbergi sildade ülesanne, Euleri tsükkel, Euleri graaf, pool-Euleri graaf, Euleri teoreem, järeldused sellest, Fleury algoritm, teoreem graafi orienteeritavusest, orienteeritud graafi eulrilisus ja pool-eulerilisus.
  3. Hamiltoni graafid: Hamiltoni dodekaeedriülesanne, Hamiltoni tsükkel, Hamiltoni graaf, pool-Hamiltoni graaf, Ore teoreem, Diraci teoreem, turniirid, teoreem turniiride hamiltonilisusest ja pool-hamiltonilisusest.
  4. Vood võrkudes: võrk, servade võimsused, allikas ja sihtpunkt võrgus, voog võrgus, voo väärtus, lõige, selle võimsus, teoreem maksimaalsest voost ja minimaalsest lõikest (täisarvulisel juhul ja üldjuhul), eraldav hulk, Mengeri teoreem.
  5. Puud: puu, mets, teoreem puu omadustest (6 tingimust), tiputi märgendatud puude loendamine, Prüferi koodid, Cayley teoreem, graafi aluspuu, vähima kaaluga aluspuu, ahne algoritm.
  6. Tasandilised graafid: graafide tasandilisus, graafide K3,3 ja K5 mittetasandilisus, graafide homöomorfism, Kuratowski teoreem (ilma tõestuseta), tasandilise graafi tahud, Euleri valem, järeldused sellest.
  7. Graafide värvimine: graafi värvitavus k värviga, graafi k-kromaatilisus, kromaatiline arv, teoreem graafi värvitavusest, Brooksi teoreem, kuue- ja viievärviteoreemid (tõestustega), neljavärviteoreem (ilma tõestuseta), graafi kromaatiline funktsioon, rekursiivne seos selle leidmiseks.
  8. Intsidentsusstruktuuride põhimõisted: punktid, blokid, intsidentsus, kordsed blokid, näited (afiinne tasand, projektiivne tasand), topeltloendamine.
  9. Steineri süsteemid: Steineri süsteemid S(l,m,n) ja S(2,3,n) (Steineri kolmikute süsteemid (STS)), STS(7) ja STS(9), alamsüsteem, teoreem STSde olemasolust, Steineri nelikute süsteemid.
  10. Disainid: disainid, nende näited, väikeste parameetritega disainid, tuletatud disain, seosed disaini parameetrite vahel, seosed 2-disaini parameetrite vahel, Fisheri võrratus, ruutdisainid, teoreem ruut-2-disainidest (4 tingimust), disaini täiend, triviaalne disain.
  11. Hadamard'i maatriksid: Hadamard'i ülesanne ja selle lahendus, Hadamard'i maatriksid, nende olemasolu tarvilik tingimus, maatriksite Kroneckeri korrutis, teoreem Hadamard'i maatriksite seosest disainidega (Hadamard'i disainid).
  12. Keeled ja automaadid: binaarsed seosed ja maatriksid, nendevaheline seos. Lõplikud automaadid: sõne äratuntavus, keele äratuntavus, keele maatriksesituvus, äratuntavuse ja maatriksesituvuse samaväärsus, lõplikud determineeritud automaadid, teoreem suvalise äratuntava keele äratundmisest lõpliku determineeritud automaadi poolt (sellise automaadi konstrueerimine).
  13. Rühmatoimed: objekti (struktuuri) automorfism, automorfismirühm, selle toime objektil, abstarktne toime (tema aksioomid), orbiit, elemendi stabilisaator.
NB! Eksami kolmandasse (suulisesse) ossa ei tule keelte ja automaatide ega rühmatoimete punkte, samuti Brooksi teoreemi tõestust. Küll aga võib seda materjali vaja minna kirjalike (kontrolltööde) osade sooritamisel.

Kuna üks kursuse eksamil käijatest läbis veidi teistsuguse programmi, ripuvad siin alternatiivsed kordamisküsimused ja eksamipiletid.

Vastu tulles eksaminantide sooviavaldustele ja arvestades, et vastavat infot saladuses nagunii pidada ei õnnestu (pole mõtetki), on siin ka

Eksamipiletid:

  1. Euleri graafid. Fleury algoritm.
  2. Hamiltoni graafid. Turniirid.
  3. Vood võrkudes. Teoreem maksimaalsest voost ja minimaalsest lõikest.
  4. Puud. Aluspuud (ahne algoritm). Märgendatud puude loendamine.
  5. Tasandilised graafid. Euleri valem.
  6. Graafide värvimine. Kromaatiline funktsioon.
  7. Intsidentsusstruktuurid, nende näited, Steineri süsteemid. STS olemasolu teoreem: tarvilikkus. STS olemasolu teoreem: piisavus juhul n=3(mod 6).
  8. STS olemasolu teoreem: piisavus alates juhust n=13.
  9. Disainid (kõik v.a Fisheri võrratus ja ruut-2-disainid).
  10. Fisheri võrratus ja ruut-2-disainid.
  11. Hadamard'i maatriksid ja disainid.
Härmel Nestra loetud osa on saadaval ka dvi-formaadis:
Automaatidest
Rühmatoimetest

1. kontrolltöö ülesanded

1. variant(21.05.97)
2. variant(21.05.97)
3. variant(5.06.97)
4. variant(28.06.97)

2. kontrolltöö ülesanded

2. variant(28.05.97)
1. variant(5.06.97)
3. variant(28.06.97)

Järeleksamil antud ülesanded

1. variant(23.01.98)

Praktikumimaterjalid kevadsemestrist '98

Loengut loeb sedakorda Uno Kaljulaid, mina aga üritan kokku panna väikest praktikumimaterjali. Palju sellest valmis on, võib näha alljärgnevas.

dmprx.ps.gz

30.11.98 toimunud kontrolltöö tulemused.

Praktikum sügis '99

Seekordne lektor Härmel Nestra kirjutas kokku materjali Mengeri teoreemist, mis on siitkättesaadav DVI-formaadis ja PS-formaadis.

Kordamisküsimused DME eksamiks sügisel '99 asuvad siin ning muu eksamisse ja järeltöösse puutuv info siin.

Koduse kontrolltöö arvestuse said üliõpilased, kes lahendasid vähemalt pooled ülesanded õigesti ja tegid seda ISE:

Neile, kes esimesel katsel kodust kontrolltööd tehtud ei saanud, on siin uued ülesanded.

Ja siin on selle kontrolltöö tulemused.