Δομές Δεδομένων (2018-...) (CEID_ΝΥ233)

Χρήστος Μακρής, Σπύρος Σιούτας

Περιγραφή

Ύλη: Διάταξη στοιχείων, Διάταξη στοιχείων σε κύρια μνήμη, Bubblesort, Heapsort με ανάλυση, Quicksort με ανάλυση, Διάταξη στοιχείων σε δευτερεύουσα μνήμη. Δομημένοι τύποι στοιχείων, array, record, file, σωροί και ουρές, ουρές με προτεραιότητα, πίστες, δένδρα. O Γραμμικός Median-Aλγόριθμος. Tο πρόβλημα του Λεξικού. Συνοπτικές δομές δεδομένων, Δυϊκό ψάξιμο, Interpolation-ψάξιμο, Binary Interpolation-search, Interpolation-ψάξιμο για άγνωστες μη ισοπιθανές κατανομές. Δυναμικές συνοπτικές δομές δεδομένων. Eκτενείς δομές δεδομένων, ισοζυγισμένα δένδρα, AVL-δένδρο, Kόκκινο-Mαύρο Δένδρο ή BB-δένδρο, το BB[α] δένδρο, Yβριδικές δομές δεδομένων, Tries, Δυναμικό Interpolation ψάξιμο, Tο interpolation search tree (IST), Tο ψάξιμο στο interpolation search tree. Union-find, Hashing, Hashing με αλυσίδες, Συζήτηση των υποθέσεων και του χώρου, Hashing με ανοικτή διεύθυνση (open addressing), Extendible Hashing.

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

Ύλη: Διάταξη στοιχείων, Διάταξη στοιχείων σε κύρια μνήμη, Bubblesort, Heapsort με ανάλυση, Quicksort με ανάλυση, Διάταξη στοιχείων σε δευτερεύουσα μνήμη. Δομημένοι τύποι στοιχείων, array, record, file, σωροί και ουρές, ουρές με προτεραιότητα, πίστες, δένδρα. O Γραμμικός Median-Aλγόριθμος. Tο πρόβλημα του Λεξικού. Συνοπτικές δομές δεδομένων, Δυϊκό ψάξιμο, Interpolation-ψάξιμο, Binary Interpolation-search, Interpolation-ψάξιμο για άγνωστες μη ισοπιθανές κατανομές. Δυναμικές συνοπτικές δομές δεδομένων. Eκτενείς δομές δεδομένων, ισοζυγισμένα δένδρα, AVL-δένδρο, Kόκκινο-Mαύρο Δένδρο ή BB-δένδρο, το BB[α] δένδρο, Yβριδικές δομές δεδομένων, Tries, Δυναμικό Interpolation ψάξιμο, Tο interpolation search tree (IST), Tο ψάξιμο στο interpolation search tree. Union-find, Hashing, Hashing με αλυσίδες, Συζήτηση των υποθέσεων και του χώρου, Hashing με ανοικτή διεύθυνση (open addressing), Extendible Hashing.

Στοιχεία: 23Υ233, Υποχρεωτικό Μάθημα, 4ου Εξαμήνου, Τμήμα Μηχανικών Η/Υ & Πληροφορικής - Πανεπιστήμιο Πατρών

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

Αξιολόγηση για το Μάθημα

Το μάθημα περιλαμβάνει τελική γραπτή εξέταση και εργαστηριακές ασκήσεις (project). 

  • Οι ασκήσεις είναι σε ομάδες από 1-4 άτομα.
  • Η παράδοση των εργαστηριακών ασκήσεων είναι απαραίτητη για τoυς φοιτητές 2ου έτους. Oι φοιτητές μεγαλυτέρων ετών ΔΕΝ ΔΙΝΟΥΝ ΑΣΚΗΣΗ ΚΑΙ ΒΑΘΜΟΛΟΓΟΥΝΤΑΙ 100% ΑΠΟ ΤΟ ΓΡΑΠΤΟ ΤΟΥΣ. Οι εργαστηριακές ασκήσεις έχουν συμμετοχή 40% στην τελική βαθμολογία και μπορούν να παραδοθούν σε ομάδες των 1 έως 4 ατόμων.  Η βαθμολογία της εργασίας έχει ισχύ μόνο για το τρέχον ακ.έτος στο οποίο έχει παραδοθεί.
  • Ο βαθμός της εργασίας μπορεί να κρατηθεί μέχρι το Σεπτέμβριο.
  • ΠΡΕΠΕΙ ΝΑ ΓΡΑΨΕΤΕ ΣΤΗ ΓΡΑΠΤΗ ΕΞΕΤΑΣΗ >=5 για να μετρήσει το project.
  • Απορίες σχετικά με τη θεωρία/φροντιστήριο/εργαστηριακές ασκήσεις υποβάλλονται στο e_class του μαθήματος.

