Algebra a diskrétna matematika

akad. r. 2014 – 2015, zimný semester

 

 

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

Ústav aplikovanej informatiky  FIIT STU

miestnosť 403, 4. poschodie,

                   e-mail: kvasnicka@fiit.stuba.sk, telefón (02)21022 403

    prof. RNDr. Jiří Pospíchal, DrSc.

                        Ústav aplikovanej informatiky  FIIT STU

miestnosť 404, 4. poschodie

                   e-mail: pospichal@fiit.stuba.sk, telefón (02)21022 404

 

 

Prednášajú: prof. Ing. Vladimír Kvasnička, DrSc.

                      prof. RNDr. Jiří Pospíchal, DrSc.

 

http://math.chtf.stuba.sk/staff/kvasnicka/photo2.jpg

 

 

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

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

               

 

 

Zoznam cvičiacich predmet ADM v zimnom semestri akad. roku 1914-15:

#

Meno

pracovisko

email

1

Ing. Ladislav Clementis

UAI FIIT STU

ladislav.clementis@stuba.sk

2

Mgr. Kristína Čevorová

MU SAV

cevorova@mat.savba.sk

3

Doc. RNDr. Dušan Guller, PhD.

KAI  FMFI  UK

guller@ii.fmph.uniba.sk

4

Doc. RNDr, Pavel Chalmoviansky, PhD.

KAG  FMFI  UK

pavel.chalmoviansky@fmph.uniba.sk

5

PaedDr. Lilla Koreňová, PhD,

KAG  FMFI  UK

korenova@fmph.uniba.sk

6

Doc. RNDr. Mária Markošová, PhD.

KAI  FMFI  UK

markosova@fmph.uniba.sk

7

Mgr. Andrej Ridzik

UI SAV

andrej.ridzik@savba.sk

8

Ing. Juraj Pálfy, PhD.

UI SAV

juraj.palfy@savba.sk

9

RNDr. Pavel Petrovič, PhD,

KAI FMFI UK

pavel.petrovic@gmail.com

 

 

 

 Rozvrh predmetu ADM, zimný semester, akad. rok 2013-14

Prednáška: streda, 10.00 – 12.30 hod., DE150 aDE300 (posluchárne FEI STU, prízemie, blok D, vstup do DE150 je z -1. poschodia)

Cvičenia:

#

deň

čas

miestnosť

cvičiaci

1

pondelok

7.00-8.40 

1.37

Mgr. Čevorová

2

pondelok

7.00-8.40

1.38

Doc. Koreňová

3

pondelok

9.00-10.40

1.37

Mgr. Čevorová

4

pondelok

9.00-10.40

1.38

Mgr. Ridzik

5

pondelok

11.00-12.40

1.37

Mgr. Čevorová

6

pondelok

11.00-12.40

1.38

Mgr. Ridzik

7

pondelok

15.00-16.40

1.30a

Doc. Guller

8

pondelok

15.00-16.40

1.39

Dr. Petrovič

9

pondelok

17.00-18.40

1.30a

Doc. Guller

10

pondelok

17.00-18.40

1.39

Dr. Petrrovič

11

pondelok

19.00-20.40

1.30a

Doc. Guller

12

pondelok

19.00-20.40

1.39

Dr. Petrovič

13

utorok

7.00-8.40 

1.37

Dr. Pálfy

14

utorok

7.00-8.40

1.38

Ing. Clementis

15

utorok

9.00-10.40

1.37

Dr. Pálfy

16

utorok

9.00-10.40

1.38

Ing. Clementis

17

utorok

13.00-14.40

1.39

Doc. Markošová

18

utorok

15.00-16.40

1.39

Doc. Koreňová

19

utorok

17.00-18.40

1.39

Doc. Koreňová

20

štvrtok

14.00-15.50

1.30a

Doc. Chalmoviansky

21

štvrtok

16.00-17.50

1.30a

Doc. Chalmoviansky

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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ú stredoškolské  vedomosti z logiky a teórie množín.

 

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. Polynómy, algebraické rovnice, rozklad. 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 9 bodov (z 20 bodov) z písomky 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:

(a) max 20 bodov za písomku v priebehu semestra

(b) max 80 bodov za písomnú skúšku.

 

Stupnica hodnotenia na STU

stupeň

