Warranty: This web page is designed for MS Internet Explorer, an application of another program than this one (e.g. Mozilla) , may cause problems with downloading attached files. But these problems are easily overcome if you manually change in the address the “backslash” symbol ‘\’ by “slash” symbol ‘/’.

 

Algebra a diskrétna matematika

 

Prednáška z Algebry a diskrétnej matematiky v akad. roku 2004 – 2005 (click here).

 

Prednášajúci: prof. Ing. Vladimír Kvasnička, DrSc. (garant predmetu)

Ústav aplikovanej informatiky  FIIT STU

miestnosť T005, blok C, prízemie, za Katedro Elektrických strojov a prístrojov,

                   email: kvasnicka@fiit.stuba.sk, telefón (02)60291264, (02)65422707, klapka 105.

 

     doc. RNDr. Jiří Pospíchal, DrSc. (garant predmetu)

Ústav aplikovanej informatiky  FIIT STU

miestnosť D117

                   email: pospichal@fiit.stuba.sk, telefón (02)60291679, (02)65422707, klapka 117.

 

Ročník: bakalárske štúdium, 1. nominálny ročník, druhý (letný) semester

Rozsah: prednáška – 3 hod, seminár – 2 hod.

Prednáška: utorok 7.20-10.05 hod v posluchárni DE300.

Konzultácie s prednášajúcim: dohodnúť vopred emailom.

 

Cvičiaci z Katedry matematiky FEI STU

RNDr. Karla Čipková, PhD., miestnosť: A 414,  telefón: (02)60291472, email: karla.cipkova@stuba.sk,

konzultácie dohodnúť emailom.

doc. Mgr. Gejza Jenča, PhD., miestnosť  A 404, telefón (02)60291853, email: gejza.jenca@stuba.sk

 konzultácie dohodnúť emailom.

Mgr. Dávid Pancza, miestnosť: A 421, telefón: (02)60291729, email: david.pancza@stuba.sk

konzultácie dohodnúť emailom.

 

Cvičiaci z Ústavu aplikovanej informatiky FIIT STU

Mgr. Alena Kovárová, miestnosť D203, telefón: (02)6029109, email: kovarova@fiit.stuba.sk

                                      konzultácie dohodnúť emailom

 

 

Rozvrh cvičení:

 

1

PON

13:05

B101

kr. 3

RNDr. Čipková

2

PON

15:00

B101

kr. 2

RNDr. Čipková

3

UTO

14:00

CD35

kr. 6

doc. Jenča

4

STR

8:15

CD35

kr. 8

doc. Jenča

5

STR

10.10

CD35

kr. 4

doc. Jenča

6

STR

9:15

C301

kr. 5,7

doc. Pospíchal

7

STR

11:10

C301

kr. 15

doc. Pospíchal

8

STR

13:05

CD35

kr. 16

prof. Kvasnička

9

STR

15:00

CD35

kr. 17

Mgr. Kovárová

10

STV

9:15

C517

kr. 10

Mgr. Pancza

11

STV

11:10

C517

kr. 1

Mgr. Pancza

12

STV

9:15

CD35

kr. 9

RNDr. Čipková

13

STV

11:10

CD35

kr. 14

RNDr. Čipková

14

STV

15:00

CD35

kr. 13

RNDr. Čipková

 

 

Ciele predmetu:

Oboznámiť študentov v bakalárskom štúdiu so základnými matematickými štruktúrami, ktoré sú požadované pri štúdiu informatiky. Rozvinúť u študentov schopnosť rigorózneho matematického myslenia pri riešení a formulovaní informatických problémov. Predpoklady na úspešné absolvovanie skúšky z tohto predmetu sú vedomosti z prednášky Matematická logika a základné stredoškolské vedomosti z teórie množín a z algebry.

 

Anotácia predmetu:

