Diszkrét matematika I középszint, előadás


Az előadás helye és ideje: Hétfő 8.15-11.00, Déli épület 0-821, Bolyai János terem

Gyakorlat

A gyakorlati jegy feltétele, a gyakorlaton való részvétel, legfeljebb 3 hiányzással. A gyakorlatok elején a gyakorlatvezető rövid tesztet irat az előadáson elhangoztt egyszerű fogalmakból, definiciókból, tételekből, melyre +1/-1 eredményt lehet kapni (hiányzás esetén 0). A gyakorlati jegy további feltétele, hogy félév végén a tesztek összeredménye legalább 0 legyen.

A gyakorlati számonkérés 2 db központi évfolyam-zh (6-6 feladat, 2x60 pont) formájában történik, ezek az előadások időpontjában lesznek (80-90 perc), a feladatok a központi feladatsorok alapján lesznek válogatva (1. zh.: okt. 14./16., 2. zh.: dec. 9./11.). A ponthatárok: (zh-nként) 20-tól 2-es, 30-tól 3-as, 40-től 4-es, 50-től 5-ös. Az év végi jegy a két zh. összpontszámja alapján kerül meghatározásar: 40-től 2-es, 60-tól 3-as, 80-tól 4-es, 100-tól 5-ös. Akinek mindkét zh-ja 1-es, a gyakorlati jegye automatikusan 1-es, akinek csak az egyik, az a vizsgaidőszak első hetében újraírhatja azt. Akinek nem sikerül javított az 1-es zh.-t azok szintén 1-es gyakorlati jegyet kapnak.

Minden gyakorlatvezető adhat maximum plusz 10 pontot a féléves munkára (szorgalmi feladatok megoldására).

A gyakorlathoz utóvizsga nincs.

Számonkérés

Előadáson való részvétel kötelező, legfeljebb 3 hiányzás megengedett.

A vizsga írásbeli, 3 részből áll:

  1. alapfogalmak/alaptételek: 5x1 pont
  2. egyéb definíció, tételkimondás: 10x1 pont,
  3. bizonyítás: 3x3 pont
A sikeres vizsgához az alapkérdésekből legalább 4-re kell jól tudni a választ, továbbá legalább 3 pontot el kell érni a bizonyításokból Az első rész lehetséges kérdései publikusak lesznek. A viszga eredménye: 10 ponttól 2-es, 15 ponttól 3-as, 20 ponttól jogot szerez szóbeli vizsgára, ahol 4-est illetve 5-öst szerezhet.

A vizsga második és harmadik részéhez nem adunk ki külön tételsort, de a felkészülés segítése érdekében a 2012-es tételsor letölthető.

A szóbeli részhez tartózó tételsor.

Zárthelyi dolgozatok pótlása, javítása

A zárthelyi dolgozatokat 2013.12.18. (szerda) napon a 0-821 Bolyai teremben lehet pótolni, javítani.

Első dolgozat: 8.30-10.00
Második dolgozat: 10.15-11.45

Legfeljebb egy dolgozatot lehet pótolni, javítani, a dologzatokat a gyakorlatvezetők javítják.

Irodalom:

Járai Anral (szerk.): Bevezetés a Matematikába (Informatikai Alkalmazásokkal) c. könyv 1-6 fejezetei. A könyvbe szereplő feladatok külön is letölthetőek.


Egyes előadások tartalma

Az egyes előadások kivetitett előzetes diái még az aktuális előadás elött felkerül a honlapra. A időközben felmerült hibákat igyekszem folyamatosan javítani.

1. előadás, 2013. 09. 09: Komplex számok
Harmadfokú egyenlet megoldásának problémája. Komplex számok definíciója, algebra alaptétele. Alapműveletek komplex számok körében, abszolútérték, konjugált. Alapvető összeföggések a konjugálttal ill. abszolútértékkel. Trigonometrikus alak, Moivre-azonosságok.

2. előadás, 2013. 09. 16: Komplex számok, számelmélet
Komplex számok (folyt.): példa gyökvonásra, egységgyökök, gyökvonás és egységgyökök kapcsolata, rend, primitív gyökök.

Számelmélet: oszthatóság, oszthatóság tulajdonságai, egységek, asszociáltak, prímek, felbonthatatlanok, minden prím felbonthatatlan. Maradékos osztás, számrendszerek. Kitüntetett (legnagyobb) közös osztó, kitüntetett (legkisebb) közös többszörös. Euklideszi, bővített euklideszi algoritmus.

