Λίστες και ταξινόμηση

Overview

Goals

Στόχοι της εργασίας είναι η υλοποίηση διπλά συνδεδεμένων λιστών και αλγορίθμων ταξινόμησης σε γλώσσα C. Επίσης, η συγκριτική μέτρηση της επίδοσης των εξεταζόμενων αλγορίθμων.

Learning Objectives

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

Context

Το μάθημα παρέχει στους φοιτητές μία εισαγωγή στις βασικές δομές δεδομένων και στις κύριες τεχνικές ταξινομήσεως και αναζητήσεως. Τα καλυπτόμενα θέματα περιλαμβάνουν: Εισαγωγή στις ασυμπτωτικές εκτιμήσεις, επιδόσεις χειρότερης, μέσης και επιμερισμένης περιπτώσεως. Βασικές δομές δεδομένων, όπως Πίνακες, Λίστες, Στοίβες, ουρές FIFO, Διπλοουρές, Στατικά – Δυναμικά Δένδρα και η διελεύσεις τους. Δυαδικό Ψάξιμο και Εισαγωγή και Ανάλυση των συγκριτικών αλγορίθμων ταξινομήσεως (Εισαγωγής, Επιλογής, Φυσαλίδας, Αναμικτήρα, Ταχυδιάταξη, Σωρού, Συγχωνεύσεως), και των με διανομή αλγορίθμων ταξινομήσεως (Κάδου, Σημαντικότερου Ψηφίου και Λιγότερου Σημαντικού Ψηφίου). Επιλογή και Στατιστικές Τάξεως. Διατεταγμένα Λεξικά, όπως Απλά και Ισοζυγισμένα Δένδρα (AVL, (a,b), Ερυθρόμαυρα) και Ψηφιακά Δένδρα (Trie, PATRICIA). Ένωση-Εύρεση σε Ξένα μεταξύ τους Σύνολα. Εισαγωγή στον Κατακερματισμό και στα Αδιάτακτα Λεξικά, όπως Κατακερματισμός με Αλυσίδες, Με Ανοικτή Διευθυνσιοδότηση, Ανακατακερματισμός και Επεκτάσιμος Κατακερματισμός. Λίστες Αναπηδήσεως (SkipLists), Εξαρθρωμένα Δένδρα (SplayTrees), Treaps, Ουρές Προτεραιότητας (Δυωνυμική, Fibonacci).