Δομές Δεδομένων και Ανάλυση Αλγορίθμων

Γενικά

Μαθησιακά Αποτελέσματα

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

  • Θα έχουν αποκτήσει πολύ καλή γνώση των θεμελιωδών δομών δεδομένων
  • θα είναι σε θέση να χρησιμοποιούν τις δομές δεδομένων για την υλοποίηση καλοσχεδιασμένων και αποδοτικών προγραμμάτων.
  • Θα έχουν κατανοήσει τις έννοιες της αφαίρεσης, των αφηρημένων τύπων δεδομένων και της αντικειμενοστρέφειας και το ρόλο που παίζουν στην ανάπτυξη των προγραμματιστικών συστημάτων
  • Θα είναι σε θέση να εφαρμόουν την Αναδρομή ως Μεθοδολογία Προγραμματισμού
  • Θα έχουν ουσιαστικοποιήσει τις γνώσεις τους στις τεχνικές της γλώσσας αντικειμενοστρεφούς προγραμματισμού (Java) στην ανάπτυξη Αλγορίθμων και Δομών Δεδομένων
  • Θα μπορούν να αναλύουν την πολυπλοκότητα των προγραμμάτων που αναπτύσσουν
Γενικές Ικανότητες
  • Αναζήτηση, ανάλυση και σύνθεση δεδομένων και πληροφοριών, με τη χρήση και των απαραίτητων τεχνολογιών
  • Αυτόνομη εργασία
  • Ομαδική εργασία

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

Εισαγωγικές Εννοιες:
Δομές Δεδομένων, Τύποι Δεδομένων και η υλοποίησή τους
Αφηρημένοι Τύποι Δεδομένων (Abstract Data Types)
Απόκριψη πληροφορίας, “ενκαψούλωση” δεδομένων, κληρονομικότητα και πολυμορφισμός.
Πρωταρχικοί Τύποι Δεδομένων στη Java
Τύποι Αναφοράς στη Java
Ελεγχος τύπων (type checking)

Ανάλυση Πολυπλοκότητας:
Τύποι πολυπλοκότητας
Παραδείγματα ανάλυσης πολυπλοκότητας αλγορίθμων ταξινόμησης

Γραμμικές Δομές Δεδομένων:
Πίνακες (Arrays)
Διανύσματα (Vectors)
Συμβολοσειρές (Strings) Αμετάβλητες και Ευμετάβλητες συμβολοσειρές
H κλάση StringTokenizer στη Java

Στοίβες και Ουρές: (Stacks & Queues)
Υλοποίηση Στοίβας με τη βοήθεια Πίνακα και Διανύσματος
Υλοποίηση Ουράς με τη βοήθεια Πίνακα και Διανύσματος
Κυκλική Ουρά

Δυναμικές Δομές Δεδομένων
Συνδεδεμένες Λίστες (Linked Lists)
Εφαρμογές Δυναμικής Εκχώρησης μνήμης
Υλοποίηση Στοίβας και Ουράς με τη βοήθεια Συνδεδεμένης Λίστας

Αναδρομή:
Αναδρομικοί αλγόριθμοι και αναδρομικές δομές δεδομένων
Η Αναδρομή σαν Μεθοδολογία Προγραμματισμού

Δέντρα (Trees):
Ορισμοί και ορολογία
Δυαδικά Δέντρα
Υλοποίηση Δυαδικών Δέντρων με τη βοήθεια Δεικτών
Μέθοδοι Διέλευσης από τους κόμβους Δυαδικού Δέντρου
Δυαδικά Δέντρα Αναζήτησης
Σωροί και Λίστες Προτεραιοτήτων

Γράφοι (Graphs):
Ορισμοί και ορολογία
Τρόποι υλοποίησης γράφων
Βασικοί αλγόριθμοι γράφων.

Αρχεία και Ρεύματα (Files & Streams):
Φυσική και Λογική Οργάνωση αρχείων
Ακολουθιακά αρχεία
H Εννοια του Stream στη Java
Streams Εισόδου Αρχείων (Είσοδος Αρχείων)
Streams Εξόδου Αρχείων (Εξοδος Αρχείων)
Διάφοροι Τυποι Streams – Φίλτρα
Αρχεία κατ’ ευθείαν πρόσβασης, hashing

Διδακτικές και Μαθησιακές Μέθοδοι - Αξιολόγηση

Τρόπος Παράδοσης
  • Πρόσωπο με πρόσωπο θεωρητική διδασκαλία (παράδοση, συζήτηση, επίλυση προβλημάτων, ασκήσεις πράξης).
Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών
  • Χρήση λογισμικού παρουσιάσεων διαφανειών.
  • Χρήση ηλεκτρονικής πλατφόρμας μάθησης (moodle).
  • Χρήση Αντικειμενοστρεφούς γλώσσας προγραμματισμού Java
  • Χρήση ολοκληρωμένου περιβάλλοντος ανάπτυξης λογισμικού (π.χ. Netbeans)
Οργάνωση Διδασκαλίας
Δραστηριότητα Φόρτος εργασίας εξαμήνου
Διαλέξεις52
Ανάπτυξη-δοκιμή προγραμματιστικών ασκήσεων60
Ατομική Μελέτη και ανάλυση βιβλιογραφίας68
Σύνολο 180
Αξιολόγηση φοιτητών

Τελική Γραπτή Εξέταση (100% της βαθμολογίας) που περιλαμβάνει:
- Ερωτήσεις Σύντομης Απάντησης
- Δοκιμασίες πολλαπλής επιλογής
- Επίλυση προβλημάτων

Συνιστώμενη Βιβλιογραφία

Συγγράμματα μέσω του συστήματος "Εύδοξος"
  1. Michael Goodrich & Roberto Tamassia. “Data Structures and Algorithms in Java”, 4th Edition, Addison-Wesley (2006). Κυκλοφορεί μετάφρασή του στα Ελληνικά: Δομές Δεδομένων & Αλγόριθμοι σε JAVA (Κωδ στον «Εύδοξο» 32997672)
  2. Robert Sedgewick. "Algorithms in Java, Parts 1-4 : Fundamentals, Data Structures, Sorting, Searching", 3rd Edition, Addison-Wesley (2003). Κυκλοφορεί μετάφρασή του στα Ελληνικά: Αλγόριθμοι σε JAVA (Κωδ. στον «Εύδοξο» 13586)
Συμπληρωματική ελληνόγλωσση βιβλιογραφία
  1. Λουκάς Γεωργιάδης, Σταύρος Νικολόπουλος και Λεωνίδας Παληός. «Δομές δεδομένων». Ηλεκτρονικό βιβλίο, ΕΛΛΗΝΙΚΑ ΑΚΑΔΗΜΑΪΚΑ ΣΥΓΓΡΑΜΜΑΤΑ https://repository.kallipos.gr/handle/11419/6217
  2. Δομές Δεδομένων με Java, Σταμάτης Δημοσθένης, Σημειώσεις διαλέξεων του μαθήματος
Συμπληρωματική ξενόγλωσση βιβλιογραφία
  1. “Data Structures and Algorithms in Java”, Michael Goodrich & Roberto Tamassia, 4th Edition, Addison-Wesley (2006)