Ύλη Αλγόριθμοι & Πολυπλοκότητα — Σεζόν 2023-2024

[1] Δομή Ύλης

Κάθε Chapter αντιστοιχεί ακριβώς στο περιεχόμενο κάθε διάλεξης (δεν λείπει καμία!!).
Μελετάτε όπως παρουσιάστηκε στις διαλέξεις για να είστε έτοιμοι για το πολυπόθητο 5.

---

01 - ΓΡΑΦΗΜΑΤΑ

• Chapter 1

  • Εισαγωγή στα Γραφήματα

• Chapter 2

  • Συνδεσιμότητα & Δένδρα
  • Διάσχιση κατά Βάθος (ΔκΒ)
  • Διάσχιση κατά Πλάτος (ΔκΠ)
  • Σημείο Κοπής σε Μη-Κατευθυνόμενα Γραφήματα

• Chapter 3

  • ΔκΒ σε Κατευθυνόμενα Γραφήματα
  • Ισχυρά Συνδεδεμένες Γραφικές Συνιστώσες (ΙΣΓΣ)
  • Τοπολογική Ταξινόμηση

• Chapter 4

  • Άσκηση (ΔκΒ σε Μη-Κατευθυνόμενο Γράφημα)
  • Άσκηση (Μονοπάτι μεταξύ δύο κορυφών)
  • Άσκηση (Γραφικές Συνιστώσες)
  • Άσκηση (ΔκΒ σε Κατευθυνόμενο Γράφημα)
  • Άσκηση (Εύρεση συντομότερης διαδρομής)

---

02 - ΣΥΝΤΟΜΟΤΕΡΑ ΜΟΝΟΠΑΤΙΑ

• Chapter 5

  • Ιδέα, Αλγόριθμος & Παράδειγμα Dijkstra
  • Ορθότητα & Πολυπλοκότητα Dijkstra

• Chapter 6

  • Ιδέα, Αλγόριθμος & Παράδειγμα Bellman-Ford
  • Ορθότητα & Πολυπλοκότητα Bellman-Ford
  • Πρόβλημα εύρεσης μακρύτερου μονοπατιού

• Chapter 7

  • Άσκηση (Δένδρο Συντομότερων Μονοπατιών)
  • Άσκηση (Εφαρμογή Dijkstra)
  • Άσκηση (Μοντελοποίηση προβλήματος με Dijkstra)
  • Άσκηση (Πρόβλημα ταξιδιώτη)
  • Άσκηση (Πρόβλημα arbitrage, Bellman-Ford)

---

03 - ΕΛΑΧΙΣΤΟ ΣΥΝΔΕΤΙΚΟ ΔΕΝΔΡΟ

• Chapter 8
  • Ιδέα & Αλγόριθμος Prim
  • Παράδειγμα Prim
  • Ορθότητα & Πολυπλοκότητα Prim
  • Ιδέα, Αλγόριθμος, Παράδειγμα, Ορθότητα & Πολυπλοκότητα Kruskal
  • Άσκηση (Θεωρία Ελάχιστου Συνδετικού Δένδρου)

---

04 - ΔΥΝΑΜΙΚΟΣ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ

• Chapter 9

  • Εισαγωγή & Χρησιμότητα Δ.Π. (Fibonacci)
  • Πέντε στάδια μεθοδολογίας Δυναμικού Προγραμματισμού
  • Μέγιστο άθροισμα υπακολουθίας (Προθεματική & Επιθεματική)
  • Δυναμικός Προγραμματισμός & Βέλτιστη Υποδομή

• Chapter 10

  • Συντομότερο μονοπάτι σε ΚΑΓ
  • Σχέση Bellman-Ford με Δ.Π.
  • Άσκηση (Μεγαλύτερη αύξουσα υπακολουθία)
  • Στοίχιση Κειμένου

• Chapter 11

  • Άσκηση (Μικρότερος αριθμός χαρτονομισμάτων)
  • Πολλαπλασιασμός Πινάκων

