19 February - 25 February

21/2

• Υπενθύμιση βασικών εννοιών πολυπλοκότητας (κλάσεις, αναγωγές, NP-πληρότητα). 
  
• Εισαγωγή-διαδικαστικά. 
  
• Προσεγγιστικοί αλγόριθμοι: εισαγωγικές έννοιες, λόγος προσέγγισης, το πρόβλημα Vertex Cover (slides: 1-15).
  Προτεινόμενη μελέτη: Vazirani κεφ. 1 (κυρίως 1.1), και 2.2. Επίσης: DPV 9.2.1.