Kombinatorne
strukture
| |
Smjer: |
Nastavni, Teorijska kompjuterska nauka |
| |
Semestar: |
IX
|
| |
Tip kursa: |
Izborni |
| |
Fond sati: |
2+2+0 |
| |
Broj
ECTS kredita: |
10 |
Nastavni program:
- Pojam kombinatorne strukture (kombinatorne
konfiguracije) nad konačnim skupom; Načini predstavljanja kombinatornih
struktura; Matrica incidencije; Izomorfne strukture;
- Blok šema (blok-dizajn) – Pojam i
primjeri; Parametri date blok-šeme; Uravnotežena nepotpuna i uravnotežena
potpuna blok-šema; Potrebni uslovi za egzistenciju uravnotežene nepotpune
blok-šeme; Potrebni i dovoljni uslovi za egzistenciju uravnotežene nepotpune
blok‑šeme (v, r, b, k) nad konačnim skupom;
- Fišerova nejednakost i Štajnerovi
sistemi trojki; Razrješiva blok-šema; Kirkmanov sistem trojki; Simetrična
blok-šema i teorema Bruksa-Rejzera-Čovla;
- Sistemi različitih predstavnika
date konfiguracije (pojam transferzale); Teorema o broju različitih predstavnika
konfiguracije;
- Konačne ravni (projektivna i afina);
- Ekstremalni kombinatorni problemi
(problem o pokrivanju i problem o minimalnom sistemu različitih predstavnika);
- Latinski pravougaonik (pojam,
osobine i primjeri); Veza latinskog pravougaonika reda r nad skupom i
konfiguracije K nad istim skupom; Proširenje latinskog pravougaonika reda r do
latinskog kvadrata reda nad istim skupom; Vrste latinskog kvadrata (ciklički,
simetrični, magični);
Literatura:
-
Igor Š. Milovanović, Emina I. Milovanović:
Diskretna matematika, Univerzitet u Nišu, Elektrotehnički fakultet ,
Niš, 2000
-
Igor Š. Milovanović, Emina I. Milovanović,
Branislav M. Ranđelović: Diskretna matematika, zbirka zadataka,
Univerzitet u Nišu, Elektrotehnički fakultet , Niš, 2001
- M. Holl:
Kombinatorika, Izdateljstvo Mir, Moskva, 1970.