Παρουσίαση/Προβολή

Υπολογισιμότητα και Πολυπλοκότητα

(CS121) - ΝΙΚΟΛΑΟΣ ΔΗΜΟΚΑΣ

Περιγραφή Μαθήματος

Γενική Περιγραφή

Το μάθημα Υπολογισιμότητα και Πολυπλοκότητα πραγματεύεται ζητήματα όπως:

Ασυμπτωτική Ανάλυση και Ανάλυση Πολυπλοκότητας
Αλγόριθμοι Ωμής Βίας, Διαίρει και Κυρίευε, Μείωσης και Κυριαρχίας
Δένδρα Β-Tree και Β+ Tree
Δυναμικός Προγραμματισμός
Αλγόριθμοι Γράφων και Ελάχιστα Συνδετικά Δένδρα
Αλγόριθμοι Συντομότερων Διαδρομών
Ελάχιστο Συνδεδεμένο Κυρίαρχο Σύνολο και Ομαδοποίηση
Μέγιστη Ροή και Άπληστοι Αλγόριθμοι

Ώρες Διδασκαλίας

Τρίτη: 13:00 – 15:00 (Αίθουσα Β1)
Παρασκευή: 13:00 – 15:00 (Αίθουσα Β1)

Ημερομηνία δημιουργίας

Παρασκευή 9 Οκτωβρίου 2020

Σελίδα μαθήματος

Περίγραμμα
Περιεχόμενο μαθήματος
- Η έννοια του αλγορίθμου και της πολυπλοκότητας.
- Αναδρομικοί αλγόριθμοι και αναδρομικές εξισώσεις.
- Τεχνικές αναζήτησης.
- Τεχνικές διάσχισης σε γράφους.
- Τεχνικές σχεδίασης αλγορίθμων, αλγόριθμοι Divide and conquer, άπληστοι αλγόριθμοι,
  Δυναμικός προγραμματισμός, Δενδροειδείς αλγόριθμοι .
- Προβλήματα απόφασης, οι κλάσεις P και NP, προβλήματα NP-complete και NP-hard
Μαθησιακοί στόχοι

Σκοπός του μαθήματος είναι η εξοικείωση των φοιτητών με τις τεχνικές που χρησιμοποιούνται για την σχεδίαση την ανάλυση και την μέτρηση αποδοτικότητας αλγορίθμων επίλυσης προβλημάτων. Επιπλέον οι φοιτητές θα γνωρίσουν τις βασικές κλάσεις πολυπλοκότητας.

Με την επιτυχή ολοκλήρωση του μαθήματος ο φοιτητής/τρια θα:
- Έχει κατανοήσει τις βασικές αρχές και μεθόδους σχεδίασης αλγορίθμων.
- Γνωρίζει τις πλέον αποδοτικές μεθόδους επίλυσης προβλημάτων.
- Γνωρίζει τις βασικότερες αρχές ανάλυσης και μέτρησης της αποδοτικότητας των αλγορίθμων.
- Γνωρίζει τις βασικότερες κλάσεις πολυπλοκότητας.
Μέθοδοι αξιολόγησης
- Γραπτή τελική εξέταση (100%)
- Προαιρετικά ασκήσεις και εργασία εξαμήνου (20%). Στην περίπτωση αυτή η γραπτή τελική εξέταση θα λάβει το (80%) του τελικού βαθμού.
Προτεινόμενα συγγράμματα
1. Μποζάνης, Παναγιώτης. (2017). Αλγόριθμοι (2^η έκδ.). Εκδόσεις Α. ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε.
  [Κωδικός Βιβλίου στον Εύδοξο: 68369726]
2. Παπαρρίζος, Κωνσταντίνος. (2010). Ανάλυση & Σχεδίαση Αλγορίθμων. Εκδόσεις Α. ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε. [Κωδικός Βιβλίου στον Εύδοξο: 18548861]
3. Levitin, Anavy. (επιμ. Ρουμελιώτης M.). (2018). Ανάλυση και Σχεδίαση Αλγορίθμων (3^η έκδ.).
  Εκδόσεις Α.ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε. [Κωδικός Βιβλίου στον Εύδοξο: 68370088]
4. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L. & Stein Clifford. (2016). Εισαγωγή στους Αλγόριθμους (3^η αμερικανική έκδ.). Εκδόσεις ΙΤΕ & Πανεπιστημιακές Εκδόσεις Κρήτης.
  [Κωδικός Βιβλίου στον Εύδοξο: 59359780]
5. Kleinberg, J. & Tardos, E. (2009). Σχεδιασμός Αλγορίθμων. Εκδόσεις Κλειδάριθμος ΕΠΕ.
  [Κωδικός Βιβλίου στον Εύδοξο: 13898]
6. Dasgupta, S., Papadimitriou, C., & Vazirani, U. (2009). Αλγόριθμοι. Εκδόσεις Κλειδάριθμος ΕΠΕ.
  [Κωδικός Βιβλίου στον Εύδοξο: 13583]
7. Goodrich, Michael T. & Tamassia, Roberto. (2016). Αλγόριθμοι Σχεδίαση και Εφαρμογές. Εκδόσεις Χ.ΓΚΙΟΥΡΔΑ & ΣΙΑ ΕΕ. [Κωδικός Βιβλίου στον Εύδοξο: 59359833]
8. Knuth, Donald E. (2009). Η Τέχνη του Προγραμματισμού: Θεμελιώδεις Αλγόριθμοι (τόμος Α΄) (3^η έκδ.). Εκδόσεις Α. ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε. [Κωδικός Βιβλίου στον Εύδοξο: 18549081]
9. Knuth, Donald E. (2009). Η Τέχνη του Προγραμματισμού: Ημι-αριθμητικοί Αλγόριθμοι (τόμος Β΄) (3^η έκδ.). Εκδόσεις Α. ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε. [Κωδικός Βιβλίου στον Εύδοξο: 18548866]
10. Knuth, Donald E. (2009). Η Τέχνη του Προγραμματισμού: Ταξινόμηση και Αναζήτηση (τόμος Γ΄) (3^η έκδ.). Εκδόσεις Α. ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε. [Κωδικός Βιβλίου στον Εύδοξο: 18548987]