Ordlista för Diskret matematik
45 begrepp ur SF1662, förklarade i kursens sammanhang och inte i allmänhet. Varje term länkar vidare till avsnittet där den används.
Mängder, funktioner och relationer
- Injektionäven: injektiv, injektiv funktion
- En funktion där olika argument alltid ger olika funktionsvärden.
- Läs om Mängder, funktioner och relationer
- Surjektionäven: surjektiv, surjektiv funktion
- En funktion som når varje element i sin angivna målmängd.
- Läs om Mängder, funktioner och relationer
- Bijektionäven: bijektiv, bijektiv funktion
- En funktion som är både injektiv och surjektiv och därför parar ihop mängdernas element ett till ett.
- Läs om Mängder, funktioner och relationer
- Kardinalitetäven: mäktighet
- En mängds storlek. För ändliga mängder är den antalet element; allmänt jämförs storlek med bijektioner.
- Läs om Mängder, funktioner och relationer
- Ekvivalensrelation
- En relation som är reflexiv, symmetrisk och transitiv och därmed delar mängden i ekvivalensklasser.
- Läs om Mängder, funktioner och relationer
- Partition
- En uppdelning av en mängd i icke-tomma, parvis disjunkta delmängder vars union är hela mängden.
- Läs om Mängder, funktioner och relationer
- Partialordningäven: ordningsrelation, partiell ordning
- En relation som är reflexiv, antisymmetrisk och transitiv. Två olika element behöver inte vara jämförbara.
- Läs om Mängder, funktioner och relationer
- Antisymmetriäven: antisymmetrisk
- En relation är antisymmetrisk om två element som relateras i båda riktningarna måste vara samma element. Detta förbjuder inte relation från ett element till sig självt.
- Läs om Mängder, funktioner och relationer
- Total ordningäven: linjär ordning, totalordning
- En partialordning där varje par av element kan jämföras i minst en riktning.
- Läs om Mängder, funktioner och relationer
Induktion, rekursion och bevis
- Induktionsantagandeäven: induktionshypotes
- Antagandet att påståendet gäller för ett fixerat index; det används för att bevisa nästa fall utan att anta detta nästa fall.
- Läs om Induktion, rekursion och bevis
- Rekursionäven: rekursionsformel
- En definition där senare värden anges med hjälp av tidigare värden och ett tillräckligt antal startvärden.
- Läs om Induktion, rekursion och bevis
- Motsägelsebevisäven: indirekt bevis
- Ett bevis där negationen av slutsatsen antas och leder till en motsägelse med antagandena eller ett redan känt påstående.
- Läs om Induktion, rekursion och bevis
Heltal och diofantiska ekvationer
- Delbarhetäven: delare
- Ett heltal delar ett annat om det senare är det förra multiplicerat med ett heltal.
- Läs om Heltal och diofantiska ekvationer
- Största gemensamma delareäven: gcd, sgd
- Det största positiva heltal som delar båda de givna heltalen, när de inte båda är noll.
- Läs om Heltal och diofantiska ekvationer
- Relativt primaäven: coprime, relativt prim
- Två heltal är relativt prima om deras största gemensamma delare är ett.
- Läs om Heltal och diofantiska ekvationer
- Diofantisk ekvationäven: diofantiska ekvationer
- En ekvation där lösningarna söks bland heltalen.
- Läs om Heltal och diofantiska ekvationer
Kongruenser och RSA
- Kongruensäven: kongruent, modulo
- Två heltal är kongruenta modulo ett positivt heltal om deras differens är delbar med modulen.
- Läs om Kongruenser och RSA
- Principalrestäven: minsta icke-negativa rest
- Den entydiga resten som är minst noll och mindre än den positiva modulen.
- Läs om Kongruenser och RSA
- Modulär invers
- En restklass som multiplicerad med den givna restklassen ger ett; den finns precis när talet och modulen är relativt prima.
- Läs om Kongruenser och RSA
Kombinatorik och sannolikhet
- Binomialkoefficientäven: kombinationer
- Antalet sätt att välja ett bestämt antal objekt ur olika objekt utan att ordningen spelar roll.
- Läs om Kombinatorik och sannolikhet
- Fakultet
- Produkten av de positiva heltalen upp till ett givet icke-negativt heltal. Noll fakultet definieras som ett.
- Läs om Kombinatorik och sannolikhet
- Multimängd
- En samling där ett element får förekomma flera gånger och antalet förekomster ingår i beskrivningen.
- Läs om Kombinatorik och sannolikhet
- Komplementhändelseäven: komplement
- Händelsen som består av alla utfall där den ursprungliga händelsen inte inträffar.
- Läs om Kombinatorik och sannolikhet
- Stirlingtal av andra slagetäven: S(n,k), Stirlingnummer, Stirlingtal
- Antalet partitioner av ett bestämt antal olika objekt i ett bestämt antal icke-tomma, omärkta grupper.
- Läs om Kombinatorik och sannolikhet
- Multinomialkoefficientäven: multinomial, multinomialsats
- Antalet sätt att fördela olika objekt i märkta grupper med givna storlekar; samma uttryck räknar ordningar av identiska objekttyper med givna multipliciter.
- Läs om Kombinatorik och sannolikhet
Permutationer och grupper
- Cykel i en permutationäven: cykelform
- En sluten följd av olika element där permutationen skickar varje element till nästa och det sista till det första.
- Läs om Permutationer och grupper
- Elementordningäven: ordning
- Det minsta positiva antalet gånger ett gruppelement måste kombineras med sig självt för att ge identitetselementet. Finns inget sådant antal är ordningen oändlig.
- Läs om Permutationer och grupper
- Undergrupp
- En delmängd av en grupp som själv är en grupp med samma operation. Den innehåller identiteten och är sluten under operation och inverser.
- Läs om Permutationer och grupper
- Sidoklassäven: högersidoklass, vänstersidoklass
- Mängden som fås genom att multiplicera alla element i en undergrupp med samma gruppelement från samma sida. I additiv notation används addition.
- Läs om Permutationer och grupper
- Normal undergrupp
- En undergrupp vars vänster- och högersidoklasser sammanfaller för varje gruppelement; detta gör kvotgruppens operation väldefinierad.
- Läs om Permutationer och grupper
- Cyklisk gruppäven: generator
- En grupp där varje element kan skrivas som en heltalspotens av ett enda element, eller som en heltalsmultipel i additiv notation.
- Läs om Permutationer och grupper
Grafer, färgning och matchning
- Bipartit grafäven: tvådelad graf
- En graf vars noder kan delas i två mängder så att varje kant går mellan mängderna.
- Läs om Grafer, färgning och matchning
- Eulerkretsäven: Eulersk krets
- En sluten vandring som använder varje kant exakt en gång. Noder får besökas flera gånger.
- Läs om Grafer, färgning och matchning
- Hamiltoncykeläven: Hamiltonsk cykel
- En cykel som besöker varje nod exakt en gång innan den återkommer till startnoden.
- Läs om Grafer, färgning och matchning
- Kromatiskt taläven: nodfärgning
- Det minsta antalet färger som krävs för att färga noder så att grannar får olika färger.
- Läs om Grafer, färgning och matchning
- Planär grafäven: planaritet
- En graf som kan ritas i planet utan att kanter korsar varandra utanför sina gemensamma ändpunkter.
- Läs om Grafer, färgning och matchning
- Matchning
- En samling kanter där inga två kanter delar en ändpunkt. En matchning täcker en nod om någon av kanterna möter noden.
- Läs om Grafer, färgning och matchning
- Kromatiskt polynomäven: chromatic polynomial, färgpolynom
- Ett polynom vars värde vid en icke-negativ heltalig palettstorlek räknar grafens godkända hörnfärgningar ur denna palett. Alla färger behöver inte användas.
- Läs om Grafer, färgning och matchning
- Kantkontraktionäven: kontrahera, kontraktion
- Att identifiera en kants ändpunkter till ett hörn och ta bort kanten. Vid räkning av färgningar kan parallella kanter i den resulterande grafen slås ihop.
- Läs om Grafer, färgning och matchning
- Kantdeletionäven: deletion, kantborttagning
- Att ta bort en kant men behålla dess ändpunkter och alla övriga hörn och kanter.
- Läs om Grafer, färgning och matchning
Polynom och gaussiska heltal
- Gaussiskt heltaläven: gaussiska heltal
- Ett komplext tal vars realdel och imaginärdel båda är heltal.
- Läs om Polynom och gaussiska heltal
- Enhetäven: inverterbart element
- Ett element i en ring som har en multiplikativ invers i samma ring.
- Läs om Polynom och gaussiska heltal
- Irreducibeläven: irreducibelt polynom
- Ett icke-nollelement som inte är en enhet och som inte kan skrivas som en produkt av två icke-enheter i den aktuella ringen.
- Läs om Polynom och gaussiska heltal
- Associerade element
- Två element som skiljer sig genom multiplikation med en enhet. De betraktas som samma väsentliga faktor vid faktorisering.
- Läs om Polynom och gaussiska heltal