Please ensure Javascript is enabled for purposes of website accessibility

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

Εικόνα επιλογής

Εισαγωγή στους Αλγορίθμους 2025-2026

(23Υ205) -  Χρήστος Ζαρολιάγκης

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

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

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

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

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

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

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

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

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

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

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

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

Γενική περιγραφή τεχνικής «Διαίρει & Βασίλευε». Αλγόριθμοι συγχωνευτικής ταξινόμησης (mergesort) και μέτρησης αντιστροφών. Αναδρομικές σχέσεις και μέθοδοι επίλυσής τους.

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

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

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

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

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

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

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

Παρασκευή, 26 Σεπτεμβρίου 2025

Σελίδα μαθήματος
  • Περίγραμμα

    Μαθησιακοί στόχοι

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

    Με την ολοκλήρωση της διδασκαλίας του μαθήματος οι φοιτητές θα έχουν αναπτύξει τις ακόλουθες δεξιότητες:

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

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

    Βασικά Συγγράμματα

    Πρώτο Εναλλακτικό Σύγγραμμα

    Δεύτερο Εναλλακτικό Σύγγραμμα

    Τρίτο Εναλλακτικό Σύγγραμμα

    Αλλα συγγράμματα

    • S. Dasgupta, C. Papadimitriou, and U. Vazirani. Αλγόριθμοι, ελληνική έκδοση, Εκδόσεις Κλειδάριθμος, 2008.
    • K. Mehlhorn, Data Structures and Algorithms, Vol.1: Sorting and Searching, Springer-Verlag, 1984.
    • Κ. Τσίχλας, Α. Γούναρης, Ι. Μανωλόπουλος. Σχεδίαση και Ανάλυση Αλγορίθμων, Εκδόσεις Κάλλιπος, 2015.

    Μέθοδοι αξιολόγησης

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

     

    Οι φροντιστηριακές και εργαστηριακές ασκήσεις είναι προαιρετικές, αλλά ενθαρρύνονται όλοι οι φοιτητές να τις εκπονήσουν προκειμένου να κατανόησουν καλύτερα την ύλη και να απόκτησουν πρακτική εμπειρία σε βασικές τεχνικές υλοποίησης.

     

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

    Τελικός Βαθμός  =  max { BTE, (0.7 x ΒΤΕ + 0.15 x ΒΦΑ + 0.15 x ΒΕΡ) }

    όπου ΒΤΕ = Βαθμός Τελικής Εξέτασης, ΒΦΑ = Βαθμός Φροντιστηριακών Ασκήσεων, και ΒΕΡ = Βαθμός Εργαστηριακών Ασκήσεων.