Informatikk

Formelle språk

Hva et formelt språk, et alfabet og et ord er. Grunnbegrepene i teorien om formelle språk forklart ved å sammenligne med det vanlige språket vårt og med eksempler.

Endelige automater

Endelig automat som beregningsmodell med tilstander og overganger. Definisjon, tilstandsdiagram, formalisering av beregningen og eksempler på aksepterte ord.

Minimering av automater

Uoppnåelige tilstander i en endelig automat, som ikke kan nås fra starttilstanden. Definisjon og framgangsmåte for å fjerne dem trygt fra automaten.

Lukkethetsegenskaper for regulære språk

Regulære språk er lukket under union, snitt, konkatenering og Kleene-stjerne. Hva det vil si at en mengde er lukket under en operasjon, og hvorfor det gjelder for regulære språk.

Regulære uttrykk

Hva et regulært uttrykk er, og hvordan det beskriver en mengde ord. Definisjon, sammenligning med aritmetiske uttrykk og sammenhengen med endelige automater.

Estimering av antall ulike verdier

Linear counting: hvordan du anslår antall unike verdier i store datamengder. Hashfunksjoner, bitmap og hvorfor den naive framgangsmåten ikke er nok.

Bloom-filter: finnes elementet i mengden?

Et Bloom-filter er en probabilistisk datastruktur som raskt svarer på om et element er i en mengde. Prinsippet, hashfunksjoner og praktisk bruk.

Cæsar-chiffer

Slik fungerer Cæsar-chifferet, en av de eldste måtene å kryptere tekst på. Prinsippet med forskyvning av bokstaver, generalisering av chifferet og et nettbasert krypteringsverktøy.

Vigenère-chiffer

Vigenère-chifferet bruker flere alfabeter og står derfor imot frekvensanalyse. Prinsippet for kryptering, Vigenère-kvadratet, valg av nøkkel og et verktøy.