Diskret Matematik Glosor

Alla Inga Spara

• Mängd är en samling av distinkta objekt (element.) Exempel: {hund, katt, häst}
• Element ett av objekten i en mängd. Exempel: A är ett ... i mängden {A, B, C}.
• Delmängd A är en ... I B om allt i A finns i B. Det skrivs A ⊆ B.
• Union ... av mängderna A och B innehåller alla element som finns i A eller B (eller båda).
• Snitt ... av två mängder A och B innehåller alla element som finns i både A och B.
• Komplement ... till en mängd A består av de element som inte finns i A men som finns i det givna universumet. Det skrivs Aᶜ eller U \ A.
• Produktmängd ... A × B består av alla ordnade par (a, b) där a tillhör A och b tillhör B.
• Standardmängder ℕ = {0, 1, 2, ...} (naturliga tal), ℤ = {..., -2, -1, 0, 1, 2, ...} (heltal), ℤ₊ = {1, 2, 3, ...} (positiva heltal)
• Bijektion är en hopparning mellan två mängder där varje element i den ena mängden paras ihop med exakt ett unikt element i den andra – och vice versa. Tänkt mängderna (A, B) och (1, 2): Pro
• Oändlighet En mängd är ... om det inte har ett slut Exempel: mängden ℕ innehåller uppräkneligt ... många element.
• Division av heltal När ett heltal delas med ett annat får man en heltalskvot och en rest. Exempel: 17 ÷ 6 = kvot 2, rest 5.
• Primtal Ett ... är ett heltal större än 1 som bara är delbart med 1 och sig självt
• Primtalsfaktorisering Att skriva ett heltal som en produkt av primtal. Exempel: 90 = 2 · 3 · 3 · 5.
• Största gemensamma delare (gcd) Det största tal som delar två (eller flera) heltal utan rest. Exempel: gcd(90, 20) = 10.
• Minsta gemensamma delare (lcm) Det minsta heltal som är en gemensam multipel till två (eller flera) heltal. Exempel: lcm(90, 20) = 180.
• Euklides algoritm En metod för att beräkna största gemensamma delare (gcd) mellan två heltal.
• Diofantiska ekvationer En ekvation där man bara godtar heltalslösningar.
• Modulär aritmetik Räkning modulo n, (och i ℤₙ). Man börjar om från 0 varje gång man når n. Exempel: 17 ≡ 5 (mod 12).
• Binära tal Tal skrivna i bas 2, där endast siffrorna 0 och 1 används. Exempel: 1101₂ = 13₁₀.
• Rekursiv definition, rekursion En definition där ett begrepp definieras i termer av sig självt (enklare version) , ofta med ett basfall och en regel för hur nya fall byggs från tidigare.
• Rekursiv talföljd En talföljd där varje tal definieras med hjälp av ett eller flera föregående tal. Exempel: Fibonaccitalen definieras som fₙ = fₙ₋₁ + fₙ₋₂ med f₁ = 0, f₂ = 1.
• Summasymbol Symbolen Σ används för att uttrycka ...
• Produktsymbol Symbolen Π används för att uttrycka ...
• Induktionsbevis En bevismetod där man visar att ett påstående gäller för ett basfall och att om det gäller för ett n, så gäller det även för n + 1. Detta visar att det gäller för alla n ≥ basfal
• Sannolikhet anger hur troligt det är att en viss händelse inträffar, och uttrycks som ett tal mellan 0 och 1
• Additionsprinciper (eller) Sannolikhetslära: Om två händelser är disjunkta (kan inte inträffa samtidigt) är sannolikheten för att någon av dem inträffar summan av deras sannolikheter.
• Additionsprincipen (eller) Kombinatorik: om det finns x antal sätt att behandla ett fall (X) och y antal sätt att behandla ett annat disjunkt fall Y finns det x+y sätt att behandla X eller Y. Ex. juice och
• Multiplikationsprincipen (och) Sannolikhetslära: Om A och B är oberoende händelser gäller P(A och B) = P(A) * P(B).
• Multiplikationsprincipen (och) Kombinatorik: Om en sammansatt händelse består av flera oberoende val multipliceras antalet alternativ för varje steg. Exempel: 3 tröjor × 4 byxor = 12 kombinationer.
• Permutation En ... är en ordnad följd av objekt. Antalet ... av n objekt är n!. Exempel: 3! = 6 sätt att ordna tre personer.
• Urval Att välja k element bland n stycken utan att ordningen spelar roll.
• Postfacksprincipen Om man har fler brev än postfack måste något postfack få fler än ett brev. Om 13 par strumpor ska läggas i 12 lådor → minst en låda får två par.
• Hörn (nod) En punkt i en graf där kanter möts. Representerar ofta ett objekt eller ett tillstånd.
• Kant (båge) En koppling mellan två noder i en graf. Kan vara riktad eller oriktad.
• Grad ... av ett hörn är antalet kanter som är incidenta (ansluter till/kopplade) till hörnet.
• Granne Två noder som är direkt förbundna med en kant
• Stig En följd av noder där varje nod är förbunden med nästa via en kant och inga noder upprepas. Tex AàBàC
• Cykel En stig som börjar och slutar i samma nod. Gäller noderna i en delgraf.
• Sammanhängande komponent En del av en graf där man kan ta sig från varje nod till alla andra noder i just den delen.
• Komplett graf Alla noder är grannar med varandra i grafen.
• Delgraf En graf som består av ett urval av noder och kanter från en större graf.
• Bipartit graf En graf vars noder kan delas in i två grupper så att alla kanter går mellan grupperna och inte inom dem.
• Riktad graf En graf där kanterna har en riktning, från en nod till en annan.
• Hamiltoncykel En cykel som passerar genom alla noder i grafen exakt en gång och återvänder till startnoden. Gäller alla noderna i grafen.
• Eulerkrets En cykel som passerar genom varje kant exakt en gång och återvänder till startpunkten.
• Isomorfi Två grafer är ... om de har samma struktur, även om de ser olika ut. De kan ritas om till varandra.
• Grannmatris En tabell som visar vilka noder som är grannar med varandra. 1 betyder att en kant finns, 0 att den inte finns.
• Incidensmatris En matris där rader motsvarar noder och kolumner motsvarar kanter. Anger vilka noder som är incidenta (anlutna) med vilka kanter.
• Träd En sammanhängande graf utan cykler. Det finns exakt en väg mellan varje par av noder.
• Bredden-först Sökning i ett träd eller graf där man först utforskar alla noder på en nivå innan man går vidare till nästa.
• Djupet-först Sökning där man följer varje väg så långt det går innan man backar och försöker nästa.
• Inordning Traversering av ett binärt sökträd: vänster, besök, höger. Visar elementen i sorterad ordning.
• Preordning Traversering av ett binärt träd: besök, vänster, höger.
• Postordning Traversering av ett binärt träd: vänster, höger, besök.
• Logiska operatorer Eller à Disjunktion. Betyder i logik alltid och/eller. En disjunktion klassas alltså som sann då fort minst en delsats är sann. Icke à Negation. Lägga till ”det är inte sant ” på
• Implikation Om påståendet A gäller så gäller även påståendet B. A --> B
• Ekvivalens påståendet P gäller om och endast om påståendet Q gäller. P <--> Q
• Sanningsvärdestabell En tabell som visar sanningsvärdet (sant eller falskt) för ett logiskt uttryck beroende på olika kombinationer av ingångsvärden.
• Satslogikens räknelagar Lagar som beskriver hur logiska uttryck kan förenklas eller omformas, t.ex. distributiva, associativa och De Morgans lagar.
• Boolesk algebra En algebraisk struktur för logiska uttryck där variabler bara kan anta värdena 0 (falskt) eller 1 (sant).
• Disjunktiv normalform Ett logiskt uttryck skrivet som en OR-summa av AND-termer, , där varje term innehåller alla variabler (positiva eller negationer. Exempel: (A∧¬B∧C)∨(¬A∧B∧¬C)
• Konjunktiv normalform Ett logiskt uttryck skrivet som en AND-produkt av OR-termer, där varje term innehåller alla variabler. Exempel: (A∨¬B∨C)∧(¬A∨B∨¬C).
• Grindnät En elektrisk krets som implementerar logiska funktioner med grindar som OCH-, ELLER- och INTE-grindar.
• Predikat Ett påstående P(x) om ett allmänt objekt x. Exempel: P(x) = 'x är en hund'.
• Kvantifikatorerna Upp och ner A för alla, bakåt vänt E för existens
• Automat En maskin som utför ett arbete på beställning. Brukaren gör något, som att stoppa pengar i ett myntfack. Maskinen gör något, som att leverera en läskburk. Ändlig automat: En änd
• Tillstånd Ett läge som en automat kan befinna sig i. ... förändras när automaten bearbetar indata.
• Övergång En regel som beskriver hur en automat går från ett tillstånd till ett annat beroende på aktuell indata.
• Mealyautomat Man ger insignal, automaten gör en övergång och ger en utsignal. (T.ex. Stoppar in peng, får ut läsk.)
• Inmatning Automaten får som indata ett ord, det vill säga en följd av symboler, och läser in en symbol i taget.
• Utmatning Vid slutet av inmatningen avgör automaten om ordet accepteras eller förkastas.
• Tillståndstabell En tabell som beskriver alla tillstånd och övergångar i en automat, samt eventuell utdata.
• KMP-automat En ändlig automat som söker efter en viss sträng i en text.
• Accepterande automat är konstruerad för att känna igen ett visst språk om alla ord i språket leder till ett accepterande tillstånd, markerat med en extra ring. Alla andra inmatningar leder till ett i
• Alfabet En uppsättning symboler.
• Sträng En följd av symboler ur alfabetet.
• Språk En mängd av godkända strängar.
• Ord En sträng i ett språk.
• Sammansättning av ord Att kombinera två ord till ett nytt. Exempel: 'KANIN' och 'ÖRON' ger 'KANINÖRON'.
• Addition (union) av {kanin} och {öron} ger {kanin, öron}.
• Sammansättning av språk/multiplikation Att kombinera alla ord från ett språk med alla ord från ett annat. Exempel: {'KANIN', 'HUND'} × {'ÖRON', 'MAT'} = {'KANINÖRON', 'KANINMAT', 'HUNDÖRON', 'HUNDMAT'}.
• Reguljärt språk Ett formellt språk som kan beskrivas av reguljära uttryck innehållande symboler ur ett alfabet samt operatorerna +, X, * (klenestjärna).
• Kleene-stjärna En operator står för upprepning godtyckligt antal gånger.
• Diskret matematik En gren av matematiken som behandlar icke-kontinuerliga fenomen, till exempel heltal, prickar, sanningsvärdena sant och falskt, lottdragning etc.
• Diskret modell En förenklad och formell representation av ett verkligt system där objekten är åtskilda och ofta beskrivs med hjälp av mängder, grafer eller tal.
• Formell representation Att uttrycka idéer eller problem med exakta matematiska symboler och strukturer istället för vardagligt språk. Ex. boolska symboler som V.

Alla Inga Spara