Algebra a diskrétna
matematika
Prednáška z Algebry a diskrétnej matematiky
v akad. roku 2007 – 2008 (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 Katedrou
elektrických strojov a prístrojov,
e-mail:
kvasnicka@fiit.stuba.sk, telefón
(02)60291264, (02)65422707, klapka 105.
prof. RNDr.
Jiří Pospíchal, DrSc. (garant predmetu)
Ústav aplikovanej informatiky FIIT STU
miestnosť D117
e-mail: 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: štvrtok
10.00-12.50 hod v posluchárni DE300.
Konzultácie
s prednášajúcim: dohodnúť vopred emailom.
Cvičiaci:
prof. Ing. Vladimír Kvasnička, DrSc., miestnosť T005, blok C, prízemie, za Katedrou elektrických strojov
a prístrojov,
e-mail: kvasnicka@fiit.stuba.sk,
telefón (02)60291264, (02)65422707, klapka 105.
konzultácie
v stredu 14.00-16.00 hod (alebo dohodnúť emailom)
Mgr. Juraj Laca, miestnosť D006,
telefón (02)60291718, email: laca@fiit.stuba.sk
konzultácie dohodnúť emailom
doc. RNDr. Mária Markošová, CSc.,
Katedra aplikovanej informatiky FMFI UK, Mlynská dolina,
email: markosova@ii.fmph.uniba.sk , konzultácie dohodnúť emailom
Mgr.
Pavel Petrovič, PhD., Katedra aplikovanej informatiky
FMFI UK, Mlynská dolina, email: pavel.petrovic@gmail.com
konzultácie dohodnúť emailom
personálna web stránka ADM (click here)
prof.
RNDr. Jiří Pospíchal, DrSc., miestnosť: D117, telefón
(02)60291679, e-mail: pospichal@fiit.stuba.sk,
konzultácie dohodnúť emailom
Ing.
Tomáš Selnekovič, miestnosť D006, telefón:
(02)6029718, email: selnekovic@fiit.stuba.sk
konzultácie dohodnúť emailom
Rozvrh
cvičení:
|
1.
kr. |
STR |
15:00-17:00 |
cd35 |
prof. Kvasnička |
|
2.
kr. |
UTO |
11:00-13:00 |
cd35 |
Mgr. Petrovič |
|
3.
kr. |
UTO |
11:00-13:00 |
bc35 |
Ing. Selnekovič |
|
4.
kr. |
UTO |
11:00-13:00 |
b101 |
doc. Markošová |
|
5.
kr. |
STR |
15:00-17:00 |
b101 |
Mgr. Laca |
|
6.
kr. |
STR |
13:00-15:00 |
b101 |
Mgr. Laca |
|
7.
kr. |
STR |
15:00-17:00 |
ab35 |
prof. Pospíchal |
|
8.
kr. |
STR |
8:00-10.00 |
c201 |
prof. Pospíchal |
|
9.
kr. |
STR |
13:00-15:00 |
cd35 |
prof. Kvasnička |
|
10.
kr. |
STR |
13:00-15:00 |
ab35 |
prof. Pospíchal |
|
11.
kr. |
UTO |
14:00-16:00 |
ab35 |
Ing. Selnekovič |
|
12.
kr. |
UTO |
9:00-11:00 |
b101 |
doc. Markošová |
|
13.
kr. |
UTO |
9:00-11:00 |
cd35 |
Mgr. Petrovič |
|
14.
kr. |
UTO |
7:00-9:00 |
cd35 |
Mgr. Petrovič |
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.
|
Práve vyšla učebnica „Algebra
a diskrétna matematika“, ktorá je v predaji v kníhkupectve
MALÉ CENTRUM.
Vybraný text (PDF) |
Sylabus prednášky:
1. týždeň (25. 9. 2008). 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
2. týždeň (2. 10. 2008). 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.
Priesvitky: pdf
3. týždeň (9. 10. 2008). 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
4. týždeň (16.
10. 2008). Kombinatorika I – permutácie, faktoriály, binomické
koeficienty, permutácia a kombinácie
Priesvitky: pdf
|
1. kontrolná písomka bude v stredu dňa 15. 10. 2008 1. termín o 19.00 hod CD300: 1., 9. krúžok a prvá polovica 11. krúžku (Hyben, Chovanec,
Chropeň, Jančiga, Kardoš, Kentoš, Kincel, Klobušický) DE300: 2., 10. krúžok a druhá polovica 11. krúžku (Klukan, Kmeť,
Kokolevský, Kopkáš Martin, Kosa Matúš, Kozel, Kratochvíl, Kudlačák) CD150: 3. krúžok DE150: 4. krúžok 2. termín o 19.40 hod CD300: 5., 13. krúžok a prvá polovica 12. krúžku (Kušnier,
Kvasnička, Laštinec, Leitman, Letavay, Liďák, Lúčanský,
Macháč) DE300: 6., 14. krúžok a druhá polovica 12. krúžku (Majher, Maron, Martinický, Matula, Matuška, Mazag, Mičica, Mikoczy) CD150: 7. krúžok DE150: 8. krúžok Riešené príklady: pdf Poznámka: Príklad 1 je považovaný za prémiový (hodnotený 2 bodmi), príklad 6 –
prémiový je považovaný za príklad 1 (hodnotený 3 bodmi). Výsledky budú postupne
zverejnené v rámci AIS do 23. 10. 2008. 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 a s kladnou veľkosťou fontov. |
5. týždeň (23. 10. 2008). Kombinatorika
II – enumeračné metódy, rekurentné vzťahy, algoritmy
„rozdeľuj a panuj“, generujúce funkcie, metódy zahrnutia
a vylúčenia.
Priesvitky: pdf
6. týždeň (30. 10. 2008). Algebraické
štruktúry I – binárne operácie a ich vlastnosti, algebraické
štruktúry, grupa, podgrupa, základné vlastnosti grupy, grupové kódy.
Priesvitky: pdf
7. týždeň (6. 11. 2008). Algebraické štruktúry II – Boolova algebra,
definícia a základné vlastnosti, Boolove funkcie, logické siete,
minimalizácia Boolových výrazov.
Priesvitky:
pdf
8. týždeň (13. 11. 2008). Maticová
algebra I – definícia matice, špeciálne matice, operácie nad maticami,
maticová algebra, hodnosť matice, inverzná matica.
Priesvitky:
pdf
9. týždeň (20. 11. 2008). 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
|
2. kontrolná písomka (z prednášok 4. – 8.)
dňa 20. 11. 2008 (štvrtok) o 19.00 a 19.40 hod
v posluchárňach DE 300, CD 300, CD 150 a BC 150. 1. termín o 19.00 hod CD300: 1., 9. krúžok a prvá polovica 11. krúžku (Hyben, Chovanec,
Chropeň, Jančiga, Kardoš, Kentoš, Kincel, Klobušický) DE300: 2., 10. krúžok a druhá polovica 11. krúžku (Klukan, Kmeť,
Kokolevský, Kopkáš Martin, Kosa Matúš, Kozel, Kratochvíl, Kudlačák) CD150: 3. krúžok BC150: 4. krúžok 2. termín o 19.40 hod CD300: 5., 13. krúžok a prvá polovica 12. krúžku (Kušnier,
Kvasnička, Laštinec, Leitman, Letavay, Liďák, Lúčanský,
Macháč) DE300: 6., 14. krúžok a druhá polovica 12. krúžku (Majher, Maron, Martinický, Matula, Matuška, Mazag, Mičica, Mikoczy) CD150: 7. krúžok BC150: 8. krúžok Riešené príklady: pdf Výsledky budú postupne
zverejnené v rámci AIS do 27. 11. 2008. 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 a s kladnou veľkosťou
fontov. |
10. týždeň (27. 11. 2008). 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: farebné pdf
11. týždeň (4. 12. 2008). 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: farebné pdf
12. týždeň (11. 12. 2008).
Teória grafov III – stromy ako modely, vlastnosti stromov, binárne prehľadávanie,
prefixové kódy, stromy algebraických výrazov, hry.
Priesvitky: farebné pdf
|
3. kontrolná písomka (z
prednášok 9. – 11.) dňa 11. 12.
2008 (štvrtok) o 19.00 a 19.40 hod v posluchárňach DE
300, CD 300, CD 150 a BC 150. 1. termín o 19.00 hod CD300: 1., 9. krúžok a prvá polovica 11. krúžku (Hyben, Chovanec,
Chropeň, Jančiga, Kardoš, Kentoš, Kincel, Klobušický) DE300: 2., 10. krúžok a druhá polovica 11. krúžku (Klukan, Kmeť, Kokolevský,
Kopkáš Martin, Kosa Matúš, Kozel, Kratochvíl, Kudlačák) CD150: 3. krúžok BC150: 4. krúžok 2. termín o 19.40 hod CD300: 5., 13. krúžok a prvá polovica 12. krúžku (Kušnier,
Kvasnička, Laštinec, Leitman, Letavay, Liďák, Lúčanský,
Macháč) DE300: 6., 14. krúžok a druhá polovica 12. krúžku (Majher, Maron, Martinický, Matula, Matuška, Mazag, Mičica, Mikoczy) CD150: 7. krúžok BC150: 8. krúžok Riešené príklady: pdf Výsledky budú postupne
zverejnené v rámci AIS do 15. 12. 2008. 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 a s kladnou veľkosťou fontov. |
|
Náhradné priebežné písomky pre
všetkých študentov, bez ohľadu na to, kto ich cvičí, Zmena dátumu!
Náhradná písomka bude 18. 12. 2008 o 19.15h v DE300 (predbežne, ako
prvá bude nahradzovaná 3. kontrolná písomka 19.15-19.45, potom 2. kontrolná
písomka a nakoniec 1. kontrolná písomka, pokiaľ ale nebude nikto
chcieť písať dve alebo tri náhradné písomky, je možné, že sa
časové termíny zlúčia a všetci začnú v 19.15) Poznámka: Ospravedlňujem sa
za spôsobené zmätky okolo dátumu náhradnej písomky, ktoré som spôsobil
hromadným mailom z AIS. Samozrejme, platí termín 18. 12. 2008. 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 30 min.
Riešené príklady 1. náhradná kontrolná písomka: pdf Riešené príklady 2. náhradná kontrolná písomka: pdf Riešené príklady 3. náhradná kontrolná písomka: pdf |
Skúška z Algebry a diskrétnej
matematiky
Dátum skúšky je 14. 1. 2009 v čase 10.30
– 13.15, miestnosti: AB300, BC300, CD300, DE300, BC150, DE150. Podrobnosti sú
špecifikované dolu. Upozornenie: Skúšky sa môžu zúčastniť len študenti, ktorí získali
z cvičenia aspoň 20 bodov. 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:
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. Upozornenie: Skúšky sa môžu zúčastniť len študenti, ktorí získali
z cvičenia aspoň 20 bodov. Rozdelenie krúžkov podľa posluchární
Príklady (pdf) Známky sa budú zapisovať do
indexu v piatok 23. 1. 2009 o 10.00 hod vo vestibule na 1.
poschodí, blok D
|
|
bude 2.2.2009 o 13.30-15.00 v DE300, podrobnosti
budú oznámené neskoršie. Opravnej písomky sa môže zúčastniť len
ten študent, ktorý nedosiahol 56 bodov. Príklady (pdf) Známky sa budú zapisovať do
indexu vo štvrtok 5. 2. 2009 o 10.00 hod vo vestibule na 1.
poschodí, blok D Finálny histogram výsledkov ku dňu 5.2.2009
|
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.
[7]
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)