3. előadás, 2013. 09. 23: Számelmélet
Számelmélet (folyt.): Minden felbonthatatlan prím. Számelmélet alaptétele és következményei, osztók száma. Prímek: végtelen sok prímszám van, Erathoszthenész szitája. Kongruenciák: alapfogalmak, alaptulajdonságok. Lineáris kongruenciák megoldása. Lineáris diofantikus egyeneltek. Szimultán kongruenciák, kínai maradék tétel. Maradékosztályok, teljes ill. redukált maradékrendszerek, műveletek maradékosztályok között.

4. előadás, 2013. 09. 30: Számelmélet
Számelmélet (folyt.): Maradékosztályok, műveletek maradékosztályok között. Euler féle φ függvény: fogalma és kiszámolása. Euler-Fermat tétel. Gyors hatványozás. Generátor (primitív gyök) fogalma, diszkrét logaritmus.

Kriptográfiai alkalmazások: Ceasar kód, One Time Pad, RSA.

5. előadás, 2013. 10. 07: Számelmélet, kombinatorika
Kriptográfiai alkalmazások: RSA (folyt.), Diffie-Hellman kulcscsere protokoll

Kombinatorika: elemi leszámlálások, ismétléses/ismétlés nélküli permutáció, variáció, kombináció. Binomiális tétel, alapvető összefüggések a binomiális együtthatók között. Polinomiális tétel.

6. előadás, 2013. 10. 14: Zárthelyi irása
Beosztás névsor alapján:
7.50-9.20: A-K
9.30-11.00 L-Zs
A dolgozat írására 90 percük lesz.
A dolgozat írásához használhatnak papírt, tollat (hozandó), egysoros számológépet (hozható).
A zh-t a gyakorlatvezető javítják, ill. az eredményeket ők közlik.
A zh-n mindenki tüntesse fel: név, neptun kód, gyak. vezető neve, csoport, gyakorlat ideje.

7. előadás, 2013. 10. 21: Elmarad

8. előadás, 2013. 11. 04: Kombinatorika, logika, halmazelmélet
Kombinatorika (folyt.): skatulya-elv, szita formula.

Logika: predikátumok, logikai jelek, kvantorok, formulák. nyitott/zárt formulák.

Halmazelmélet: halmazok, részhalmazok, speciális halmazok.

9. előadás, 2013. 11. 11: Halmazelmélet, relációk
Halmazelmélet (folyt.):Halmazok uniója, metszete, tulajdonságaik. Diszjunkt halmazok. Halmazok különbsége, komplementere, szimmetrikus differenciája. Hatványhalmazok.

Relációk: rendezett párok, Descart-szorzat. Binér relációk. Relációk értelmezési tartománya, érték készlete, leszűkítése, kiterjesztése, inverze. Egy halmaz képe és inverz képe egy adott relációnál. Relációk kompozíciója.

10. előadás, 2013. 11. 18: Relációk, függvények
Relációk (folyt.): relációk kompozíció tulajdonságai. Relációk tulajdonságai. Relációk gráfja. Ekvivalenciarelációk, osztályozások és ezek kapcsolata.Részbenrendezések, rendezések, szigorú és gyenge relációk, részbenrendezések. Intervallumok.

11. előadás, 2013. 11. 25: Relációk, függvények, számfogalom
Relációk (folyt.): szigorú részbenrendezés esetében a ,,megelőzi'' kapcsolat, ill. a kezdőszeletek. Részbenredezések Hasse-diagrammja. Részbenrendezés esetében a legkisebb, legnagyobb, minimális és maximális elemek. Részhalmazok korlátai, infimum, supremum. Alsó- és felsőhatár tulajdonságú halmazok.

Függvények: függvények fogalma, argumentuma, értéke. Függvénytulajdonságok: injektív, szürjektív, bijektív függvények. Permutációk, példa az n-edik egységgyökök permutációjára. Függvények kompozíciója. Monoton függvények, ezek függvénytulajdonságai.

Műveletek, műveletek függvények között. Műveletek tulajdonságai: asszociativitás, kommutativitás. Művelettartó függvények.

Számfogalom: természetes számok, Peano-axiómák. A természetes számok, mint egységelemes félcsoport.

12. előadás, 2013. 12. 02: Függvények, számfogalom

13. előadás, 2013. 12. 09: Zárthelyi irása
Beosztás névsor alapján:
7.50-9.20: L-Zs
9.30-11.00: A-K
A dolgozat írására 90 percük lesz.
A dolgozat írásához használhatnak papírt, tollat (hozandó), egysoros számológépet (hozható).
A zh-t a gyakorlatvezető javítják, ill. az eredményeket ők közlik.
A zh-n mindenki tüntesse fel: név, neptun kód, gyak. vezető neve, csoport, gyakorlat ideje.