Algebra a diskrétna matematika
Prednáška z Algebry a diskrétnej matematiky
v akad. roku 2006 – 2007 (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: utorok 7.30-10.00 hod v posluchárni DE300.
Konzultácie
s prednášajúcim: dohodnúť vopred emailom.
Cvičiaci:
prof.
RNDr. Jiří Pospíchal, DrSc., miestnosť: D117, telefón
(02)60291679, e-mail: pospichal@fiit.stuba.sk,
konzultácie dohodnúť emailom
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
dohodnúť emailom
Mgr.
Alena Kovárová, miestnosť D203, telefón: (02)6029109,
email: kovarova@fiit.stuba.sk
konzultácie 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)
Rozvrh
cvičení:
|
1.
kr. |
STR |
11:00-13:00 |
cd35 |
Mgr. Kovárová |
|
2.
kr. |
ŠTV |
9:00-11:00 |
c101 |
prof. Kvasnička |
|
3.
kr. |
STR |
9:00-11:00 |
cd35 |
prof. Pospíchal |
|
4.
kr. |
PON |
11:00-13:00 |
cd35 |
Mgr. Petrovič |
|
5.
kr. |
ŠTV |
16:00-18:00 |
cd35 |
doc. Markošová |
|
6.
kr. |
ŠTV |
11:00-13:00 |
c517 |
Mgr. Laca |
|
7.
kr. |
STR |
7:00-9:00 |
cd35 |
prof. Pospíchal |
|
8.
kr. |
ŠTV |
7:00-9:00 |
c101 |
prof. Kvasnička |
|
9.
kr. |
PON |
9:00-11:00 |
cd35 |
Mgr. Petrovič |
|
10.
kr. |
STR |
14:00-16:00 |
cd35 |
Mgr. Kovárová |
|
11.
kr. |
ŠTV |
11:00-13:00 |
c101 |
prof. Kvasnička |
|
12.
kr. |
ŠTV |
9:00-11:00 |
c517 |
Mgr. Laca |
|
13.
kr. |
ŠTV |
14:00-16:00 |
cd35 |
doc. Markošová |
|
14.
kr. |
PON |
13:00-15:00 |
cd35 |
Mgr. Petrovič |
|
15.
kr. |
PON |
15:00-17:00 |
cd35 |
prof. Pospíchal |
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.
Sylabus
prednášky:
1. týždeň (19. 2. 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.
Text
k prednáške: pdf
Riešené cvičenia: pdf
Priesvitky:
pdf
2. týždeň (26. 2. 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.
Text k prednáške: pdf
Riešené cvičenia: pdf
Priesvitky:
pdf
3. týždeň (4. 3. 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.
Text k prednáške: pdf
Riešené
cvičenia: pdf
Priesvitky: pdf
4. týždeň (11.
3. 2008). Kombinatorika I – permutácie, faktoriály, binomické
koeficienty, permutácia a kombinácie
Text k prednáške: pdf
Riešené cvičenia: pdf
Priesvitky: pdf
|
1. kontrolná písomka (z prednášok 1. – 3.) Písomka bude vo štvrtok 13. 3. 2008
v posluchárňach AB300, AB150, CD300, DE150 a v dvoch
termínoch o 19.00 hod a 19.45 hod. Rozdelenie termínov podľa krúžkov: 1.
termín o 19.00 hod AB300: 1., 2. a prvá polovica 3. krúžku CD300: druhá polovica 3. krúžku, 4. a 5.
krúžok AB150: 6. krúžok DE150: 7. krúžok 2.
termín o 19.45 hod AB300: 8., 9. a 10. krúžok (študenti 2.
ročníka, ktorí sa zúčastňujú cvičení
s uvedenými krúžkami sa presunú do posluchárne AB150) CD300: 11., 12. a 13. krúžok AB150: 14. krúžok DE150: 15. krúžok Riešené príklady: pdf Výsledky budú postupne
zverejnené v rámci AIS do 20. 3. 2008. Upozornenie: V priebehu písomky pedagogický dozor vykoná prezenciu, doneste si študentský preukaz
s fotografiou. Písomka trvá 30 minút čistého času. Obsahuje 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ň (18. 3. 2008). 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: pdf
6. týždeň (1. 4. 2008). 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:
pdf
7. týždeň (8. 4. 2008). Algebraické štruktúry II – Boolova algebra,
definícia a základné vlastnosti, Boolove funkcie, logické siete,
minimalizácia Boolových výrazov.
Text
k prednáške: pdf
Riešené
cvičenia: pdf
Priesvitky:
pdf
8. týždeň (15. 4. 2008). 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:
pdf
|
2. kontrolná písomka bude vo štvrtok dňa 17. 4. 2008
o 19.00 hod a 19.45 hod z prednášok 4. – 7. 1.
termín o 19.00 hod AB300: 1., 2. a prvá polovica 3. krúžku CD300: druhá polovica 3. krúžku, 4. a 5.
krúžok AB150: 6. krúžok DE150: 7. krúžok 2.
termín o 19.45 hod AB300: 8., 9. a 10. krúžok (študenti 2.
ročníka, ktorí sa zúčastňujú cvičení
s uvedenými krúžkami sa presunú do posluchárne AB150) CD300: 11., 12. a 13. krúžok AB150: 14. krúžok DE150: 15. krúžok Riešené príklady: pdf Výsledky budú postupne
zverejnené v rámci AIS do 24. 4. 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. |
9. týždeň (22. 4. 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).
Text k prednáške: pdf
Riešené
cvičenia: pdf
Priesvitky: pdf
10. týždeň (29. 4. 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.
Text k prednáške: pdf
Riešené
cvičenia: pdf
Priesvitky: farebné pdf
11. týždeň (6. 5. 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.
Text k prednáške: pdf
Riešené
cvičenia: pdf
Priesvitky: farebné pdf
|
3. kontrolná písomka (z prednášok 8. – 10.) bude dňa 6. 5. 2008
o 19.00 hod a 19.45. 1.
termín o 19.00 hod AB300: 1., 2. a prvá polovica 3. krúžku CD300: druhá polovica 3. krúžku, 4. a 5.
krúžok DE300:
6.,7. krúžok 2.
termín o 19.45 hod AB300: 8., 9. a 10. krúžok (študenti 2.
ročníka, ktorí sa zúčastňujú cvičení
s uvedenými krúžkami sa presunú do posluchárne
DE300) CD300: 11., 12. a 13. krúžok DE300:
14.,15. krúžok Riešené príklady: pdf Výsledky budú postupne
zverejnené v rámci AIS do 13. 5. 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. |
12. týždeň (13. 5. 2008). Teória grafov III – stromy ako modely, vlastnosti stromov, binárne prehľadávanie,
prefixové kódy, stromy algebraických výrazov, hry.
Text k prednáške: pdf
Riešené
cvičenia: pdf
Priesvitky: farebné pdf
|
Náhradné priebežné písomky pre
všetkých študentov, bez ohľadu na to, kto ich cvičí, dňa 14.5. (streda) o 19.00, v CD150 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 náhradnej 1. písomky: pdf Riešené príklady náhradnej 2. písomky: pdf Riešené príklady náhradnej 3. písomky: pdf |
Skúška z Algebry a diskrétnej matematiky
1. termín: 13.6. 2008 (piatok) o 10.30 – 12.00 hod. 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í
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. Oznam pre dozor: Pred písomkou o 10.15 sa stretneme vo vestibule pred dekanátom, kde
odznejú organizačné pokyny a
rozdajú sa písomky. Písomky sa budú odovzdávať v kancelárii
prof. Kvasničku (T005). Prosíme dozor, aby rozdelil písomky podľa
krúžkov, opravovať písomky budú pedagógovia, ktorí vedú cvičenia. Príklady (pdf) Známky sa budú zapisovať do indexu 20.6.2008
o 14.00 vo vestibule na 1. poschodí, blok D. Pri zápise známky
sa už písomka nemôžu z časových dôvodov pozerať, pokiaľ
si ich chcete pozriet, musíte predtým navštíviť pedagóga, ktorý vedie
cvičenie vo vašom krúžku.
|
NEW
|
Druhý termín skúšky je 2. 7. 2008 o 10.30 hod v posluchárni DE300 , písomku môžu písať študenti 47813, 17495, 47828, 47992, 36218,
47871, 17000, 48116, 47894, 48016, 48099, 47926, 48026, 48029, 47931, 48118,
47949, 47950, 47901 Príklady (pdf) |
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)