Teória matematického dôkazu, charakteristika deduktívneho dôkazy v axiomatickom systéme, základné typy dôkazu, zovšeobecnenie a falzifikácia, induktívny dôkaz. Teória množín  - operácie, množinová algebra, funkcie a relácie, mohutnosť a enumerácia (counting), kombinatorika. Matice – špeciálne matice, operácie nad maticami, inverzná matica, systém lineárnych rovníc, Gaussova eliminačná metóda, determinanty, Cramerove pravidlo. Algebraické štruktúry – binárna operácia a jej vlastnosti, grupy, permutačné grupy. Boolova algebra – základné vlastnosti, Boolove funkcie, klopné obvody, logické siete,  minimalizácia Boolovho výrazu. Teória grafov – definícia a reprezentácia grafov, cesty a kružnice, izomorfizmus, stromy, konštruktívna enumerácia stromov, planárne grafy, usporiadanie, prehľadávanie, najkratšia cesta, problém obchodného cestujúceho, siete a toky.

 

Kľúčové slová:

Dôkaz, matematická indukcia, množiny, kombinatorika, matice, systém lineárnych rovníc, determinanty, algebraické štruktúry, grupy, Boolova algebra a Boolove funkcie, logické siete, grafy, grafové algoritmy.

 

Podmienky úspešného absolvovania:

(1)   Zápočet – získanie najmenej 20 bodov (zo 45 bodov) z 3 písomiek a žiadna neospravedlnená neúčasť na cvičení.

(2)   Skúška – získanie najmenej 56 bodov z celkového počtu 100 bodov (známka E) takto:

(3)  max 45 bodov za tri písomky (3x15=45) v priebehu semestra

(4)  max 55 bodov za písomnú skúšku.

 

 

Pomocné body za nájdenie chyby (podstatnej) v texte prednášky a v cvičeniach (nie v priesvitkách prezenácie)

 

#

študent

body

1

Vladimir Janov

0.5

2

Martin Krcho

1.0

3

Igor Andruska

1.0+1.0+0.5

4

Tomas Valko

1.0+0.5

5

Andrej Matiasovsky

0.5

6

Tibor Racko

0.5

 

Upozornenie: Ak máte pripomienku k textu prednášky alebo k riešeným príkladom, táto musí byť konkrétna a podrobne odôvodnená. Pripomienky typu „zdá sa mi“ a pod. budú ignorované.

 

 

Sylabus prednášky:

 

1.     týždeň (21. 2. 2006). Metódy matematického dôkazu  - deduktívny dôkaz v axiomatickom systéme, základné pravidlá logického usudzovania, priamy dôkaz, nepriamy dôkaz, dôkaz sporom, dôkaz pre rôzne prípady, zovšeobecnenie v predikátovej logike, falzifikácia (kontrapríklad), matematická indukcia.

     Text k prednáške: pdf

     Riešené cvičenia: pdf

     Priesvitky: farebné pdf, čierno-biele pdf, 4 na 1 liste pdf

 

2.     týždeň (28. 2. 2006).  Teória množín I – množina, podmnožina, operácie nad množinami, množinová algebra, mohutnosť a enumerácia (counting), karteziánsky súčin.

     Text k prednáške: pdf

     Riešené cvičenia: pdf

     Priesvitky: farebné pdf, čierno-biele pdf, 4 na 1 liste pdf

 

3.     týždeň (7. 3. 2006). Teória množín II – relácia, operácie nad reláciami, relácia rovnosti, relácia usporiadanosti, Hasseho diagram. Funkcie, zložená funkcia, inverzná funkcia.

     Text k prednáške: pdf

     Riešené cvičenia: pdf

     Priesvitky: farebné pdf, čierno-biele pdf, 4 na 1 liste pdf

 

4.                 týždeň (14. 3. 2006). Kombinatorika I – permutácie, faktoriály,  binomické koeficienty, permutácia a kombinácie

Text k prednáške: pdf

Riešené cvičenia: pdf

Priesvitky: farebné pdf, čierno-biele pdf, 4 na 1 liste pdf

 

1. kontrolná písomka (z prednášok 1. – 4.)  

