Datalogi
Formelle sprog
Hvad et formelt sprog, et alfabet og et ord er. Grundbegreber i teorien om formelle sprog forklaret ved sammenligning med almindeligt sprog og med eksempler.
Endelige automater
Endelig automat som beregningsmodel med tilstande og overgange. Definition, tilstandsdiagram, formalisering af beregningen og eksempler på accepterede ord.
Minimering af automater
Uopnåelige tilstande i en endelig automat, som ikke kan nås fra starttilstanden. Definition og fremgangsmåde til sikkert at fjerne dem fra automaten.
Lukkethedsegenskaber for regulære sprog
Regulære sprog er lukkede under forening, fællesmængde, konkatenering og Kleene-stjerne. Hvad lukkethed under en operation betyder, og hvorfor det gælder for regulære sprog.
Regulære udtryk
Hvad et regulært udtryk er, og hvordan det beskriver en mængde af ord. Definition, sammenligning med aritmetiske udtryk og forbindelsen til endelige automater.
Estimering af antal forskellige værdier
Linear counting: sådan estimerer du antallet af unikke værdier i store datamængder. Hashfunktioner, bitmaps og hvorfor den naive fremgangsmåde ikke slår til.
Bloom-filter: findes elementet i mængden?
Et Bloom-filter er en probabilistisk datastruktur, der hurtigt svarer på, om et element er i en mængde. Princip, hashfunktioner og praktisk anvendelse.
Cæsarchiffer
Sådan fungerer Cæsarchifferet, en af de ældste måder at kryptere tekst på. Princippet med forskydning af bogstaver, generalisering af chifferet og et online krypteringsværktøj.
Vigenère-chiffer
Vigenère-chifferet bruger flere alfabeter og modstår derfor frekvensanalyse. Princippet i krypteringen, Vigenère-kvadratet, valg af nøgle og et værktøj.
