Δομές Δεδομένων και Τεχνικές Προγραμματισμού

Εισαγωγή στις έννοιες: της Αφαίρεσης και Απεικόνισης Δεδομένων της Διεπαφής (τι κάνει) και της Υλοποίησης (πώς το κάνει). του Αφαιρετικού Τύπου Δεδομένων (ΑΤΔ) - Διεπαφή και Υλοποίηση Ορισμός ΑΤΔ, εναλλακτικές υλοποιήσεις με ενότητες της C και εφαρμογές τους. Ειδικότερα αναπτύσσονται οι ΑΤΔ Boolean. Γραμμικές Δομές: Στοίβα, Ουρά, Λίστα Ιεραρχικές Δομές: Δένδρο, Δυαδικό Δένδρο Αναζήτησης, Ισοζυγισμένα Δένδρα. Γραφήματα Υλοποίηση των ανωτέρω ΑΤΔ με πίνακες και συνδεδεμένες δομές (πίνακες και δείκτες). Εισαγωγή στην Αξιολόγηση Αλγορίθμων και στον συμβολισμό Ο( ). Τεχνικές Προγραμματισμού: Αναδρομή, Δοκιμή και Εκσφαλμάτωση Προγραμμάτων.

Στόχοι Μαθήματος

Το μάθημα δίνει έμφαση στην χρήση ΑΤΔ με αναφορές από την καθημερινή μας ζωή (π.χ. διαχείριση ουράς σε τράπεζα, λίστας επαφών στο κινητό μας). Οι εργασίες που δίνονται έχουν 4 στόχους α) την εμπέδωση και εμβάνθυνση στην C (στον προγραμματισμό γενικότερα), β) στην χρήση και ανάπτυξη ΑΤΔ γ) σε τεχνικές προγραμματισμού (ενότητες, δοκιμή, κλπ) και δ) στην σύνδεση του μαθήματος με πραγματικές εφαρμογές. Επιδιώκουμε να καλλιεργήσουμε την διερεύνηση του κόσμου γύρω μας: Μπορώ ως προγραμματιστής να φανταστώ την δομή και την λειτουργία ενός συστήματος που συναντώ στην ζωή μου (π.χ ουρά τράπεζας). Μπορώ να το σχεδιάσω και να αναπτύξω; Μπορώ να το βελτιώσω;    Επίσης να καλλιεργήσουμε την ιδέα ότι ο υπολογιστής είναι το εργαστήριο μας, που κάνουμε όλα τα πειράματά μας. Σε σχέση με άλλες επιστήμες έχουμε το απόλυτο εργαστήριο, από τον αρχάριο μέχρι τον πιο έμπειρο, όλοι έχουμε το ίδιο εργαστήριο. Είναι ένα προνόμιο που μόνο η Πληροφορική Επιστήμη το έχει.  Να εισάγει  - Έννοιες και αρχές που συναντώνται συχνά στην Πληροφορική, όπως Αφαίρεση και Απεικόνιση. - Χρήση ενδιάμεσων δομών (επίπεδα μοντελοποίησης) για την απεικόνιση δεδομένων στον υπολογιστή  - Ιδιαίτερα ουρές, στοίβες, λίστες, δένδρα και γράφους ως Αφηρημένους Τύπους Δεδομένων (ΑΤΔ) και την υλοποίησή τους στην C. - Αλγόριθμους που χρησιμοποιούν τις ανωτέρω δομές. - Χρήσιμες τεχνικές προγραμματισμού (modular programming, ενότητες, αναδρομή) - Πολυπλοκότητα Αλγορίθμων με το συμβολισμό Ο( ) - Έλεγχος (testing), αποσφαλμάτωση (debugging) και τεχνικές ανάπτυξης προγραμμάτων. 

Προαπαιτούμενες Γνώσεις

 -  Βασικά της γλώσσαs C  -  Εισαγωγή στον Προγραμματισμό

Περιεχόμενα

Το μάθημα ξεκινά με μια επισκόπηση της γλώσσας C δίνοντας έμφαση στούς δείκτες για επανάληψη και εμπέδωση γνώσης. Ως παράδειγμα χρήσης δεικτών και structs θα δούμε την δημιουργία και διαχείριση απλής λίστας συνδεδεμένων στοιχείων.  Θα την χρησιμοποιήσουμε μαζί με τους πίνακες για να ορίσουμε τις δομές Στοίβα, Ουρά, Λίστα, Δένδρο και Γράφο.  Παρουσιάζουμε την οργάνωση των προγραμμάτων της C σε modules.c, header.h files και main.c που θα χρησιμοποιήσουμε για να υλοποιήσουμε τις δομές Στοίβα, Ουρά, Λίστα, Δένδρο και Γράφο ως Αφηρημένους Τύπους Δεδομένων (ΑΤΔ).  Επίσης θα δούμε την χρήση της αναδρομής σε αλγορίθμους αναζήτησης και ταξινόμησης στοιχείων.  Θα εισάγουμε τον συμβολισμό Ο() ως μέτρο αξιολόγησης της πολυπλοκότητας αλγορίθμων.