Diskret Matematik Glosor

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 mängd A bestå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.

Click

Type

Listen

Games

Print