Písomka bude trvať 30 minút čistého času. Bude obsahovať 5 príkladov, z ktorých je možno získať
celkovo 15 bodov, zo šiesteho "prémiového príkladu" možno získať ďalšie 2 body navyše (čiže 
celkovo 17 bodov). Je povolené použiť ťahák rozsahu jedného listu formátu A4. 
 
Písomka sa bude písať v dvoch termínoch:
 
1. termín
vo štvrtok 16.3.2006 od 19 do 19.30 krúžky 5,7,15,16,17
CD 300 krúžky 5,7, a prvá polovica kr. 15,
DE 300 krúžky 16,17, a druhá polovica kr. 15,
Pred písomkou budú na dverách miestností vyvesené presné 
informácie o rozdelení študentov. 
Príklady: skupina A pdf, skupina B pdf. 
Výsledky: pdf
 
2. termín
a v piatok 17.3.2006 podľa nasledovného harmonogramu:
 
AB 300 o 13:30 krúžky 2, 14, 13 (priezvisko začínajúce na písmená A, B)
DE 300 o 13:30 krúžky 3, 9, 13 (priezvisko začínajúce na písmená C az Z)
AB 300 o 14:15 krúžky 1, 10, 6 ( iba títo študenti: Jancik Roman, Krcho 
Martin, Honsch Marián, Ludvik Martik, Lysina Anton, Lulco Michal, Marcinka 
Marek, Macko Michal, Libosvar Kamil, Majek Stanislav, Kucecka Tomás, Kutenicsova 
Dana, Majer Tomas)
DE 300 o 14:15 krúžky 4,  8, 6 (ostatní študenti z tohto krúžku)
Príklady: pdf
Výsledky: pdf (komplet)
 
Pred písomkou budú na dverách miestností vyvesené vyššie uvedené 
informácie o rozdelení študentov.

 

 

 

5.                 týždeň (21. 3. 2006). Kombinatorika II – enumeračné metódy, rekurentné vzťahy, algoritmy „rozdeľuj a panuj“, generujúce funkcie, metódy zahrnutia a vylúčenia.

Text k prednáške: pdf

Riešené cvičenia: pdf

Priesvitky: farebné pdf, čierno-biele pdf, 4 na 1 liste pdf

 

6.     týždeň (28. 3. 2006). Algebraické štruktúry I – binárne operácie a ich vlastnosti, algebraické štruktúry, grupa, podgrupa, základné vlastnosti grupy, grupové kódy.

     Text k prednáške pdf

     Riešené cvičenia: pdf

Priesvitky: farebné pdf, čierno-biele pdf, 4 na 1 liste pdf

 

7.     týždeň (4. 4. 2006). Algebraické štruktúry II – Boolova algebra, definícia a základné vlastnosti, Boolove funkcie, klopné obvody, logické siete, minimalizácia Boolových výrazov.

Text k prednáške: pdf

Riešené cvičenia: pdf

Priesvitky: farebné pdf, čierno-biele pdf, 4 na 1 liste pdf, prezentácia na AI seminári: farebné pdf, čierno-biela pdf, 4 na 1 liste pdf.

 

8.     týždeň (11. 4. 2006). Maticová algebra I – definícia matice, špeciálne matice, operácie nad maticami, maticová algebra, hodnosť matice, inverzná matica.

     Text k prednáške: pdf

Riešené cvičenia: pdf

Priesvitky: farebné  pdf , čierno-biele pdf ,4 na 1 liste pdf.

 

9.     týždeň (18. 4. 2006). Prednáška sa nekoná

Na seminároch sa cvičí problematika podľa výberu pedagógov.

 

2. kontrolná písomka bude v týždni 17.-21. 4. 2006  (z prednášok 5. – 8.)  

Písomka bude trvať 30 minút čistého času. Bude obsahovať 5 príkladov, z ktorých je možno získať
celkovo 15 bodov, zo šiesteho "prémiového príkladu" možno získať ďalšie 2 body navyše (čiže 
celkovo 17 bodov). Je povolené použiť ťahák rozsahu jedného listu formátu A4. 
Upozornenie: Písomka môže obsahovať príklady na hodnosť matice a inverznú maticu. 
Písomka sa bude písať v dvoch termínoch:
 
