FMMMB0417 Diskrečioji matematika 2

 

MODULIO DARBO PROGRAMA

 

Modulio kodas: FMMMB0417

Modulio pavadinimas: Diskrečioji matematika 2

Kreditų skaičius: 4

Valandų  skaičius  per  semestrą:

 

paskaitos

48

laboratoriniai darbai

16

pratybos

16

 

 

  1. Paskaitos

 

Eil. Nr.

Tema, turinys

 

val.

1.

Saryšių teorija. Aibių Dekarto sandauga. Sąryšiai, jų savybės. Veiksmai su sąryšiais. Saryšių kompozicija. Laipsniai. Sąryšių  algebra. Ekvivalentumas. Ekvivalentumo klasės. Faktoraibės. Tvarkos sąryšis. Minimalieji ir maksimalieji elementai. Sutvarkytosios aibės. Sąryšio tranzityvusis ir refleksyvusis uždariniai. Funkcijos. Aibės ir atvaizdžiai. Injekcija, siurjekcija, bijekcija. Perstatos.

 

10

2.

Grafų teorijos pagrindinės sąvokos. Apibrėžimai. Gretimumas. Grafų pografiai. Neorientuotojo grafo komponentės bei jungumas. Maršrutai, grandinės, ciklai. Atstumas tarp grafo viršūnių. Orientuotieji grafai ir sąryšiai, įėjimo ir išėjimo puslaipsniai. Incidencijų ir gretimumo matricos. Grafų sąjungos, sandaugos, ciklų matricos. Grafų izomorfizmas. Žymėtieji ir nežimietieji grafai. Invariantai. Planarieji grafai.

 

8

3.

Grafų analizė. Sujungimo taškai. Tiltai ir blokai. Skiriančioji aibė. Kirpis. Srautas. Maksimalaus srauto radimas. Trumpiausi keliai. Orientuotojo grafo pusmaršrutis. Grafo stiprumas. Bazė. Branduolys. Paieška grafuose. Medžiai. Orientuotieji, sutvarkytieji, binarieji medžiai. Medžių pateikimas kompiuterio atmintyje. Rūšiavimo medžiai. Karkasai. Grafų ciklai. Ciklomatinis skaičius. Oilerio ir Hamiltono ciklai. Nepriklausomi ciklai. Oilerio ciklų konstravimas. Komivojažieriaus uždavinys. Grafų nepriklausomosios aibės ir nuspalvinimas. Grafo stabilieji poabiai. Grafo vidinio ir išorinio skaičiai.  Stabiliųjų poaibių konstravimas. Taisyklingasis nuspalvinimas. Grafo chromatinis skaičius. Nuspalvinimo algoritmai.

 

18

4.

Grafų analizės algoritmai. Algoritmų sudėtingumas. Individualaus uždavinio matmuo. Polinominis ir eksponentinis sudėtingumas. Sunkieji uždaviniai. Sunkiųjų uždavinių pavyzdžiai. NP ir NPC uždavinių klasės.

 

6

5.

Informacijos teorijos elementai. Informacijos šaltinio entropija. Prefeksinio kodo sąvoka. Optimalusis kodavimas. Klaidas randantys bei taisantys kodai. Kriptografijos uždaviniai ir principai. Atvirojo rakto sistemos. RSA algoritmas. Elektroninis parašas.

 

6

 

Iš viso:

48

                     

  1. Laboratoriniai darbai

 

Eil. Nr.

Tema, turinys

 

val.

1.

Diskrečiosios matematikos elementai Maple terpėje.

 

6

2.

Kombinatoriniai algoritmai.

 

5

3.

Rekurenčiosios lygtys.

 

5

 

Iš viso

16

                     

  1. Pratybos

 

Eil. Nr.

Tema, turinys

 

val.

1.

Sąryšių savybės. Veiksmai su sąryšiais. Sąryšių uždariniai.

 

3

2.

Grafų teorijos pagrindinės sąvokos.

 

2

3.

Grafų izomorfizmas.

 

1

4.

Grafų jungimas.

 

1

5.

Orientuotieji, sutvarkytieji, binarieji medžiai.

 

1

6.

Grafų ciklai

 

2

7.

Grafo vidinio ir išorinio skaičiai.

 

2

8.

Nuspalvinimo algoritmai.

 

2

9.

Algoritmų sudėtingumas.

 

2

 

Iš viso

16

 

  1. Namų darbai

 

Eil. nr.

Tema, turinys

 

val.

1.

Komivojažieriaus uždavinys.

 

10

2.

Klaidas randantys bei taisantys kodai.

 

10

 

Iš viso

20

                   

 

 

  1. Literatūra

 

  1. K. Plukas, E. Mačikėnas, B. Jarašiūnienė, I. Mikuckienė. Taikomoji diskrečioji matematika: vadovėlis. Kaunas: Technologija, 2003, 330 p.
  2. V. Stakėnas . Informacijos kodavimas. (Mokomoji priemonė). Vilnius: VU, 1996.
  3. A. Žilinskas, G. Leonavičius, E. Valavičius. Informatika (vadovėlis aukštosiosm mokykloms). V.: Aldorija, 2000.
  4. O. Ore. Grafai ir jų pritaikymas. Vilnius: Mintis, 1973.
  5. Garey M.R. and Johnson D.S. Computers and Intractability. A Guide to the Theory of NP-Comleteness. New Jersey, Bell Laboratories Murray Hill, 1977. (Yra šios knygos vertimas į rusų kalbą. Maskva, Mir, 1982).
  6. J. A. Anderson. Discrete Mathematics with combinatorics. New Jersey: Prentice Hall, 2001. (Yra šios knygos vertimas į rusų kalbą: Maskva: Viljams, 2003).
  7. V. K. Balakrishman. Introductory Discrete mathematics. 1991.
  8. O. Nicodemi. Discrete mathematics. New York, 1987.
  9. B. Kolman and R. C. Busby. Discrete Structures with Applications. New Jersey, 1987.
  10. F. A. Novikov. Diskretnaja matematika dlia programmistov. Sankt-Peterburg: Piter, 2000, 304
  11. V. M. Fomičev. Diskretnaja matematika i kriptologija. Kurs lekcii. M: DIALOG_MIFI, 2003, 400 p.

 

 

 

Programą sudarė

doc.A. Krylovas

 

 

 

 

 

 

v., pavardė                                            parašas                                                                  data

 

Katedros vedėjas

prof. R.Čiegis

 

 

 

 

 

 

v., pavardė                                            parašas                                                                  data

Studijų komiteto

(krypties komisijos)

pirmininkas

prof. R.Čiegis

 

 

 

 

 

 

v., pavardė                                            parašas                                                                  data