ΥΛΗ ΕΞΕΤΑΣΕΩΝ 2020-2021: από τις Πανεπιστημιακές Σημειώσεις του κ. Τσακαλίδη, ο,τι περιγράφεται ως ύλη στα έγγραφα (attachments). OI ΕΞΕΤΑΣΕΙΣ ΠΡΑΓΜΑΤΟΠΟΙΟΥΝΤΑΙ ΜΕ ΚΛΕΙΣΤΑ ΒΙΒΛΙΑ. 

 

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

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

Σημειώσεις

  • Α. Τσακαλίδης: Δομές Δεδομένων, Εκδόσεις Πανεπιστημίου Πατρών, 2008.
  • Παροράματα στις σημειώσεις (αρχείο .zip)
  • Array Initialization in O(1). Πρόσθετες σημειώσεις είναι διαθέσιμες εδώ (αρχείο pdf)
  • Kurt Melhorn: Data Structures and Algorithms 1: Sorting and Searching, Springer Verlag, 1984. (Link)
  • Mehlhorn, Kurt, Sanders, Peter: Algorithms and Data Structures, Springer Berlin Heidelberg,2008. (Link)

Συμπληρωματικές Αναφορές

  • A.V. Aho, J.E. Hopcroft, J.D. Ullman, The design and analysis of computer algorithms, Addison - Wesley, 1974.
  • A.V. Aho, J.E. Hopcroft, J.D. Ullman, Data Structures and Algorithms, Addison - Wesley, 1983.
  • Th. Cormen, Ch. Leiserson, R. Rivest, Introduction to algorithms, 1st Edition MIT Press 1991, 2nd Edition MIT-Press, 2001.
  • D. Knuth, The Art of Computer Programming: Vol.1 Fundamental Algorithms, Vol. 3 Sorting and Searching.
  • E. Horowitz, S. Sahni, S. Anders, Fundamentals of data structures in C, Computer Science Press, 1993. (Κεντρική βιβλιοθήκη ΠΠ)
  • M.T. Goodrich and Tamassia, Data Structures and Algorithms in Java, Wiley, 1998. (Βιβλιοθήκη Τμήματος)
  • L.J. Garrett, J.F. Korsh, Data structures, algorithms and program style using C, PWS-KENT Publishing Company 1988.(Βιβλιοθήκη Τμήματος)
  • C. van Wyk, Data structures and C programs, Addison-Wesley, 1988.(Βιβλιοθήκη Τμήματος)
  • S. Sahni, Data structures, algorithms and applications in C++, McGraw-Hill, 1998. (Βιβλιοθήκη Τμήματος)
Διδάσκοντες

Διδάσκοντες: Καθηγητής Σιούτας Σ., Αν. καθηγητής Μακρής Χ., Ανδρέας Καναβός

Επικοινωνία: makri@ceid.upatras.gr και sioutas@ceid.upatras.gr

Το zoom link μαθήματος είναι το: https://upatras-gr.zoom.us/j/92396242820?pwd=Tlk1QmNjYks3ZmFJc2UwVEtHTE0yUT09

Ώρες Μαθήματος: Τρίτη 15:00-17:00 στο zoom link μαθήματος KAI

Θεωρία/Φροντιστήριο: Πέμπτη 15:00-17:00  στο zοομ link μαθήματος

Ημερολόγιο