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

(ICTE332) -  Νικόλαος Πλόσκας

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

Σκοπός του μαθήματος είναι η ανάλυση και σχεδίαση αλγορίθμων. Μετά την επιτυχή ολοκλήρωση του μαθήματος, οι φοιτητές θα είναι σε θέση:

• να πραγματοποιούν ανάλυση αλγορίθμων,
• να μελετούν αλγορίθμους ως προς την πολυπλοκότητα
• να εκτελούν ασυμπτωτική ανάλυση αλγορίθμων να σχεδιάζει και να υλοποιεί προγραμματιστικά μια σειρά από αναδρομικούς και άπληστους αλγόριθμους
• να σχεδιάζουν και να υλοποιούν αλγορίθμους εφαρμόζοντας τις αρχές του δυναμικού προγραμματισμού
• να κατανοούν και να εφαρμόζουν αλγορίθμους γραφημάτων και δικτύων
• να κατανοούν τις κλάσεις P και NP

Διδακτικές ενότητες

• Ρυθμός αύξησης συναρτήσεων
• Ασυμπτωτικός συμβολισμός
• Πολυπλοκότητα αλγορίθμων
• Αναδρομή
  • Αναδρομικές σχέσεις
• Πιθανοτική ανάλυση και τυχαιοκρατικοί αλγόριθμοι
• Αλγόριθμοι ωμής βίας ή εξαντλητικής αναζήτησης
• Διαίρει και βασίλευε
• Δυναμικός προγραμματισμός
• Οπισθοδρόμηση
• Διακλάδωση και περιορισμός
• Άπληστοι αλγόριθμοι
• Αλγόριθμοι γραφημάτων
  • Στοιχειώδεις αλγόριθμοι γραφημάτων
    • Οριζόντια διερεύνηση
    • Καθοδική διερεύνηση
    • Τοπολογική ταξινόμηση
  • Ελαφρύτατα συνδετικά δένδρα
    
    • Prim
    • Kruskal
  • Ελαφρύτατες διαδρομές
    
    • Bellman-Ford
    • Dijkstra
    • Floyd-Warshall
    • Johnson
  • Μέγιστη ροή
    
    • Ford-Fulkerson
• P vs NP
• Προσεγγιστικοί αλγόριθμοι
• Ευρετικοί αλγόριθμοι

 

Βιβλιογραφία

• Εισαγωγή στους αλγόριθμους (μετάφραση της 3ης αγγλικής έκδοσης): Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein, Πανεπιστημιακές Εκδόσεις Κρήτης, 2016 (Κωδικός βιβλίου στον Εύδοξο: 59359780)
  • Αντίτυπα στη βιβλιοθήκη (2η έκδοση) με ταξινομικό αριθμό QA76.6.I585815 2012

• Σχεδιασμός αλγορίθμων: Jon Kleinberg, Eva Tardos, Εκδόσεις Κλειδάριθμος, 2009 (Κωδικός βιβλίου στον Εύδοξο: 13898)
  • Αντίτυπα στη βιβλιοθήκη με ταξινομικό αριθμό QA267.7.K5416 2008
• Αλγόριθμοι: Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Εκδόσεις Κλειδάριθμος, 2009 (Κωδικός βιβλίου στον Εύδοξο: 13583)
  • Αντίτυπα στη βιβλιοθήκη με ταξινομικό αριθμό QA9.58.D37 2009
• Ανάλυση και σχεδίαση αλγορίθμων (3η έκδοση): Anany Levitin, Εκδόσεις Τζιόλα, 2018 (Κωδικός βιβλίου στον Εύδοξο: 68370088)
  
  • Αντίτυπα στη βιβλιοθήκη με ταξινομικό αριθμό QA76.9.A43L48 2018

• Ανάλυση και σχεδίαση αλγορίθμων: Κωνσταντίνος Παπαρρίζος, Εκδόσεις Τζιόλα, 2010 (Κωδικός βιβλίου στον Εύδοξο: 18548861)

• Αλγόριθμοι (2η έκδοση): Παναγιώτης Μποζάνης, Εκδόσεις Τζιόλα, 2017 (Κωδικός βιβλίου στον Εύδοξο: 68369726)

  • Αντίτυπα στη βιβλιοθήκη (1η έκδοση) με ταξινομικό αριθμό QA76.9.A43B69 2005

Συμπληρωματική Βιβλιογραφία

• Grokking algorithms: An illustrated guide for programmers and other curious people: Aditya Bhargava, Simon and Schuster, 2016
• The algorithm design manual (3rd edition): Steven Skiena, Springer, 2020.

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

Τρίτη 19 Φεβρουαρίου 2019