Topic outline

  • General

    Εισαγωγή στη Θεωρία και Ανάλυση Αλγορίθμων

    Διδάσκων : Χ. Παπαδόπουλος

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

    Μαθησιακοί Στόχοι Μαθήματος: Στόχος του μαθήματος είναι η μετάδοση γνώσεων στους σπουδαστές του τμήματωμ Μαθηματικών για την ανάλυση αλγορίθμων, την αποδοτικότητα, τον ασυμπτωτικός συμβολισμός. Οι συνηθισμένοι χρόνοι εκτέλεσης και οι βασικές δομές δεδομένων όπως: πίνακες, λίστες, στοίβες, ουρές. Ακόμα αναλύονται έννοιες όπως το ευσταθές ταίριασμα, ορθότητα σωρός και ουρά προτεραιότητας. Μέθοδος «Διαίρει και Βασίλευε»:Εφαρμογές σε ταξινόμηση στοιχείων, Επίλυση αναδρομικών σχέσεων. Γραφήματα και αλγόριθμοι γραφημάτων: Διάτρεξη γραφημάτων (BFS, DFS), Συνεκτικότητα, Τοπολογική διάταξη. Μέθοδοι «Απληστείας» και «Δυναμικού Προγραμματισμού»:Ελάχιστα σκελετικά δένδρα (αλγόριθμος Prim, αλγόριθμος Kruskal), Συντομότερες διαδρομές (αλγόριθμος Dijkstra, Ροή δικτύου), Χρονοπρογραμματισμός. Επιλεγμένα θέματα: Υπολογιστική πολυπλοκότητα, NP-πληρότητα

    Λέξεις κλειδιά: Βασικές δομές δεδομένων. ασυμπτωτικός συμβολισμός, ευσταθές ταίριασμα, μέθοδος διαίρει και βασίλευε, ταξινόμηση στοιχείων, επίλυση αναδρομικών σχέσεων, αλγόριθμοι BFS και DFS, συνεκτικότητα, τοπολογική ταξινόμηση, ελάχιστα σκελετικά δένδρα, συντομότερες διαδρομές, μέθοιδοι απληστίας και δυναμικού προγραμματισμού, ΝΡ-πληρότητα.

  • 1. Βασικά στοιχεία σχεδίασης & ανάλυσης αλγορίθμων

    Περιγραφή θεματικής ενότηταςΒασικά στοιχεία σχεδίασης & ανάλυσης αλγορίθμων. Εισαγωγικά θέματα του μαθήματος. Η έννοια της αποδοτικότητας ενός αλγορίθμου. Αντιπροσωπευτικά προβλήματα ως προς την πολυπλοκότητα χρόνου. Ορισμοί πολυωνυμικού και εκθετικού χρόνου.

    Λέξεις κλειδιά: Ταχύτητα επίλυσης προβλημάτων με Η/Υ 

    Ύλη βιβλιογραφίας:
    [KT]: Κεφάλαιο 2.1, 
    [CLRS]: Κεφάλαια 1.1, 1.2, 2.1, 2.2

  • 2. Ανάλυση αλγορίθμων

    Περιγραφή θεματικής ενότητας : Ανάλυση αλγορίθμων, Αποδοτικότητα, Ασυμπτωτικός ρυθμός αύξησης και ασυμπτωτικοί συμβολισμοί. Ασυμπτωτικά όρια για κάποιες συνηθισμένες συναρτήσεις. Επισκόπηση Συνηθισμένων Χρόνων Εκτέλεσης. Εφαρμογές σε Κατάταξη Συναρτήσεων.

    Λέξεις κλειδιά : βήματα αλγορίθμου, ασυμπτωτικός χρόνος εκτέλεσης, αποδοτικός αλγόριθμος

    Ύλη Βιβλιογραφίας
    [KT]: Κεφάλαιο 2.2, 2.4 
    [CLRS]: Κεφάλαιο 3.1

  • 3. Συνηθισμένοι χρόνοι εκτέλεσης και δομές δεδομένων

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

    Λέξεις κλειδιά : πίνακες, λίστες, ουρές, στοίβες, χρόνοι εκτέλεσης αλγορίθμου

    Ύλη Βιβλιογραφίας
    [KT]: Κεφάλαιο 2.4, 2.5 
    [CLRS]: Κεφάλαια 3.2, 10.1, 11.1.

  • 4. Ευσταθές ταίριασμα, ορθότητα, σωρός και ουρά προτεραιότητας

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

    Λέξεις κλειδιά: σωρός και ουρά προτεραιότητας, ευσταθές ταίριασμα, ορθότητα, ανάλυση αλγορίθμου 

    Ύλη Βιβλιογραφίας
    [KT]: Κεφάλαιο 1.1, 2.3, 2.5 
    [CLRS]: Κεφάλαιο 6.

  • 5. Μέθοδος «Διαίρει και Βασίλευε», ταξινόμηση στοιχείων και επίλυση αναδρομικών σχέσεων

    Περιγραφή θεματικής ενότητας: Μέθοδος «Διαίρει και Βασίλευε», ταξινόμηση στοιχείων με συγχώνευση. Επίλυση αναδρομικών σχέσεων με τις μεθόδους εκδίπλωσης αναδρομής (δέντρο αναδρομής), Επαναληπτική μέθοδος – ανάπτυξη διαδρομής, Μέθοδος αντικατάστασης – σωστής πρόβλεψης, αλλαγής μεταβλητών, Βασικό Θεώρημα Αναδρομών (Μaster Theorem), Γραμμικές αναδρομικές σχέσεις. Κάτω Φράγματα σε Αναζητήσεις και Ταξινομήσεις. Μέτρηση αντιστροφών. Πλησιέστερο ζεύγος σημείων. 

    Λέξεις κλειδιά: αποδοτικοί αλγόριθμοι ταξινόμησης, μέθοδος διαίρει και βασίλευε, τρόποι επίλυσης αναδρομικών σχέσεων

    Ύλη Βιβλιογραφίας
    [KT]: Κεφάλαιο 5.1, 5.2, 5.3, 5.4
    [CLRS]: Κεφάλαιο 2.3, 4.1, 4.2, 4.3,  7.1, 7.2

  • 6. Βασικοί αλγόριθμοι γραφημάτων

    Περιγραφή θεματικής ενότητας: Βασικές έννοιες και ιδιότητες γραφημάτων. Αλγόριθμοι γραφημάτων: διάσχιση κατά πλάτος (BFS), διάσχιση κατά βάθος (DFS). Αποδοτική υλοποίηση των αλγορίθμων και πρακτικές εφαρμογές. Διμερή γραφήματα. Κατευθυνόμενα Άκυκλα Γραφήματα. Συνεκτικότητα γραφημάτων και τοπολογική ταξινόμηση. 

    Λέξεις κλειδιά: διάσχιση κατά πλάτος (BFS), διάσχιση κατά βάθος (DFS), τοπολογική ταξινόμηση

    Ύλη Βιβλιογραφίας
    [KT]: Κεφάλαιο 3.1, 3.2, 3.3, 3.4, 3.5, 3.6
    [CLRS]: Κεφάλαιο 22.1, 22.2, 22.3, 22.4, 22.5

  • 7. 'Απληστοι αλγόριθμοι, χρονοπρογραμματισμός και συντομότερες διαδρομές (Dijkstra)

    Περιγραφή θεματικής ενότητας: 'Απληστοι αλγόριθμοι. Χρονοπρογραμματισμός Διαστημάτων. Ορθότητα άπληστων αλγορίθμων. Διαμέριση Χρονικών Διαστημάτων. Χρονοπρογραμματισμός για Ελαχιστοποίηση Καθυστέρησης. Στρατηγικές Ανάλυσης Άπληστων Αλγορίθμων και παραδείγματα. Συντομότερες Διαδρομές σε Γραφήματα και ο αλγόριθμος του Dijkstra. 

    Λέξεις κλειδιά: χρονοπρογραμματισμός, άπληστη επιλογή, συντομότερη διαδρομή, ο αλγόριθμος του Dijkstra

    Ύλη Βιβλιογραφίας
    [KT]: Κεφάλαιο 4.1, 4.2, 4.4
    [CLRS]: Κεφάλαιο 16.1, 16.2, 16.5, 24.3

  • 8. Ελάχιστα σκελετικά δένδρα (αλγόριθμοι Prim και Kruskal), κωδικοποίηση Huffman

    Περιγραφή θεματικής ενότητας: Ελάχιστα σκελετικά δένδρα (αλγόριθμοι Prim και Kruskal). Ιδιότητα αποκοπής και η ιδιότητα του κύκλου. Αποδοτική υλοποίηση των αλγορίθμων. Ανάλυση και χαρακτηρισμός των αλγορίθμων. H δομή δεδομένων Union-Find. Κώδικες Huffman και Συμπίεση Δεδομένων.

    Λέξεις κλειδιά: άπληστη επιλογή, σκελετικό δένδρο, ελαφρύτερο σκελετικό δένδρο, κωδικοποίηση χαρκτήρων κατά Huffman

    Ύλη Βιβλιογραφίας
    [KT]: Κεφάλαιο 4.5, 4.6, 4.8
    [CLRS]: Κεφάλαιο 23.1, 23.2, 16.3

  • 9. Μέθοδος "δυναμικού προγραμματισμού": Ροή δικτύου, χρονοπρογραμματισμός και σακίδια

    Περιγραφή θεματικής ενότητας: Μέθοδος "δυναμικού προγραμματισμού". Σταθμισμένος Χρονοπρογραμματισμός Διαστημάτων. Τμηματοποιημένα Ελάχιστα Τετράγωνα. Αθροίσματα Υποσυνόλων και Σακίδια.  Ευθυγράμμιση Ακολουθίας. Συντομότερα Μονοπάτια – Αλγόριθμος του Bellman-Ford. Εύρεση αρνητικών κύκλων σε γραφήματα. 

     Ροή δικτύου, χρονοπρογραμματισμός και σακίδια

    Λέξεις κλειδιά: δυναμικός προγραμματισμός, χρονοπρογραμματισμός, πρόβλημα του σακιδίου (Knapsack)

    Ύλη Βιβλιογραφίας
    [KT]: Κεφάλαιο 6.1, 6.2, 6.3, 6.4, 6.6, 6.8, 6.10
    [CLRS]: Κεφάλαιο 15.1, 15.2, 15.3, 15.4, 15.5, 24.1

  • 10. Επιλεγμένα θέματα: Υπολογιστική πολυπλοκότητα και ΝΡ-πληρότητα

    Περιγραφή θεματικής ενότητας: Επιλεγμένα θέματα: Υπολογιστική πολυπλοκότητα και ΝΡ-πληρότητα. Κατηγοριοποίηση προβλημάτων ως προς την Υπολογισιμότητα. Αναγωγές Πολυωνυμικού Χρόνου. Αναγωγή από Απλή Ισοδυναμία. Αναγωγή από ειδική περίπτωση σε γενική περίπτωση. Αναγωγή με μικροεργαλεία (gadgets). Η κλάση ΝΡ. ΝΡ-πλήρη προβλήματα. 

    Λέξεις κλειδιά: υπολογιστική πολυπλοκότητα, οι κλάσεις P και NP, ΝΡ-πληρότητα, αναγωγή πολυωνυμικού χρόνου

    Ύλη Βιβλιογραφίας
    [KT]: Κεφάλαιο 8
    [CLRS]: Κεφάλαιο 34 (Β' τόμος)

  • 11. Επανάληψη

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

    Λέξεις κλειδιά: επανάληψη της ύλης

     

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

    Επιλογή 1:
    [KT] J. Kleinberg and E. Tardos, Σχεδιασμός Αλγορίθμων, ελληνική έκδοση, Εκδόσεις Κλειδάριθμος, 2008 (4η επιλογή στον Εύδοξο).

    Επιλογή 2:
    [CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Εισαγωγή στους Αλγορίθμους, ελληνική έκδοση, Πανεπιστημιακές Εκδόσεις Κρήτης, 2012.

    Επιλογή 3:
    [DPV] S. Dasgupta, C. Papadimitriou, and U. Vazirani, Αλγόριθμοι, ελληνική έκδοση,Εκδόσεις Κλειδάριθμος, 2008

    • Διαλέξεις