• Chapter 12

  • Άσκηση (Μεγιστοποίηση κέρδους εταιρίας)
  • Μέγιστη κοινή υπακολουθία

• Chapter 13

  • Άσκηση (Knapsack integer & 0-1)
  • Άσκηση (Μικρότερος αριθμός χαρτονομισμάτων, δύο παράμετροι)

---

05 - ΑΠΛΗΣΤΟΙ ΑΛΓΟΡΙΘΜΟΙ

• Chapter 14

  • Εισαγωγή & Προγραμματισμός εργασιών
  • Χαρακτηριστικά μεθόδου απληστίας
  • Χρόνος παραμονής σε κατάστημα

• Chapter 15

  • Απροθηματικοί κώδικες
  • Άσκηση (Μικρότερος αριθμός κλειστών διαστημάτων)
  • Άσκηση (Οδικό ταξίδι με λιγότερες στάσεις)

• Chapter 16

  • Άσκηση (Προγραμματισμός εργασιών για μεγιστοποίηση κέρδους)

---

06 - ΚΛΑΣΕΙΣ ΠΡΟΒΛΗΜΑΤΩΝ

• Chapter 16

  • Εισαγωγή

• Chapter 17

  • Κλάση NP
  • Αναγωγές
  • Παρατηρήσεις πολυπλοκότητας

• Chapter 18

  • Κλάση NP-complete
  • SAT, 3SAT, 1-3SAT

• Chapter 19

  • Άσκηση (kΙΚΑΝ)
  • Άσκηση (ΔΙΠΛΗ-ΙΚΑΝ)
  • Άσκηση (ΟΧΙ-ΟΛΑ-ΙΔΙΑ-4ΙΚΑΝ/3ΙΚΑΝ)
  • Πρόβλημα INDSET

---

[2] Συμπληρωματικά PDF

• Theory_Algorithms&Complexity_Synopsis.pdf - Θεωρητικό υπόβαθρο κεφαλαίων
• Algorithms_Algorithms&Complexity_Synopsis.pdf - Αλγόριθμοι κάθε κεφαλαίου
• Exercises_Algorithms&Complexity_Synopsis.pdf - Ασκήσεις κάθε κεφαλαίου
• Lecture_Guide_Algorithms&Complexity2024.pdf - Διαφάνειες διαλέξεων + προσωπικές σημειώσεις

---

[3] Σημειώσεις σχετικά με ύλη

Λόγω καταλήψεων, ύλη σταμάτησε στην 19η διάλεξη - "Πρόβλημα INDSET".

Δεν καλύφθηκαν από slides (29/12/2023 & 16_npcexer.pdf):

• DIR-PATH-HAMILTON, 01-EQUAL, SUBSET-SUM
• Άσκηση 1-3ΙΚΑΝ, ΚΑΤ-ΜΟΝΟΠΑΤΙ-ΧΑΜΙΛΤΟΝ, 01ΙΣΟΤ, ΥΠΟΣΥΝΑΘΡ, ΑΝΣΥΝΟΛΟ/ΚΑΛΥΨΗΚΟΜΒΩΝ, 3ΧΡΩΜΑΤΙΣΜΟΣ, ΔΙΑΧΩΡΙΣΜΟΣ

Οι ασκήσεις υπάρχουν στα PDF:

• Exercises_Algorithms&Complexity_Synopsis.pdf
• Algorithms_Algorithms&Complexity_Synopsis.pdf

---

[4] Navigation Screenshots

• Lecture_Navigation.png
• Theory_Navigation.png
• Algorithms_Navigation.png
• Exercises.png

Τα headings των PDF έχουν καταγραφεί για γρήγορη πλοήγηση.

---

ΚΑΛΗ ΕΞΕΤΑΣΤΙΚΗ ΝΑ 'ΧΟΥΜΕ ΣΥΝΤΡΟΦΟΙ!!