TDDC75 Diskreta strukturer
Temamål
Diskret matematik: Du skall veta vad en mängd är och
behärska mängdnotationen. Du skall kunna de olika likhetsbegreppen
för mängder (likhet, delmängd, äkta delmängd,
disjunkta mängder) och de vanligaste mängdoperationerna, som
union, snitt, differens, komplement, potensmängd.
Du skall kunna visa mängdteoretiska lagar, samt ha kännedom
om Venndiagram. Du skall kunna göra enkla induktiva definitioner
av mängder. Du skall känna
till vad som menas med en mängds kardinalitet.
Du skall veta vad ett par
och en tupel är, och kunna ta Kartesiska produkten av mängder.
Du skall veta vad en relation är och behärska olika notationen
för relationer. Du skall kunna utföra operationer som invers
och sammansättning på relationer, och veta vad identitetsrelationen
är. Du skall veta vad grundläggande egenskaper som reflexivitet,
transitivitet, symmetri och anti-symmetri är och kunna
visa att relationer har/inte har dessa egenskaper. Du skall kunna ta reflexiva/transtiva/symmetriska
höljet av en relation. Du skall kunna känna igen en partialordning,
totalordning och en ekvivalensrelation, samt känna till vad
som menas med minimala/maximala element, minsta/största element,
ekvivalensklass och partition. Du skall ha kännedom om Hassediagram
samt riktade grafer.
Du skall veta vad en funktion,
domän och värdemängd är, samt behärska
notationen för funktioner. Du skall kunna definiera en funktion
induktivt. Du skall veta vad som menas med injektiv, surjektiv
och bijektiv och inversen av en funktion. Du skall även veta
vad som menas med kommutativ, associativ och distributiv,
och kunna sätta samman två funktioner. Du skall ha kännedom
om partiella funktioner.
Du skall veta vad en boolesk algebra
är; speciellt den binära booleska algebran. Du skall kunna
utföra enkla beräkningar med hjälp av algebrans lagar
och ska kunna ta fram konjunktiv och disjunktiv normalform för
en boolesk funktion.
Du skall veta vad en sträng och ett
språk är, samt kunna utföra enkla operationer som konkatenering
av strängar. Du förväntas känna till vad ett talsystem
är; speciellt decimala, binära och hexadecimala
talsystemen för heltal. Du skall kunna översätta mellan
de olika talsystemen och kunna addera binära tal och ta tvåkomplementet
av ett naturligt tal.
Du skall kunna göra enkla bevis av egenskaper för ovanstående begrepp inklusive utföra enkla induktiva bevis.
Digitalteknik: Digitalteknik är hur vi kan bygga nät med önskad funktionalitet
med grindar och vippor. Grindarna implementerar logiska funktioner. I digitalteknik
arbetar vi endast med digitala signaler ("ettor och nollor"). Verkligheten är
dock ofta analog. Därför behöver vi omvandling från analoga signaler till digitala
signaler och tvärt om (A/D och D/A omvandlare). Figuren nedanför visar hur ett
digitalt system kan se ut.
Digitala system finns överallt i vår vardag, t.ex. i datorer, bilar, telefoner,
kylskåp, fjärrkontroller och tv. I kombinatoriska nät beror utsignalerna endast
av insignalernas ögonblicksvärden. I sekvensnät beror utsignalerna inte endast
på insignalernas ögonblicksvärden utan även på insignalernas tidigare värden.
För att sekvensnätet ska komma ihåg insignalernas tidigare värden måste vippor
användas. För realisera kombinatoriska nät och sekvensnät kan följande algoritmer
användas:
För att realisera ett kombinatoriskt
nät gör man på följande sätt:
- Ta fram ett logiskt uttryck från en verbal beskrivning.
- Förenkla det logiska uttrycket med hjälp av en grafisk förenklingsmetod.
- Rita det förenklade uttrycket med önskade grindar.
- Rita upp en tillståndsgraf över systemets beteende.
- Använd en metod för att från tillståndsgrafen ta fram ett logiskt uttryck.
- Använd en grafisk förenklingsmetod för att förenkla det logiska uttrycket.
- Rita upp det förenklade uttrycket med vippor och önskade grindar .
- Du ska kunna använda dig av metoderna för syntes av sekvensnät: tillståndsgraf (Mealy/Moore), tillståndstabell, kodning av tillstånd, flödestabell, tillståndsminimering.
- Du ska kunna minimera booleska uttryck av upp till fem variabler med hjälp av Karnauhgdiagram. Du ska även kunna hantera karnaughdiagram med ofullständigt specificierade funktioner.
- Du ska kunna minimera randcellarna i ett iterativt kombinatoriskt nät.
Du ska även kunna realisera kombinatorska nät med hjälp av grindtyperna OR,
AND, NOT, EXOR, NAND och NOR, samt använda dig av olika speciella kombinatoriska
nät,såsom adderare, komparator, avkodare, demultiplexer och multiplexer. Du
ska kunna använda dig av klockade vippor av typerna D, JK, SR och T. Du ska
även kunna realisera sekvensnät med användning av speciella sekvesnät, som t.ex.
räknare och skiftregister. Du ska kunna analysera och verifiera kombinatoriska
nät, sekvensnät samt iterativa kombinatoriska nät. Du ska känna till och kunna
använda olika talkodningar samt även felupptäckande/felrättande kod. Du ska
känna till vad programmerbar logik är och kunna skilja på vad PLA och PAL är.
Du ska känna till grindutgångstyperna tristate, öppen kollektor samt totempole.
Du ska kunna använda dig av NAND och inverterare med öppen kollektorutgång (trådade
grindar). Du ska kunna konstruera en avstudsare samt en enpulsare med hjälp
av grindar och vippor.
Sidansvarig: Mikael Asplund
Senast uppdaterad: 2023-06-29