Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 09.02.2016, Vorlesung und Übung - 25

58:08
 
Teilen
 

Manage episode 188073177 series 1569371
Von Karlsruher Institut für Technologie (KIT) entdeckt von Player FM und unserer Community - Das Urheberrecht hat der Herausgeber, nicht Player FM, und die Audiodaten werden direkt von ihren Servern gestreamt. Tippe auf Abonnieren um Updates in Player FM zu verfolgen oder füge die URL in andere Podcast Apps ein.
25: Vorlesung und Übung | 0:00:00 Starten 0:02:07 Caesar-Chiffre 0:05:07 Monoalphabetische Verschiebungschiffre 0:06:57 Vigenère-Verschlüsselung 0:20:34 Set Cover 0:27:01 Set Cover Beispiel 1 0:27:37 Set Cover ist NP-vollständig 0:27:53 Beweis ""Set Cover ist NP-hart"" 0:35:36 Set Cover Beispiel 2 0:37:40 Beweis F erfüllbar 0:41:18 Bewies ""3SAT ist NP-hart"" 0:42:14 Negation in die Blätter drücken 0:43:25 Nichtblattknoten -> Neue Variablen 0:47:21 Clique 0:47:43 Clique Beispiel 0:50:22 Subset Sum 0:50:50 Die Subset Sum Instanz 0:52:51 Integer Linear Programming (ILP) 0:53:30 Directed Hamilton Cycle (DHC) 0:56:23 Umgang mit NP-harten Problemen

27 Episoden