Είσοδος

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

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

 

 
Περιγραφή

  

Εξ αποστάσεως εκπαίδευση --- Σύνδεσμοι WEBEX

Διάλεξη

Σύνδεσμός

Τρίτη 17:00-19:00

https://centralntua.webex.com/centralntua/j.php?MTID=m3188aeed227fff3cfd00a8fb5f59815e

Πέμπτη 16:00-10:30

https://centralntua.webex.com/centralntua/j.php?MTID=m457d8e20c9ba124961fc56870f97874d

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

Διδάσκων

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

Διαλέξεις

·       Τρίτη  17:00 - 19:00, online

·       Πέμπτη  16:00 - 18:00, online

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

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

Σύγγράμματα

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

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

Αξιολόγηση

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


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