Είσοδος

Αλγόριθμοι και Πολυπλοκότητα

Γενικά στοιχεία

 

 
Περιγραφή

Εισαγωγή. Δομές δεδομένων και αλγόριθμοι. Ασυμπτωτική ανάλυση.
Γραφήματα. Βασικές έννοιες. Αναζήτηση κατά «βάθος» και κατά «πλάτος». Τοπολογική διάταξη.
Η μέθοδος "Διαίρει‐και‐Βασίλευε". Δυαδική αναζήτηση. Πολλαπλασιασμός πινάκων.
Η μέθοδος της Απληστίας. Το πρόβλημα επιλογής δραστηριοτήτων. Κώδικες Huffman. Ελάχιστα μονοπάτια από κοινή αφετηρία (αλγόριθμος Dijkstra). Ελάχιστα διασυνδετικά δένδρα (Αλγόριθμος Prim).
Δυναμικός Προγραμματισμός. Πολλαπλασιασμός αλυσίδας. Μεγίστη κοινή υπο‐ακολουθία. Ελάχιστα μονοπάτια για κάθε ζεύγος κόμβων.
Κάτω φράγματα. Φράγματα εισόδου‐εξόδου. Φράγματα «αντιπάλου» (adversary). Ταξινόμηση, Κώδικες Huffman.
Προβλήματα γραφημάτων. Έλεγχος ακυκλικότητας γραφήματος. Ισχυρά συνδεδεμένα συστατικά. Ελάχιστα διαδυνδετικά δένδρα: ο αλγόριθμος του Kruskal. Ελάχιστα
μονοπάτια από κοινή αφετηρία: ο αλγόριθμος των Bellman‐Ford. Μέγιστη ροή: ο αλγόριθμός των Ford‐Fulkerson και ο αλγόριθμος των Edmonds‐Karp.
NP και υπολογιστική δυσεπιλυσιμότητα. Αναγωγές πολυωνυμικού χρόνου. Η κλάση NP. NP‐πλήρη προβλήματα.

Διδάσκων

Αντώνιος Συμβώνης, Καθηγητής
Κτίριο Μαθηματικού, Γρ. 3.18

Διαλέξεις

  • Τετάρτη 12:45 - 2:30μμ, αιθ. 105, Νέο κτίριο ΣΕΜΦΕ
  • Παρασκευή 8:45 - 10:30πμ, αιθ. 105, Νέο κτίριο ΣΕΜΦΕ 

Υλικό διαλέξεων 

Υλικό φροντιστηριακών ασκήσεων

Σύγγράμματα

  • "Εισαγωγή στους Αλγορίθμους (σε έναν τόμο)"
    Cormen, Leiserson,Rivest, Stein
    Πανεπιστημιακές Εκδόσεις Κρήτης, 2012
    Διανομή από το βιβλιοπωλείο: ...

  • "Σχεδιασμός Αλγορίθμων"
    Kleinberg, Tardos
    Εκδόσεις Κλειδάριθμος
    Διανομή από το βιβλιοπωλείο: ...

Αξιολόγηση

  • Προγραμματιστικές/Γραπτές Ασκήσεις: 15% 
  • Τελικό γραπτό διαγώνισμα: 85%



Συγχρηματοδότηση
από την Ε.Ε.