číselné hodnotenie

počet bodov

A (výborne)

1.0

<92, Ą)

B (veľmi dobre)

1.5

<83,92)

C (dobre)

2.0

<74,83)

D (uspokojivo)

2.5

<65,74)

E (dostatočne)

3.0

<56,65)

FX (nedostatočne)

4.0

<0,56)

 Literatúra

[1]                        V. Kvasnička a J. Pospíchal: Algebra a diskrétna matematika. STU Press, Bratislava, 2008.

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

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

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

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

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

 

Text učebného textu „Algebra a diskrétna  matematika“ (pdf)

 

Sylabus prednášky:

 

1. týžden: (24 .9. 2014) (prednáša VK a JP)

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.

          Priesvitky: (pdf)

          Text prednasky: (pdf)

          Riesene priklady: (pdf)

 

2. týžden: (1.10.2014)  (prednáša VK a JP)

Teória množín Imnožina, operácie nad množinami, množinová algebra, mohutnosť a enumerácia, karteziánsky súčin

          Priesvitky: (pdf)

          Text prednášky: (pdf)

          Riešené priklady: (pdf)

 

 

3.                týždeň (8.10.2014 (VK a JP)).

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.

         Priesvitky: (pdf)

         Text prednášky: (pdf)

         Riešené príklady: (pdf)

 

4. týždeň (15.10. 2014 (JP a VK)). 
Kombinatorika  – permutácie, faktoriály,  binomické koeficienty, permutácia a kombinácie ,
metóda inklúzie a exklúzie

      Priesvitky: (pdf)

      Text prednášky: (pdf)

      Riešené príklady: (pdf)

 

5.                týžden (22.10.2014  (VK a JP))

Algebraické štruktúry I – binárne operácie a ich vlastnosti, algebraické štruktúry, grupa, podgrupa, základné vlastnosti grupy, grupové kódy, Boolova algebra,

definícia a základné vlastnosti, Boolove funkcie,

       Priesvitky: (pdf)

      Text prednášky: (pdf)

      Riešené príklady: (pdf)

 

6. týždeň  (29. 10.. 2014 

Kontrolná písomka  bude trvať 45 minút čistého času. Bude obsahovať 5 príkladov z prednášok 1-5, z ktorých je možno získať celkovo 20 bodov (po 4 bodoch). Je povolené použiť vlastnoručne písaný (nie xeroxovaný) ťahák  rozsahu jedného listu formátu A4 bez riešených príkladov (teda obsahujúci vzorčeky a vety). 1. písomka (pdf)

Písomka sa bude konat v stredu 29.11.  v čase prednášky a bude organizovaná takto:

1. termín 10.00 – 10.45

    V posluchárni DE150   budú krúžky 1 -4   (dozor Kvasnička a Ing. Clementis)

    V posluchárni DE 300  budú krúžky 5 – 10 (dozor Pospíchal a Ing. Filipek)

2. termín 10.55 – 11.40

    V posluchárni DE150 budú krúžky 11 – 14 (dozor Kvasnička a Ing. Clementis)

    V posluchárni  DE300 budú krúžky 15 – 21  (dozor Pospíchal a Ing. Filipek)

Poznámka: Číslovanie krúžkov bolo prevzaté z tabuľky umiestnenej v hornej časti tejto stránky. Preto študenti ľahko zistia svoje číslo, keď vyhľadajú v zmienenej hornej tabuľke podľa svojho rozvrhu do ktorého krúžku patria.

Tak napr. ak mate cvičenie v útorok v čase 9.00 – 10.40 v posluchárni 1.37, potom patríte do 15. krúžku.

Písomka (pdf)

 

 

7.                týždeň  (5. 11.  2014 (JP a VK)).

Algebraické štruktúry II – spínacie obvody, logické obvody, minimalizácia Boolových výrazov pomocou Quine a McCluskey metódy logické siete, minimalizácia Boolových výrazov.

      Priesvitky: (pdf)  

      Text prednášky: (pdf)

      Riešené príklady: (pdf)

 

8.                týždeň (12. 11. 2014 (JP a VK)).

Maticová algebra I – definícia matice, špeciálne matice, operácie nad maticami, maticová algebra, hodnosť matice, inverzná matica.

      Priesvitky: (pdf)  

      Text prednášky: (pdf)

      Riešené príklady: (pdf)


9. týždeň (19. 11. 2014 (JP a VK)).

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).

       Priesvitky: (pdf) 

      Text prednášky: (pdf)

      Riešené príklady: (pdf)

 

