Παρουσίαση/Προβολή
Αλγόριθμοι και Δομές Δεδομένων (Πα.Πελ. - Εαρινό 2024)
(ΨΣ017) - Σπυρίδων Χρονόπουλος
Περιγραφή Μαθήματος
Η έννοια του αλγορίθμου (algorithm) είναι γνωστή σε ενδιαφερομένους με θέματα Πληροφορικής. Αποτελεί την πρώτη ύλη εμβάθυνσης σε άλλα αντικείμενα θεωρητικής πληροφορικής όπως π.χ. Υπολογιστική Πολυπλοκότητα, Κρυπτογραφία κλπ. καθώς και σε άλλες γνωστικές περιοχές όπως Δίκτυα, Βάσεις Δεδομένων, την Τεχνητή Νοημοσύνη, τον Παγκόσμιο Ιστό, την Επεξεργασία Εικόνας κοκ. Το μάθημα έχει ως στόχο να εισάγει τους φοιτητές και τις φοιτήτριες στις δομές δεδομένων, στους αλγορίθμους και στην ανάλυση της πολυπλοκότητας τους. Με την επιτυχή παρακολούθηση του μαθήματος οι φοιτητές και οι φοιτήτριες θα μπορούν να : (1) έχουν αλγοριθμική σκέψη, (2) εφαρμόζουν την Αναδρομή ως μεθοδολογία προγραμματισμού, (3) κατανοήσουν και να εφαρμόζουν τους αλγορίθμους αναζήτησης και ταξινόμησης, (4) σχεδιάζουν αλγορίθμους βάσει σύγχρονων τεχνικών, (5) αναλύουν την πολυπλοκότητα των αλγορίθμων, (6) κατανοήσουν τη λειτουργία θεμελιωδών δομών δεδομένων, (7) χρησιμοποιούν και να υλοποιούν δομές δεδομένων κτλ.
Ημερομηνία δημιουργίας
Τετάρτη 27 Μαρτίου 2024
-
Διδάσκοντες
Δρ. Σπυρίδων Χρονόπουλος
Περιεχόμενο μαθήματος
• Παρουσίαση απλών αλγορίθμων και ανάλυση τους
• Αναδρομή και βασικοί αναδρομικοί αλγόριθμοι
• Αλγόριθμοι αναζήτησης
• Αλγόριθμοι ταξινόμησης
• Αναδρομικές υλοποιήσεις αλγορίθμων ταξινόμησης και αναζήτησης
• Στατικές δομές δεδομένων, πίνακες
• Υλοποίηση Στοίβας και Ουράς με τη βοήθεια Πίνακα
• Κυκλική Ουρά
• Συνδεδεμένες Λίστες, Διπλά Συνδεδεμένες Λίστες, Κυκλικές Λίστες και Λίστες με Κεφαλή
• Υλοποίηση Στοίβας και Ουράς με τη βοήθεια Συνδεδεμένης Λίστας
• Δυαδικά Δέντρα
• Υλοποίηση Δυαδικών Δέντρων με τη βοήθεια Δεικτών
• Μέθοδοι Διέλευσης από τους κόμβους Δυαδικού Δέντρου
• Δυαδικά Δέντρα Αναζήτησης
• Γράφοι
• Δομές Δεδομένων στη δευτερεύουσα μνήμη
• Ακολουθιακά αρχεία, αρχεία κειμένου, αρχεία από bytes
• Αρχεία κατ’ ευθείαν πρόσβασης, hashingΜαθησιακοί στόχοι
Το μάθημα έχει ως στόχο να εισάγει τους φοιτητές και τις φοιτήτριες στις δομές δεδομένων, στους αλγορίθμους και στην ανάλυση της πολυπλοκότητας τους. Με την επιτυχή παρακολούθηση του μαθήματος οι φοιτητές και οι φοιτήτριες θα:
• αποκτήσουν αλγοριθμική σκέψη
• εφαρμόζουν την Αναδρομή ως μεθοδολογία προγραμματισμού
• κατανοήσουν και να εφαρμόζουν τους αλγορίθμους αναζήτησης και ταξινόμησης
• σχεδιάζουν αλγορίθμους βάσει σύγχρονων τεχνικών
• αναλύουν την πολυπλοκότητα των αλγορίθμων
• κατανοήσουν τη λειτουργία θεμελιωδών δομών δεδομένων
• χρησιμοποιούν τις κατάλληλες δομές δεδομένων για την υλοποίηση αποδοτικών προγραμμάτων
• υλοποιούν δομές δεδομένων συνδεδεμένης λίστας
• υλοποιούν στοίβες και ουρές με χρήση πίνακα και συνδεδεμένης λίστας
• υλοποιούν δυαδικά δέντρα αναζήτησης και θα σχεδιάζουν αλγορίθμους που τα αξιοποιούν
• αναπαριστούν, υλοποιούν και διασχίζουν γράφους
• χρησιμοποιούν τους κατάλληλους τύπους αρχείων ανάλογα με τις ανάγκες της εφαρμογής
• υλοποιούν δομές δεδομένων στο δίσκο χρησιμοποιώντας ακολουθιακά αρχεία και αρχεία κατ’ ευθείαν πρόσβασηςΜέθοδοι διδασκαλίας
- Παράδοση μαθημάτων όπως ορίζεται από το πρόγραμμα μαθημάτων του Τμήματος.
- Παράδοση μαθημάτων με τη χρήση ψηφιακών μέσων διδασκαλίας.
- Παράδοση μαθημάτων με τη χρήση ψηφιακής πλατφόρμας τηλεκπαίδευσης με σκοπό την ανάρτηση ψηφιοποιημένου οπτικοακουστικού και έντυπου υλικού και δεδομένων σχετικά με το μάθημα.
- Παρουσίαση εργασιών από φοιτητές ή από ομάδες φοιτητών (5-10 λεπτά), και αν αυτό καταστεί εφικτό, με σκοπό την διερεύνηση της ικανοποιητικής ικανότητάς τους να αποδώσουν το αντικείμενο των εργασιών τους.
- Παρουσίαση διαφόρων τύπων αλγορίθμων σχετικούς με το μάθημα.
- Επισκέψεις – διαλέξεις από επισκέπτες-εισηγητές (αν καταστεί εφικτό).
Χρήση Τεχνολογιών Πληροφορικής και Επικοινωνιών
Χρήση Τεχνολογιών Πληροφορικής και Επικοινωνιών
• Παρουσιάσεις μέσω projector.
• Υποστήριξη μαθησιακής διαδικασίας μέσω της ηλεκτρονικής πλατφόρμας e-classΜέθοδοι αξιολόγησης
Όλες οι παρακάτω διαδικασίες αξιολόγησης συνδράμουν στην επίτευξη προβιβάσιμου βαθμού και επομένως στην πιστοποίηση της επιτυχημένης ολοκλήρωσης των φοιτητικών υποχρεώσεων σε σχέση με το εν λόγω αντικείμενο μελέτης:
- Τελική εξέταση (δια ζώσης) καθώς και Πρόοδοι (αν καταστεί εφικτό)
- Προαιρετική εκπόνηση εργασίας (20%) και προφορική εξέταση (παρουσίαση – 10%) (Μόνο κατόπιν συνεννόησης με τον υπεύθυνο καθηγητή και μόνο εφόσον ισχύσει για όλους τους φοιτητές. Δεν μπορεί να ισχύσει μεμονωμένα σε καμμία περίπτωση)
- Γραπτή τελική εξέταση στη θεωρία (70% υπό την προϋπόθεση εκπόνησης εργασιών) που θα περιλαμβάνει:
- ερωτήσεις κρίσεως (απόδειξη κατανόησης εννοιών),
- ερωτήσεις που απαιτούν σύνθεση πληροφοριών και κριτική σκέψη,
- ή/και ερωτήσεις Σύντομης Απάντησης.
Προτεινόμενα συγγράμματα
- Robert Sedgewick, Αλγόριθμοι σε C, Εκδόσεις Κλειδάριθμος, 2006
- Ν. Μισυρλής, Δομές Δεδομένων με C
- Παπουτσής Ιωάννης, Εισαγωγή στις Δομές Δεδομένων και στους Αλγόριθμους (Υλοποίηση σε C), Τόμος Α, 6η έκδοση, εκδόσεις Α. Σταμούλης, Αθήνα, 2010 (κωδικός στον Εύδοξο: 23101)