discrete mathematics (tsz. discrete mathematicses)

1. (informatika) diszkrét matematika

A diszkrét matematika a matematika azon ága, amely megszámlálható, különálló (diszkrét) struktúrákat vizsgál. Ellentétben az analízissel (amely folytonos mennyiségekkel foglalkozik), a diszkrét matematika nem-folytonos, „lépcsőzetes” dolgokat vizsgál, például: egész számok, logikai állítások, gráfok, kombinációk.

• Számítástechnika alapja (algoritmusok, adattípusok, logika)
• Titkosítás, hálózatok, adatstruktúrák modellezése
• Kódoláselmélet, mesterséges intelligencia, programozás alapja
• Bizonyítási technikák tanulása

• Állításlogika: igaz-hamis értékek vizsgálata
• Logikai operátorok: ∧ (ÉS), ∨ (VAGY), ¬ (tagadás), → (implikáció)
• Logikai következtetések, táblázatok, formális bizonyítások
• Példa: Ha esik az eső, akkor nedves lesz az út → ${\textstyle P\rightarrow Q}$

• Egész számok tulajdonságai: oszthatóság, prímszámok, maradékos osztás
• Moduláris aritmetika: pl. 17 ≡ 2 (mod 5)
• Alkalmazás: kriptográfia, kódolás, RSA algoritmus

• Lehetséges elrendezések, kiválasztások száma
• Permutációk, variációk, kombinációk
• Példa: Hányféleképp választhatunk 3 embert 5-ből?

• Pontok (csúcsok) és vonalak (élek) struktúrája
• Útvonalak, körök, kapcsolatok, hálózatok
• Példa: útvonaltervezés, közösségi hálózat elemzés

• Halmazok: elemek gyűjteményei, halmazműveletek
• Metszet, unió, különbség, komplementer
• Véges és végtelen halmazok
• Példa: ${\textstyle A\cup B}$, ${\textstyle A\cap B}$, ${\textstyle A\setminus B}$

• Relációk: milyen kapcsolat van két halmaz elemei között
• Függvény: minden bemenethez egy kimenet tartozik
• Reflexív, szimmetrikus, tranzitív relációk
• Példa: „barátja valakinek” reláció egy osztályban

• Egy probléma saját magára való visszavezetése

• Rekurzív formulák, pl. Fibonacci-sorozat:

  $${\displaystyle F(n)=F(n-1)+F(n-2)}$$

• Bináris mátrixok: gráfok szomszédsági mátrixa
• Bool-algebra: logikai értékekkel végzett műveletek (0,1)

• Diszkrét valószínűségi változók (pl. dobókocka)
• Számítás: ${\textstyle P={\frac {\text{kívánt esetek száma}}{\text{összes eset}}}}$

• Direkt bizonyítás
• Indirekt bizonyítás (ellentmondás)
• Matematikai indukció
• Fontos az algoritmusok és állítások helyességének igazolásához

1. Mennyi az összes 3 jegyű szám, amiben nincs ismétlődő számjegy?
2. Írjuk fel a logikai kifejezést: “Ha esik, akkor beviszem a ruhákat.”
3. Hányféleképp lehet 4 embert leültetni egy sorba?

• Programozói, informatikai, mérnöki szakokon kötelező
• Matematika fakultáción középiskolában is érintik
• Versenyek (pl. OKTV) diszkrét matek feladatokat is tartalmaznak

absolute value algorithmics antisymmetric relation aristotle arithmetic progression automata theory average bijection bijective proof binary function binary numeral system binary relation canonical form cartesian product characterization (mathematics) claude shannon coding theory codomain combination combination combinatorial proof combinatorics combinatorics combinatorics complement (set theory) computability computational complexity theory computational geometry conditional probability congruence (geometry) contradiction, reductio ad absurdum contrapositive counterexample cryptography decimal de morgan's laws difference operator digital geometry digital geometry digital topology discrete geometry discrete optimization discrete random variable disjoint sets disjoint union distinct (mathematics) division by zero divisor domain of a function donald knuth double counting (proof technique) elementary algebra element (mathematics) empty product empty product empty set equality (mathematics) equation equivalence class equivalence relation euclidean algorithm event (probability theory) expected value extensionality factorial faulhaber's formula fermat's little theorem finite difference finite mathematics floor function function composition function (mathematics) function (mathematics) fundamental theorem of arithmetic game theory graphing equivalence graph theory graph theory a study of graph (discrete mathematics) group isomorphism group (mathematics) heterogeneous relation identity element identity function identity (mathematics) if and only if image (mathematics) inclusion map independence (probability theory) indeterminate form inequality (mathematics) inequation information theory information theory injective function intersection (set theory) left-hand side and right-hand side of an equation leonhard euler linear algebra linear equation list of topics in logic logic logical operator markov chain mathematical induction mathematical logic mathematical proof modal logic modular arithmetic modular arithmetic multiset multivalued function naive set theory necessary and sufficient normal form (mathematics) number theory number theory open sentence ordered pair partial function partially ordered set pascal's triangle paul erdős permutation permutations pigeonhole principle pons asinorum power set probability probability probability theory quadratic equation random variables range of a function recurrence relation reflexive property of equality reflexive relation relation composition relation (mathematics) sample space set (mathematics) set theory set theory sign function similarity (geometry) simple theorems in the algebra of sets solution point subgroups subset substitution property of equality subtraction successor function sufficiently large surjection symmetric difference symmetric property of equality symmetric relation symmetry table of mathematical symbols transitive closure transitive property of equality transitive relation truth table union (set theory) uniqueness quantification up to vacuous truth venn diagram without loss of generality

• discrete mathematics - Szótár.net (en-hu)
• discrete mathematics - Sztaki (en-hu)
• discrete mathematics - Merriam–Webster
• discrete mathematics - Cambridge
• discrete mathematics - WordNet
• discrete mathematics - Яндекс (en-ru)
• discrete mathematics - Google (en-hu)
• discrete mathematics - Wikidata
• discrete mathematics - Wikipédia (angol)