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

(ALG001) -  Σοφιανός Δ. Βασίλειος

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

Στόχος μαθήματος: η εισαγωγή των φοιτητών σε θεμελιώδεις αλγοριθμικές έννοιες και τεχνικές.

 

Περιεχόμενο μαθήματος:

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

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

 

2. Βασικές έννοιες Ανάλυσης και Πολυπλοκότητας Αλγορίθμων

• Αποδοτικότητα και χρονική πολυπλοκότητα, βέλτιστο αλγορίθμων, ασυμπτωτική πολυπλοκότητα, ορθότητα αλγορίθμων.

 

3. Βασικοί Αλγόριθμοι και Στοιχειώδεις Δομές Δεδομένων

• Πίνακες, λίστες, στοίβες, ουρές, δένδρα.
• Αλγόριθμοι εύρεσης ελαχίστου ή μεγίστου στοιχείων, συγχώνευσης, ενθετικής ταξινόμησης, δυαδικής αναζήτησης, απαρίθμησης πλειάδων.

• Σωρός, ουρές προτεραιότητας και εφαρμογή τους στην ταξινόμηση στοιχείων (heapsort)

4. Ευσταθές Ταίριασμα

• Διατύπωση προβλήματος και εφαρμογές του.
• Αλγόριθμος πρότασης/απόρριψης.
• Ανάλυση ορθότητας και πολυπλοκότητας αλγορίθμου.
• Αποδοτική υλοποίηση αλγορίθμου.

 

5. Τεχνική «Διαίρει και Βασίλευε» και Εφαρμογές της

• Γενική περιγραφή τεχνικής «Διαίρει & Βασίλευε».

• Αλγόριθμοι συγχωνευτικής ταξινόμησης (mergesort) και μέτρησης αντιστροφών.

• Αναδρομικές σχέσεις και μέθοδοι επίλυσής τους.

 

6. Γραφήματα και Αλγόριθμοι Γραφημάτων

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

 

7. Τεχνική Απληστίας και Εφαρμογές της

• Γενική περιγραφή τεχνικής απληστίας.
• Αλγόριθμοι επίλυσης προβλημάτων χρονοπρογραμματισμού: χρονοπρογραμματισμός διαστημάτων, διαμέριση χρονικών διαστημάτων, χρονοπρογραμματισμός για ελαχιστοποίηση καθυστέρησης.

• Αλγόριθμοι επίλυσης προβλημάτων βελτιστοποίησης: ελάχιστα γεννητικά δένδρα (αλγόριθμοι Kruskal και Prim), συντομότερες διαδρομές (αλγόριθμος Dijkstra).

• Αποδοτική υλοποίηση αλγορίθμων βελτιστοποίησης.

 

8. Τεχνική Δυναμικού Προγραμματισμού και Εφαρμογές της

Γενική περιγραφή τεχνικής δυναμικού προγραμματισμού.

Αποδοτική εφαρμογή και υλοποίηση τεχνικής δυναμικού χρονοπρογραμματισμού.

Αλγόριθμοι επίλυσης προβλημάτων σταθμισμένου χρονοπρογραμματισμός διαστημάτων. Αλγόριθμοι επίλυσης προβλημάτων σακιδίου.

Αλγόριθμος Karatsuba και άλλες εφαρμογές.

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

Δευτέρα 16 Δεκεμβρίου 2024