10. týždeň (26. 11. 2014 (JP)).

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.

      Priesvitky:   (pdf)

      Text prednášky: (pdf)

      Riešené príklady: (pdf)

 

11. týždeň (3. 12. 2014 (JP)).

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.

          Priesvitky: (pdf)

           Text prednášky: (pdf)

            Riešené príklady: (pdf)

 

12. týždeň (10. 12. 2014  (JP )). 

Teória grafov III – stromy ako modely, vlastnosti stromov, binárne prehľadávanie, prefixové kódy, stromy algebraických výrazov, hry.

       Priesvitky: (pdf)  

      Text prednášky: (pdf)

      Riešené príklady: (pdf)

 Prednáška bude trvať do 11.30 hod, potom bude opravná písomka o 11.45.

Podmienka pre účasť na opravnej písomke je dosiahnutie menej ako 9 bodov.

Opravná písomka je len pre študentov, ktorí nedosiahli dostatočný počet bodov na zápočet

(aj pre tých, čo zo závažných dôvodov nepísali kontrolnú písomku).

Čas vymedzený pre písomku je 45 min. 

Pisomka (pdf)

 

*********************************************************************************************************************

Písomná skúška z ADM sa bude konať dňa 12. 1. 2015 o 10.30 hod  (opravný termín bude 5.2.2015)

Priebeh skúšky:

1. Písomka bude obsahovať 8 príkladov, každý príklad bude hodnotený 10 bodmi, čiže maximálny počet bodov je 80.

 Hodnotenie sa bude vykonávať pomocou tabuľky uvedenej vyššie.

 1. Písomka bude obsahovať okruh otázok pokrývajúcich prebrané témy prednášky.

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

 3. Povoľuje sa vlastný oficiálny ťahák veľkosti A4 – 1 list písaný rukou.


Písomná skúška sa koná v miestnostiach:

 

(1)       U120 (dozor: Ing. J. Balažia, Ing. R. Bencel), krúžky 1, 5, 6

(2)       U80   (dozor: Ing. M. Blšták, Ing. M. Bystrický) , krúžky 13, 14

(3)       U40 (1.40)   (dozor: Ing. L. Clementis) , krúžok 2

(4)       T40 (1.28-29) (dozor: Ing. J. Filípek) krúžok 3

(5)       ACPU (dozor: Ing. T. Frťala, Ing. T. Halagan, Ing. I. Hucková a ), krúžky 8, 10, 11, 12

(6)       PU1 (dozor: Ing. P. Kapec, PhD),  krúžok 9

(7)       PU2 (dozor: Ing. O. Kaššák), krúžok 15

(8)       Sála – vestibul na -1. poschodí (dozor: Ing. T. Kováčik, Ing. R. Roštecký, Ing. V. Šulák), krúžky 16, 17, 18, 19, 20, 21

(9)       DLSS (1.30AB) (dozor: Ing. D. Zeleník, PhD.), krúžok 7

(10)            Zasadačka Ústavu aplik. Informatiky, č.d. 4.08 (dozor: Ing. Ján Hudec, PhD), krúžok 4

Príklady písomky (pdf)

 

Poznámka: čísla krúžkov sú uvedené v tabuľka na začiatku tejto web stránky!!

 

Opravná písomná skúška z ADM bude sa konať vo štvrtok 5.2.2015 v miestnosti U120 o 10.30 hod.

Dozor na skúške budú mať Ing. J. Balažia, Ing. R. Bencel, Ing. M. Blšták a Ing. M. Bystrický, stretneme sa o 10.00 hod

v malej zasadačke č.d. 4.20 o 10.00 hod, dozor preberie dokumentáciu a inštrukcie k písomke.

Priebeh opravnej skúšky je uvedený vyššie.

Poznámka: Výsledky budú odovzdané na študijné oddelenie v piatok 6.2.2015 o 10.30 hod., po tomto čase už nemá zmysel

                   chodiť za mnou  a orodovať o pridanie 1-2 bodíkov!!!

Príklady písomky (pdf)

 

 

********************************************************************************************************************