Ιστοσελίδα Μαθήματος ΕΜ 240: Δομές Δεδομένων (Data Structures)

Εαρινό Εξάμηνο 2010/11

 

Διδάσκων:  Βαγγέλης Χαρμανδάρης

email: vagelis@tem.uoc.gr

Ώρες Γραφείου (Θ304b): Δευτέρα, Τετάρτη 09:00-12:00

Ώρες Μαθήματος  (αίθουσα Θ202):                                         Δευτέρα 15:00-17:00

Ώρες Εργαστηρίου/Φροντιστηρίου (αίθουσα Η203):        Παρασκευή 17:00-19:00, Τετάρτη  17:00-19:00

                                                                                                             

 

Ύλη του Μαθήματος

Το μάθημα αυτό είναι εισαγωγικό στις δομές δεδομένων. Κύριοι στόχοι του μαθήματος είναι:

· Η κατανόηση βασικών αρχών και εννοιών των δομών δεδομένων.

· Η περιγραφή των κύριων λειτουργιών των δομών δεδομένων με ιδιαίτερη αναφορά στους πίνακες, στις στοίβες, στις ουρές και στα (δυωνυμικά και  άλλα) δένδρα.

· Η εφαρμογή όλων των παραπάνω σε διάφορα επιστημονικά υπολογιστικά προβλήματα.

 

Το μάθημα είναι χωρισμένο σε επιμέρους υπό-κεφάλαια. Αρχικά, στην εισαγωγή θα δούμε τις βασικές έννοιες των δομών δεδομένων. Επίσης θα παρουσιάσουμε μια σύντομη επισκόπηση, με βασικά παραδείγματα, της C++. Τo δεύτερο κεφάλαιο αφορά την ανάλυση αλγορίθμων και την απόδοση προγραμμάτων. Ιδιαίτερη έμφαση δίνεται στον ασυμπτωτικό συμβολισμό. Το τρίτο κεφάλαιο παρουσιάζει τις βασικές ιδιότητες και λειτουργίες μιας δομής δεδομένων, δηλαδή αναπαράσταση, απαρίθμηση, ταξινόμηση κλπ.  Στο τέταρτο κεφάλαιο αναφέρονται οι πίνακες, οι στοίβες και οι ουρές. Αναλύονται βασικά παραδείγματα και εφαρμογές.  Το τελευταίο κεφάλαιο αφορά τα δένδρα. Αρχικά παρουσιάζονται τα διωνυμικά δένδρα με τις βασικές εφαρμογές τους. Ακολουθούν εφαρμογές εύρεσης και δένδρα αναζήτησης.

 

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

· Δομές Δεδομένων, Αλγόριθμοι και Εφαρμογές στη C++, S. Sahnii,  Εκδόσεις Τζιόλα, 2004.

· Αλγόριθμοι σε C, Μέρη 1-4 (Θεμελιώδεις Έννοιες, Δομές Δεδομένων, Ταξινόμηση, Αναζήτηση), Robert Sedgewick, Τρίτη Αμερικάνικη Έκδοση, Εκδόσεις Κλειδάριθμός 2005.

· Δεδομένων, Έννοιες, Τεχνικές και Αλγόριθμοι, Γ.Φ. Γεωργακόπουλος.,  Πανεπιστημιακές Εκδόσεις Κρήτης, Ηράκλειο 2002.

· Εισαγωγή στους αλγορίθμους Τόμος Ι, T.H. Cormen, C.E. Leiserson, R.L. Rivest, Πανεπιστημιακές Εκδόσεις Κρήτης, Ηράκλειο 2006.

 

Διδασκαλία  - Αξιολόγηση

Για τις διδακτικές ανάγκες του μαθήματος θα χρησιμοποιηθούν οι σημειώσεις και φυλλάδια, σε μορφή slides,  τα οποία θα μοιράζονται σε τακτά χρονικά διαστήματα.  Επίσης η υλοποίηση των αλγορίθμων θα  γίνει σε υπολογιστές του τμήματος μας (Η203, Η205).

 

Η αξιολόγηση θα βασιστεί κατά κύριο λόγο στη συμμετοχή, στις εργαστηριακές ασκήσεις, στο τελικό διαγώνισμα και πιθανώς σε ένα project.  Στις εργαστηριακές ασκήσεις θα γίνεται υλοποίηση των σχετικών μεθόδων και θα χρησιμοποιούνται για την επίλυση προβλημάτων που προκύπτουν κυρίως από εφαρμογές. Για την υλοποίηση των αλγορίθμων δομών δεδομένων θα χρησιμοποιηθεί η γλώσσα C ή C++. Πιο συγκεκριμένα ο βαθμός θα προκύπτει ως εξής: Εργαστήριο/Ασκήσεις (50%) +  Τελική Εξέταση (50%) ή Εργαστήριο/Ασκήσεις (30%) +  Τελική Εξέταση (30%) + Project (40%). Η βάση είναι 50%.

 

Ηλεκτρονική Λίστα Αλληλογραφίας

Ενημέρωση σχετικά με το μάθημα (για τις σειρές ασκήσεων, ημερομηνίες εξετάσεων, κ.τ.λ.) γίνεται από την ηλεκτρονική λίστα αλληλογραφίας. Για να γραφτείτε στην ηλεκτρονική λίστα αλληλογραφίας του μαθήματος στείλτε email με κενό θέμα και περιεχόμενο subscribe em240-list στην διεύθυνση majordomo@tem.uoc.gr. Στην συνέχεια θα σας σταλεί ένα email στο οποίο θα χρειαστεί να απαντήσετε χρησιμοποιώντας κάποιο συγκεκριμένο μήνυμα για επιβεβαίωση. Για να εγγραφείτε στην λίστα πρέπει να χρησιμοποιήσετε την ηλεκτρονική διεύθυνση που σας παρέχεται από το Πανεπιστήμιο Κρήτης (για παράδειγμα username@tem.uoc.gr ή username@math.uoc.gr).

 

 

Σημειώσεις του Μαθήματος

· Πρόγραμμα Διδασκαλίας — Ημερολόγιο του Μαθήματος

· Κεφάλαιο 1: Εισαγωγή

· Overview of C++

· Κεφάλαιο 2: Ανάλυση - Απόδοση Αλγορίθμων

· Κεφάλαιο 3: Γραμμικές Λίστες

· Κεφάλαιο 4: Στοίβες  - Ουρές

· Κεφάλαιο 5: Δένδρα

 

Σειρές Ασκήσεων

· Σειρά Ασκήσεων 1

· Σειρά Ασκήσεων 2

· Σειρά Ασκήσεων 3

 

Παραδείγματα — Κώδικες

· C++ Example: c++example.cpp

·  List Example in c: listexample.c

· Array Stack: arrayStack.cpp

· Stack  - List: listStack.cpp

·  

 

Χρήσιμοι Σύνδεσμοι στο Διαδίκτυο

· C++: Tutorial

· Data Structures Tutorial

· C mini course (by Ken Thompson and Dennis Richie)

· C++ mini course (by Ken Thompson and Dennis Richie)

· Data Structures Tutorial

·  

· Open Courses: Advanced Data Structures

· Video Lectures: MIT: Introduction to Algorithms

 

· TOP500 Supercomputing Sites