1. termín
vo štvrtok 20.4.2006 od 19 do 19.30 krúžky 5,7,15,16,17
CD 300 krúžky 5,7, a prvá polovica kr. 15,
DE 300 krúžky 16,17, a druhá polovica kr. 15.
Príklady: skupina A pdf, skupina B pdf.
Výsledky budú zverejnené dňa 28.4.2006 do 12.00 hod.
 
2. termín
a v piatok 21.4.2006 podľa nasledovného harmonogramu:
 
AB 300 o 13:30 krúžky 2, 14, 13 (priezvisko začínajúce na písmená A, B)
BC 300 o 13:30 krúžky 3, 9, 13 (priezvisko začínajúce na písmená C az Z)
AB 300 o 14:30 krúžky 1, 10, 6 ( iba títo študenti: Jancik Roman, Krcho 
Martin, Honsch Marián, Ludvik Martik, Lysina Anton, Lulco Michal, Marcinka 
Marek, Macko Michal, Libosvar Kamil, Majek Stanislav, Kucecka Tomás, Kutenicsova 
Dana, Majer Tomas)
BC 300 o 14:30 krúžky 4,  8, 6 (ostatní študenti z tohto krúžku)
Príklady: skupina dr. Cipkovej pdf, skupina doc. Jenču pdf, skupina Mgr. Panczu pdf.
 
 
Pred písomkou budú na dverách miestností vyvesené vyššie uvedené 
informácie o rozdelení študentov. 
Výsledky: pdf (komplet)

 

10.            týždeň (25. 4. 2006). Maticová algebra II – systém lineárnych rovníc, Frobeniova veta, Gaussova eliminačná metóda. Determinanty, základné vlastnosti, výpočet determinantu, použitie k riešeniu systému lineárnych rovníc (Cramerove pravidlo).

Text k prednáške: pdf

Riešené cvičenia: pdf

Priesvitky: farebné  pdf , čierno-biele pdf ,4 na 1 liste pdf.

    

11.      týždeň (2. 5. 2006). Teória grafov I – neorientované grafy, základné pojmy, maticová reprezentácia, podgraf, cesty  a cykly v grafe, grafy, súvislosť grafu, Eulerova cesta, Hamiltonov cyklus.

Text k prednáške: pdf

Riešené cvičenia: pdf

Priesvitky: farebné  pdf , čierno-biele pdf ,4 na 1 liste pdf.

 

12.      týždeň (9. 5. 2006). Teória grafov II – cesty v ohodnotených grafoch, planárne grafy, Kuratowskeho veta, farbenie grafov a máp,        Eulerova formula, aplikácie farbenia, minimálna dominujúca vrcholová množina, číslo vrcholovej nezávislosti.

Text k prednáške: pdf

Riešené cvičenia: pdf

     Priesvitky: farebné  pdf , čierno-biele pdf ,4 na 1 liste pdf

 

3. kontrolná písomka (z prednášok 10. – 12.)

Písomka bude trvať 30 minút čistého času. Bude obsahovať 5 príkladov, z ktorých je možno získať
celkovo 15 bodov, zo šiesteho "prémiového príkladu" možno získať ďalšie 2 body navyše (čiže 
celkovo 17 bodov). Je povolené použiť ťahák rozsahu jedného listu formátu A4.

 

Písomka sa bude písať v dvoch termínoch:
 
1. termín
Vo štvrtok 11. 5. 2006 o 19.00 hod. v miestnostiach:
BC300: 5. kr., 7. kr., a 15. kr. (prvá polovica),
BC150: 15. kr. (druhá polovica) a 16. kr.
CD150: 17. kr. 
Príklady: skupina A pdf, skupina B pdf.
 
