DISZKRÉT / CODE ROUTE
9 HETES ÚTVONAL

GKNB_MSTM064 · Diszkrét matematika

SZE + HackerRank + Codewars
gyakorlási útvonal

Számelmélettől a gráfelméletig: kézi levezetés, majd programozási gyakorlat több nyelven.

9
hét
130
megadott feladat
1
kiegészítendő hét

SZE + HackerRank + Codewars

Diszkrét matematika útvonal

Aktív terv

2026. november 5. · nem hivatalos

Diszkrét matematika – gyakorló mini-ZH #1

Az 1., 3., 4., 5., 7. és 8. gyakorlat feladattípusai alapján. Javasolt idő: 90 perc · 10 feladat × 10 pont. Kézzel oldd meg és indokold.

  1. Számelmélet: maradékok, lnko

    1. Határozd meg −137 maradékát 12-vel osztva.
    2. Határozd meg 85 maradékát −9-cel osztva (0 ≤ r < 9).
    3. Euklideszi algoritmussal keresd meg az lnko(252, 198)-at, majd írd fel 252a + 198b alakban.
  2. Lineáris diofantoszi egyenletek

    1. Van-e egész megoldása a 90x + 126y = 200 egyenletnek? Indokold.
    2. Adj egy egész megoldást a 90x + 126y = 360 egyenletre, majd az összes megoldást.
    3. Adj olyan megoldást is, amelyben y > 0.
  3. Kongruencia és moduláris hatványozás

    1. Adj x > 500 egész számot, amelyre 58x ≡ 94 (mod 360).
    2. Ismételt négyzetre emeléssel számítsd ki 645 maradékát 91-gyel osztva.
  4. RSA

    Legyen p = 17, q = 31, e = 7.

    1. Határozd meg a titkos kitevőt, d-t.
    2. Add meg a nyilvános és titkos kulcsot.
    3. Titkosítsd az 5 üzenetet.
    4. Egy másik RSA-kódban a nyilvános kulcs (221; 7), a titkosított üzenet 20. Mi volt az eredeti üzenet?
  5. Kombinatorika: számjegyek, PIN-kódok

    1. A 0, 0, 1, 1, 1, 4, 4 számjegyekből hány valódi hétjegyű szám készíthető?
    2. Ezek közül hány osztható 5-tel?
    3. Egy hatjegyű PIN-kód hány esetben tartalmaz legalább egy 7-est, illetve pontosan három 7-est?
  6. Kombinatorika: szétosztás, lottó, rácsutak

    1. 12 egyforma almát hányféleképpen oszthatsz szét 5 gyerek közt? Hányféleképpen, ha mindenki kap legalább egyet?
    2. Ötöslottón, egy szelvénnyel hány esetben lesz pontosan két találatod?
    3. Hány út vezet (0,0)-ból (10,6)-ba, ha felfelé 1-et, jobbra 2-t lépsz? Hány nem megy át (4,3)-on?
  7. Logika: ekvivalencia, DNF

    1. Ekvivalens-e p → (q ∨ r) és (p ∧ ¬q) → r?
    2. Ekvivalens-e (p ↔ q) → r és (p ∧ q) → r?
    3. Add meg a (p → q) ∧ ¬(q ∧ r) formula egy ekvivalens DNF-jét.
  8. Logika: osztályozás, következtetés

    1. Osztályozd: (p ∧ (p → q)) → q; (p → q) ∧ p ∧ ¬q; (p ∨ q) → (p ∧ q).
    2. Helyes-e: p → q, q → r, r ⊨ p? Ha nem, adj ellenpéldát.
    3. Következik-e p → q, q → r, ¬r premisszákból ¬p?
  9. Gráfelmélet: fokszámok

    1. Gráfos-e a (4, 4, 3, 3, 2, 2, 1, 1) fokszámsorozat? Ha igen, adj meg egy gráfot.
    2. Gráfos-e a (5, 5, 4, 3, 2, 1) fokszámsorozat?
    3. 12 csúcsú, 17 élű gráf fokszámai: hat darab 3-as, öt darab 2-es és x. Mennyi x?
    4. 15 fős társaságban lehet-e, hogy mindenki pontosan 5 másik embert ismer?
  10. Gráfelmélet: mátrixok, címkézett gráfok

    Egy 12 csúcsú egyszerű gráfban 4 csúcs foka 6, 8 csúcsé pedig 3.

    1. Hány éle van?
    2. Hány nulla van a szomszédsági mátrixban?
    3. Hány nulla van az illeszkedési mátrixban?
    4. Hány egyszerű gráf adható meg az 1, 2, …, 7 pontokon, és ezek közül hányban van pontosan 5 él?
Megoldókulcs – csak megoldás után nyisd ki
  1. −137 = 12·(−12) + 7, tehát 7. 85 = (−9)·(−9) + 4, tehát 4. 252 = 198 + 54, 198 = 3·54 + 36, 54 = 36 + 18, ezért lnko = 18 = 4·252 − 5·198.
  2. lnko(90, 126) = 18, és 18 nem osztja a 200-at, tehát nincs megoldás. A 90x + 126y = 360 egy megoldása (4, 0); az összes: x = 4 + 7t, y = −5t. Például t = −1 esetén (−3, 5).
  3. x ≡ 163 (mod 180), így például x = 523. 645 ≡ 29·29·22·6 ≡ 83 (mod 91).
  4. n = 527, φ(n) = 480, d = 343. Nyilvános kulcs: (527; 7); titkos kulcs: (527; 343). 57 ≡ 129 (mod 527). A második részben d = 55, ezért az eredeti üzenet 45.
  5. 7! / (2!·3!·2!) − 6! / (3!·2!) = 150. Öttel osztható: 6! / (3!·2!) − 5! / (3!·2!) = 50. Legalább egy 7-es: 106 − 96 = 468 559; pontosan három: C(6, 3)·93 = 14 580.
  6. C(16, 4) = 1820, pozitív részekkel C(11, 4) = 330. Pontosan két lottótalálat: C(5, 2)·C(85, 3) = 987 700. Rácsutak: C(11, 5) = 462; a (4,3)-on átmenők C(5, 2)·C(6, 3) = 200, tehát 262 kerüli el.
  7. Az első két formula ekvivalens: mindkettő ¬p ∨ q ∨ r. A második pár nem ekvivalens, például p = q = r = hamis esetén. Egy egyszerű DNF: (¬p ∧ ¬q) ∨ (q ∧ ¬r).
  8. Sorrendben: tautológia, kontradikció, kielégíthető. A következtetés nem helyes, például p = hamis, q = hamis, r = igaz. A harmadik következtetés helyes: kontrapozícióval ¬r ⇒ ¬q ⇒ ¬p.
  9. Az első sorozat gráfos; például az élek: v₁v₂, v₁v₃, v₁v₄, v₁v₅, v₂v₃, v₂v₄, v₂v₆, v₃v₄, v₅v₆, v₇v₈. A második nem gráfos: két ötödfokú csúcs mellett minden más csúcs foka legalább 2. 2·17 = 6·3 + 5·2 + x, tehát x = 6. A 15·5 páratlan, ezért a társaság nem létezhet.
  10. 2|E| = 4·6 + 8·3 = 48, tehát 24 él. A szomszédsági mátrixban 122 − 2·24 = 96, az illeszkedésiben 12·24 − 2·24 = 240 nulla van. 7 csúcson 221 = 2 097 152 gráf van; pontosan öt éllel C(21, 5) = 20 349.

← Vissza a tantárgyhoz