Datavetenskap
Formella språk
Vad ett formellt språk, ett alfabet och ett ord är. Grundbegrepp i teorin om formella språk, förklarade genom jämförelse med vanligt språk och med exempel.
Ändliga automater
Den ändliga automaten som beräkningsmodell med tillstånd och övergångar. Definition, tillståndsdiagram, formalisering av beräkningen och exempel på accepterade ord.
Minimering av automater
Onåbara tillstånd i en ändlig automat, som inte går att nå från starttillståndet. Definition och hur du säkert tar bort dem ur automaten.
Slutenhetsegenskaper för reguljära språk
Reguljära språk är slutna under union, snitt, konkatenering och Kleenestjärna. Vad slutenhet under en operation betyder och varför det gäller för reguljära språk.
Reguljära uttryck
Vad ett reguljärt uttryck är och hur det beskriver en mängd ord. Definition, jämförelse med aritmetiska uttryck och samband med ändliga automater.
Uppskatta antalet olika värden
Linear counting: hur du uppskattar antalet unika värden i stora datamängder. Hashfunktioner, bitkartor och varför det naiva sättet inte räcker.
Bloomfilter: finns elementet i mängden?
Bloomfilter är en probabilistisk datastruktur som snabbt svarar på om ett element finns i en mängd. Principen, hashfunktioner och praktisk användning.
Caesarchiffer
Så fungerar Caesarchiffret, ett av de äldsta sätten att kryptera text. Principen med förskjutna bokstäver, en generalisering av chiffret och ett kryptoverktyg online.
Vigenèrechiffer
Vigenèrechiffret använder flera alfabet och står därför emot frekvensanalys. Principen för kryptering, Vigenèrekvadraten, valet av nyckel och ett verktyg.