2. termín
V piatok 12.5.2006 podľa nasledovného harmonogramu: 
AB 300 o 13:30 krúžky 2, 14, 13 (priezvisko začínajúce na písmená A, B)
BC 300 o 13:30 krúžky 3, 9, 13 (priezvisko začínajúce na písmená C az Z)
AB 300 o 14:30 krúžky 1, 10, 6 ( iba títo študenti: Jancik Roman, Krcho 
Martin, Honsch Marián, Ludvik Martik, Lysina Anton, Lulco Michal, Marcinka 
Marek, Macko Michal, Libosvar Kamil, Majek Stanislav, Kucecka Tomás, Kutenicsova 
Dana, Majer Tomas)
BC 300 o 14:30 krúžky 4,  8, 6 (ostatní študenti z tohto krúžku)
Príklady: skupina dr. Čipkovej pdf, skupina Mgr. Panczu pdf, skupina doc. Jenču pdf,
 

Výsledky: pdf (komplet, zverejnené dňa 16.5.2006 o 17.00)

 

 

13.      týždeň (16. 5. 2005). Teória grafov III – stromy ako modely, vlastnosti stromov, binárne prehľadávanie, prefixové kódy, stromy algebraických výrazov, hry.

     (3. kontrolná písomka)

Text k prednáške: pdf

Riešené cvičenia: pdf

     Priesvitky: farebné  pdf , čierno-biele pdf ,4 na 1 liste pdf

 

Náhradné priebežné písomky sa uskutočnia vo štvrtok dňa 18. 5. 2006.

 

Podmienky pre účasť na kontrolnej písomke:

 

Zúčastniť sa písomky môžu študenti, ktorí  majú po tretej kontrolnej písomke sumárne menej ako 20 bodov, čo je podmienka k udeleniu zápočtu (nutná podmienka ku  skúške) alebo  (spomeňte si na tabuľku pravdivostných hodnôt disjunkcie) nepísali danú písomku.

 

(1)   Plný počet bodov sa bude započítavať len študentom, ktorí sa nezúčastnili danej kontrolnej písomky.

(2)   Celkový počet udelených bodov po opravných písomkách u tých študentov, ktorý danú písomku už písali, neprekročí 20 bodov.

 

Čas vymedzený pre jednu písomku je 45 min. Opravné písomky sa píšu v miestnosti DE300 v týchto termínoch :

1.     kontrolná písomka o 19.00 hod.

2.     kontrolná písomka o 19.45 hod.

3.      kontrolná písomka o 20.30 hod. 

 
Príklady: 1. písomka pdf, 2. písomka pdf, 3. písomka pdf.
 
Výsledky: pdf (komplet)

 

 

 

Upozornenie:  Dr. Čipková žiada študentov, ktorí majú NEOSPRAVEDLNENÚ neúčasť na cvičeniach, aby sa kontaktovali s ňou a ospravedlnili svoju neúčasť, v opačnom prípade nedostanú zápočet (nemôžu sa zúčastniť skúšky, aj keď majú dostatočný počet bodov) :

 

Cernansky Oliver (1 krat)

Gabovic Tomas (3 krat)

Ecker Lukas (4 krat)

Derzsi David (3 krat)

Haluska Peter (7 krat)

Marek Jurkemik (4 krat)

Heger Boris (6 krat)

Kepic Martin (2 krat)

Korosi Tomas (4 krat)

 

 

 

Skúška z Algebry a diskrétnej matematiky

 

1. termín:

12. 6. 2006 (pondelok) o 14.00 – 15.30 hod.

 

Upozornenie: Skúšky sa môžu zúčastniť len študenti, ktorým bol cvičiacim pedagógom udelený zápočet.

 

Rozdelenie krúžkov podľa posluchární

 

poslucháreň

krúžky

dozor

AB300

1IN,2IN, prvá polovica 3IN

I. Kapustík, M. Košík a A. Považanová

AB150

4IN,5IN

B. Dado a  M. Lekavý

BC300

6IN, 7IN, prvá polovica 8IN

A. Kovárová, Z. Husárová, V. Kvasnička

BC150

9IN,10IN

J. Žiak a J. Flochová,

CD300

1PI,2PI

I. Polášek a I. Polický

