Föreläsningar

Föreläsning 12

Var går gränsen?

OH-bilder från denna föreläsning

Hur hittar man kortaste vägen genom en graf?
Hur kopplar man ihop hörnen på billigaste sätt?
Var går gränsen mellan användbara och oanvändbara algoritmer?
Vad är NP-klassen av problem?
Problem som är svåra att lösa men det är lätt att kolla lösningen.
Ved menas med NP-kompletta problem?
En stor grupp problem som bevisligen är "lika svåra".
Hitta hamiltoncykel.
Lägga elaka pussel.
Färglägga en graf med tre färger.
Schemaläggning.
Finns det problem som bevisligen är svåra?
Avgöra om en schack-strategi är ofelbar.
Finns det problem som är omöjliga?
Kakelproblemet: kan man bygga sammanhängande mönster av alla storlekar givet ett ändligt antal kakelplattstyper.
Hur fungerar kryptering?
Klassisk kryptering med en hemlig gemensam nyckel.
Öppen-nyckel tekniker med separata krypertings och dekrypteringsnycklar.