Στόχοι:
Το μάθημα εξετάζει στις σημαντικότερες δομές δεδομένων και αλγορίθμους, δίνοντας ιδιαίτερη έμφαση στους αλγορίθμους αναζήτησης, συμβολοσειρών. Το μάθημα εστιάζει στην υλοποίηση των δομών δεδομένων και αλγόριθμων με την αντικειμενοστραφή γλώσσα προγραμματισμού Java, την κατανόηση της απόδοσης των αλγορίθμων και τις εφαρμογές που μπορούν να επιλύσουν.
Δεξιότητες:
Ικανότητα ανάλυσης της επίδοσης προηγμένων δομών δεδομένων και αλγορίθμων. Ικανότητα υλοποίησης προηγμένων δομών δεδομένων με την αντικειμενοστρεφή γλώσσα προγραμματισμού Java. Ικανότητα αντίληψης για την καταλληλότητα μία δομής δεδομένων σε κάποιο πρόβλημα. Ικανότητα προσαρμογής μία δομής δεδομένων σε κάποιο πρόβλημα. Ικανότητα συνδυασμού δομών δεδομένων για την επίλυση προβλημάτων.
Προαπαιτήσεις:
Πτυχιούχοι με υπόβαθρο Πληροφορικής. Γνώσεις βασικών δομών δεδομένων (από αντίστοιχο προπτυχιακό μάθημα). Γνώσεις αντικειμενοστρεφούς προγραμματισμού με Java.
Περιεχόμενο μαθήματος:
Οι Δομές Δεδομένων και Αλγόριθμοι είναι ένας από τους σημαντικότερους και ιστορικότερους κλάδους της Επιστήμης της Πληροφορικής, με συνεχή εξέλιξη παρέχοντας λύσεις σε θεμελιώδη προβλήματα ταξινόμησης, οργάνωσης, διαχείρισης και αναζήτησης πληροφορίας. Ταυτόχρονα τα τελευταία χρόνια παρατηρείται τεράστια ανάπτυξη του Διαδικτύου για την υποστήριξη μιας μεγάλης γκάμας δραστηριοτήτων. Το Διαδίκτυο προωθείται ως μέσο καθολικής υποστήριξης ανθρώπινων δραστηριοτήτων. Η παροχή και διακίνηση πληροφορίας στο Διαδίκτυο οδήγησε στην ανάπτυξη των Δικτυοκεντρικών Πληροφοριακών Συστημάτων. Είναι μεγίστης σημασίας η αποτελεσματική αναζήτηση αυτής της πληροφορίας και κατά συνέπεια οι αλγόριθμοι αναζήτησης για τον εντοπισμό στοιχείων σε μεγάλο όγκο πληροφοριών είναι θεμελιώδους σημασίας. Επίσης, οι αλγόριθμοι γραφημάτων μας επιτρέπουν να αντιμετωπίσουν πολλά από τα δύσκολα και σημαντικά προβλήματα, όπως Communication, circuit, mechanical, financial stock, transportation, internet, game, social relationship, neural network, protein, chemical compound. Τέλος οι αλγόριθμοι συμβολοσειρών αντιμετωπίζουν το πρόβλημα του ταιριάσματος προτύπου, όπως στα προγράμματα κειμενογράφων, την αναζήτηση λέξεων στα περιεχόμενα μιας ιστοσελίδας ή σε μια ακολουθία DNA.
Ενότητες:
Fundamentals: Basic Programming Model, Data Abstraction, Bag, Stacks, Queues, Case Study: Union-find
Ταξινόμηση: Βασικοί αλγόριθμοι ταξινόμησης, Mergesort, Quicksort (υλοποιήσεις, βελτιώσεις, διπλά κλειδιά, 3-way partitioning, Bentley-McIlroy quicksort, Dual-pivot quicksort), system sort in Java, Priority Queues, Sorting various types of data (immutable keys, Alternate orderings, Items with multiple keys, Priority queues with comparators), Εφαρμογές
Αναζήτηση: Πίνακες συμβόλων (Symbol tables). Εφαρμογές πινάκων συμβόλων (sets, dictionary clients, indexing clients). Δυαδικά δένδρα αναζήτησης. Ισοζυγισμένα δένδρα. 2-3 δένδρα, Κόκκινα-μαύρα δένδρα. B-Δένδρα, Hashing.
Συμβολοσειρές: Sorting Strings (key-indexed counting, LSD string sort, MSD string sort, 3-way string quicksort, suffix arrays), String Symbol Tables, Substring Search (brute force, Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp), Data Compression, applications)
Γραφήματα. Graph API. Συνεκτικότητα γραφήματος και διάσχιση γραφήματος (DFS, BFS), εφαρμογές (Facebook, Kevin Bacon numbers). Συνιστώσες. Symbol graph (degree of separation between two individuals in a social network). Προσανατολισμένα γραφήματα, Εφαρμογές (transportation, web, food, WordNet, scheduling, financial stock, cell phone, infectious disease, game, citation, object graph, inheritance, control flow). Ισχυρά συνδεδεμένες συνιστώσες. Τοπολογική διάταξη. Κύκλοι, Τομές γραφήματος.
Προτεινόμενη βιβλιογραφία:
Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition, Addison-Wesley, 2011
T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Εισαγωγή στους Αλγορίθμους, ελληνική έκδοση, Πανεπιστημιακές Εκδόσεις Κρήτης, 2012
J. Kleinberg and E. Tardos, Σχεδιασμός Αλγορίθμων, ελληνική έκδοση, Εκδόσεις Κλειδάριθμος, 2008
Michael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, Wiley
Mark Allen Weiss, Data Structures and Problem Solving Using Java (Fourth Edition), Addison-Wesley, 2010
Mark Allen Weiss, Data Structures and Algorithm Analysis in Java (Third Edition), Addison-Wesley, 2012
Kurt Mehlhorn, Peter Sanders, Algorithms and Data Structures: The Basic Toolbox, Springer Verlag, 2008
Επιλεγμένα άρθρα διαφορετικά κάθε έτος από τις περιοχές Searching, Graphs, Strings
Μέθοδοι αξιολόγησης:
(50%) από ατομικές εργασίες: (5) προγραμματιστικές εργασίες και (1) ερευνητική εργασία (1 εργασία ανά 2 βδομάδες)
(50%) τελική γραπτή εξέταση
Ιστοσελίδα μαθήματος:
http://compus.uom.gr/MINF168/
.jpg)
