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.
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
[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 I
– množ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)
********************************************************************************************************************