CD150

3PI, druhá polovica 3IN

J. Pospíchal

DE300

I5PI, druhá polovica 8IN

G. Frivolt a V. Rozinajová

DE150

4PI

V. Grlický

 

Oznam pre dozor: Pred písomkou o 13.30 sa stretneme v zasadačke dekanátu, kde odznejú organizačné pokyny a  rozdajú sa písomky.

Príklady (pdf)

Výsledky (pdf)

 

Písomky 1-5 opravoval doc. J. Pospíchal, písomky 6-10 prof. V. Kvasnička,

písomky 11-15 Mgr. A. Kovárová, v prípade že chcete vidieť svoju písomku, obráťťe sa na vyššie

uvedeného pedagóga.

Zapísanie výsledkov do indexu: v stredu 21. 6. 2006 o 10.00 hod. vo vestibule na 1. poschodí, blok D.

Študenti, ktorí si neprišli zapísať známku v tomto termíne, budú si môcť zapísať známku na prvom opravnom termíne, dňa 27. 6. 2006 (utorok) o 11.00 –12.30 hod. v posluchárni DE300.

 

 

 

Skúška z Algebry a diskrétnej matematiky

 

2. termín (opravný):

27. 6. 2006 (utorok) o 11.00 –12.30 hod. v posluchárni DE300

Zapisovať sa do indexov budú individuálne, číslo dverí T005, blok C, prízemie.

Príklady (pdf)

Výsledky (pdf)

 

 

 

 

 

Priebeh skúšky:

1. Písomka bude obsahovať 11 príkladov, každý príklad bude hodnotený 5 bodmi, čiže maximálny počet bodov je 55.  Hodnotenie sa bude vykonávať pomocou tabuľky:

 

stupeň

číselné hodnotenie

počet bodov

A (výborne)

1.0

<94, Ą>

B (veľmi dobre)

1.5

<84,94)

C (dobre)

2.0

<72,84)

D (uspokojivo)

2.5

<62,72)

E (dostatočne)

3.0

<56,62)

FX (nedostatočne)

4.0

<0,56)

 

pričom sa sčítajú body z kontrolných písomiek, zo skúšky a pomocné body.

 

2. Doba trvania písomky je 90 min.

 

3. Písomka bude obsahovať okruh otázok pokrývajúce všetkých 12 kapitol textu prednášky.

 

4. Teoretické otázky (základné definície a vety)  budú taktiež zahrnuté do možných otázok.

 

5. Povoľuje sa vlastný oficiálny ťahák veľkosti A4 – 1 list.

 

      

Literatúra:

[1]                          R. Garnier and J. Taylor: Discrete mathematics for New Technology. Institute of Physics Publishing, Bristol and Philadelphia, 1999. 

[2]                          K. H. Rosen: Discrete Mathematics and Its Applications. McGraw Hillm Boston, 2003.

[3]                          J. Matoušek a J. Nešetřil: Kapitoly z diskrétní matematiky. Matfyzpress,Praha,1996.

[4]                          J. Galanová a P. Kaprálik: Diskrétna matematika. STU, Bratislava, 1997.

[5]                          F. P. Preparata a R. T. Yeh: Úvod do teórie diskrétnych matematických štruktúr. Alfa a SNTL, Bratislava a Praha, 1982.

[6]                          Webovská stránka predmetu na adrese: http://www.fiit.stuba.sk/~kvasnicka/

 

 

Knihy dostupné na internete:

1.                 R. Čada, T. Kaiser a Z. Ryjáček: Diskrétní matematika. Katedra matematiky FAV, Západočeská univerzita v Plzni, 2004.

(pdf)

2.                 P. Olšák: Lineární algebra, Katedra matematiky, FEL ČVUT, Praha, 2000-2002. (pdf)

3.                 L. Motl a M. Zahradník: Pěstujeme lineární algebru, MFF UK, Praha, 1994. (pdf)

4.                 K. H. Rosen: Discrete Mathematics and Its Applications. McGraw Hill, Boston, 1998. (pdf)