Δομές Δεδομένων και Τεχνικές Προγραμματισμού
Ιωάννης Κοτρώνης
Το μάθημα ξεκινά με μια επισκόπηση της γλώσσας C δίνοντας έμφαση στούς δείκτες για επανάληψη και εμπέδωση γνώσης. Ως παράδειγμα χρήσης δεικτών και structs θα δούμε την δημιουργία και διαχείριση απλής λίστας συνδεδεμένων στοιχείων.
Θα την χρησιμοποιήσουμε μαζί με τους πίνακες για να ορίσουμε τις δομές Στοίβα, Ουρά, Λίστα, Δένδρο και Γράφο.
Παρουσιάζουμε την οργάνωση των προγραμμάτων της C σε modules.c, header.h files και main.c που θα χρησιμοποιήσουμε για να υλοποιήσουμε τις δομές Στοίβα, Ουρά, Λίστα, Δένδρο και Γράφο ως Αφηρημένους Τύπους Δεδομένων (ΑΤΔ).
Επίσης θα δούμε την χρήση της αναδρομής σε αλγορίθμους αναζήτησης και ταξινόμησης στοιχείων.
Θα εισάγουμε τον συμβολισμό Ο() ως μέτρο αξιολόγησης της πολυπλοκότητας αλγορίθμων.
Το μάθημα ξεκινά με μια επισκόπηση της γλώσσας C δίνοντας έμφαση στούς δείκτες για επανάληψη και εμπέδωση γνώσης. Ως παράδειγμα χρήσης δεικτών και structs θα δούμε την δημιουργία και διαχείριση απλής λίστας συνδεδεμένων στοιχείων.
Θα την χρησιμοποιήσουμε μαζί με τους πίνακες για να ορίσουμε τις δομές Στοίβα, Ουρά, Λίστα, Δένδρο και Γράφο.
Παρουσιάζουμε την οργάνωση των προγραμμάτων της C σε modules.c, header.h files και main.c που θα χρησιμοποιήσουμε για να υλοποιήσουμε τις δομές Στοίβα, Ουρά, Λίστα, Δένδρο και Γράφο ως Αφηρημένους Τύπους Δεδομένων (ΑΤΔ).
Επίσης θα δούμε την χρήση της αναδρομής σε αλγορίθμους αναζήτησης και ταξινόμησης στοιχείων.
Θα εισάγουμε τον συμβολισμό Ο() ως μέτρο αξιολόγησης της πολυπλοκότητας αλγορίθμων.
Το μάθημα ξεκινά με μια επισκόπηση της γλώσσας C δίνοντας έμφαση στούς δείκτες για επανάληψη και εμπέδωση γνώσης. Ως παράδειγμα χρήσης δεικτών και structs θα δούμε την δημιουργία και διαχείριση απλής λίστας συνδεδεμένων στοιχείων.
Θα την χρησιμοποιήσουμε μαζί με τους πίνακες για να ορίσουμε τις δομές Στοίβα, Ουρά, Λίστα, Δένδρο και Γράφο.
Παρουσιάζουμε την οργάνωση των προγραμμάτων της C σε modules.c, header.h files και main.c που θα χρησιμοποιήσουμε για να υλοποιήσουμε τις δομές Στοίβα, Ουρά, Λίστα, Δένδρο και Γράφο ως Αφηρημένους Τύπους Δεδομένων (ΑΤΔ).
Επίσης θα δούμε την χρήση της αναδρομής σε αλγορίθμους αναζήτησης και ταξινόμησης στοιχείων.
Θα εισάγουμε τον συμβολισμό Ο() ως μέτρο αξιολόγησης της πολυπλοκότητας αλγορίθμων.
Περίγραμμα
Περιεχόμενο μαθήματος
Το μάθημα ξεκινά με μια επισκόπηση της γλώσσας C δίνοντας έμφαση στούς δείκτες για επανάληψη και εμπέδωση γνώσης. Ως παράδειγμα χρήσης δεικτών και structs θα δούμε την δημιουργία και διαχείριση απλής λίστας συνδεδεμένων στοιχείων.
Θα την χρησιμοποιήσουμε μαζί με τους πίνακες για να ορίσουμε τις δομές Στοίβα, Ουρά, Λίστα, Δένδρο και Γράφο.
Παρουσιάζουμε την οργάνωση των προγραμμάτων της C σε modules.c, header.h files και main.c που θα χρησιμοποιήσουμε για να υλοποιήσουμε τις δομές Στοίβα, Ουρά, Λίστα, Δένδρο και Γράφο ως Αφηρημένους Τύπους Δεδομένων (ΑΤΔ).
Επίσης θα δούμε την χρήση της αναδρομής σε αλγορίθμους αναζήτησης και ταξινόμησης στοιχείων.
Θα εισάγουμε τον συμβολισμό Ο() ως μέτρο αξιολόγησης της πολυπλοκότητας αλγορίθμων.
Μαθησιακοί στόχοι
Το μάθημα δίνει έμφαση στην χρήση ΑΤΔ με αναφορές από την καθημερινή μας ζωή (π.χ. διαχείριση ουράς σε τράπεζα, λίστας επαφών στο κινητό μας). Οι εργασίες που δίνονται έχουν 4 στόχους α) την εμπέδωση και εμβάνθυνση στην C (στον προγραμματισμό γενικότερα), β) στην χρήση και ανάπτυξη ΑΤΔ γ) σε τεχνικές προγραμματισμού (ενότητες, δοκιμή, κλπ) και δ) στην σύνδεση του μαθήματος με πραγματικές εφαρμογές.
Επιδιώκουμε να καλλιεργήσουμε την διερεύνηση του κόσμου γύρω μας: Μπορώ ως προγραμματιστής να φανταστώ την δομή και την λειτουργία ενός συστήματος που συναντώ στην ζωή μου (π.χ ουρά τράπεζας). Μπορώ να το σχεδιάσω και να αναπτύξω; Μπορώ να το βελτιώσω;
Επίσης να καλλιεργήσουμε την ιδέα ότι ο υπολογιστής είναι το εργαστήριο μας, που κάνουμε όλα τα πειράματά μας. Σε σχέση με άλλες επιστήμες έχουμε το απόλυτο εργαστήριο, από τον αρχάριο μέχρι τον πιο έμπειρο, όλοι έχουμε το ίδιο εργαστήριο. Είναι ένα προνόμιο που μόνο η Πληροφορική Επιστήμη το έχει.
Να εισάγει
- Έννοιες και αρχές που συναντώνται συχνά στην Πληροφορική, όπως Αφαίρεση και Απεικόνιση.
- Χρήση ενδιάμεσων δομών (επίπεδα μοντελοποίησης) για την απεικόνιση δεδομένων στον υπολογιστή
- Ιδιαίτερα ουρές, στοίβες, λίστες, δένδρα και γράφους ως Αφηρημένους Τύπους Δεδομένων (ΑΤΔ) και την υλοποίησή τους στην C.
- Αλγόριθμους που χρησιμοποιούν τις ανωτέρω δομές.
- Χρήσιμες τεχνικές προγραμματισμού (modular programming, ενότητες, αναδρομή)
- Πολυπλοκότητα Αλγορίθμων με το συμβολισμό Ο( )
- Έλεγχος (testing), αποσφαλμάτωση (debugging) και τεχνικές ανάπτυξης προγραμμάτων.
Βιβλιογραφία
- Δομές Δεδομένων με C, Νικόλαος Μισυρλής
- ΓΕΩΡΓΑΚΟΠΟΥΛΟΣ ΦΡ. ΓΕΩΡΓΙΟΣ ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ, Έννοιες, τεχνικές και αλγόριθμοι, Πανεπιστημιακές Εκδόσεις Κρήτης
- Data Structures, Algorithms & Software Principles in C, Thomas A. Standish, Addison Wesley
2Data Structures and Algorithm Analysis in C. Mark Allen Weiss
Προαπαιτούμενα
- Βασικά της γλώσσαs C
- Εισαγωγή στον Προγραμματισμό
Το μάθημα ξεκινά με μια επισκόπηση της γλώσσας C δίνοντας έμφαση στούς δείκτες για επανάληψη και εμπέδωση γνώσης. Ως παράδειγμα χρήσης δεικτών και structs θα δούμε την δημιουργία και διαχείριση απλής λίστας συνδεδεμένων στοιχείων.
Θα την χρησιμοποιήσουμε μαζί με τους πίνακες για να ορίσουμε τις δομές Στοίβα, Ουρά, Λίστα, Δένδρο και Γράφο.
Παρουσιάζουμε την οργάνωση των προγραμμάτων της C σε modules.c, header.h files και main.c που θα χρησιμοποιήσουμε για να υλοποιήσουμε τις δομές Στοίβα, Ουρά, Λίστα, Δένδρο και Γράφο ως Αφηρημένους Τύπους Δεδομένων (ΑΤΔ).
Επίσης θα δούμε την χρήση της αναδρομής σε αλγορίθμους αναζήτησης και ταξινόμησης στοιχείων.
Θα εισάγουμε τον συμβολισμό Ο() ως μέτρο αξιολόγησης της πολυπλοκότητας αλγορίθμων.
Το μάθημα δίνει έμφαση στην χρήση ΑΤΔ με αναφορές από την καθημερινή μας ζωή (π.χ. διαχείριση ουράς σε τράπεζα, λίστας επαφών στο κινητό μας). Οι εργασίες που δίνονται έχουν 4 στόχους α) την εμπέδωση και εμβάνθυνση στην C (στον προγραμματισμό γενικότερα), β) στην χρήση και ανάπτυξη ΑΤΔ γ) σε τεχνικές προγραμματισμού (ενότητες, δοκιμή, κλπ) και δ) στην σύνδεση του μαθήματος με πραγματικές εφαρμογές.
Επιδιώκουμε να καλλιεργήσουμε την διερεύνηση του κόσμου γύρω μας: Μπορώ ως προγραμματιστής να φανταστώ την δομή και την λειτουργία ενός συστήματος που συναντώ στην ζωή μου (π.χ ουρά τράπεζας). Μπορώ να το σχεδιάσω και να αναπτύξω; Μπορώ να το βελτιώσω;
Επίσης να καλλιεργήσουμε την ιδέα ότι ο υπολογιστής είναι το εργαστήριο μας, που κάνουμε όλα τα πειράματά μας. Σε σχέση με άλλες επιστήμες έχουμε το απόλυτο εργαστήριο, από τον αρχάριο μέχρι τον πιο έμπειρο, όλοι έχουμε το ίδιο εργαστήριο. Είναι ένα προνόμιο που μόνο η Πληροφορική Επιστήμη το έχει.
Να εισάγει
- Έννοιες και αρχές που συναντώνται συχνά στην Πληροφορική, όπως Αφαίρεση και Απεικόνιση.
- Χρήση ενδιάμεσων δομών (επίπεδα μοντελοποίησης) για την απεικόνιση δεδομένων στον υπολογιστή
- Ιδιαίτερα ουρές, στοίβες, λίστες, δένδρα και γράφους ως Αφηρημένους Τύπους Δεδομένων (ΑΤΔ) και την υλοποίησή τους στην C.
- Αλγόριθμους που χρησιμοποιούν τις ανωτέρω δομές.
- Χρήσιμες τεχνικές προγραμματισμού (modular programming, ενότητες, αναδρομή)
- Πολυπλοκότητα Αλγορίθμων με το συμβολισμό Ο( )
- Έλεγχος (testing), αποσφαλμάτωση (debugging) και τεχνικές ανάπτυξης προγραμμάτων.
- Δομές Δεδομένων με C, Νικόλαος Μισυρλής
- ΓΕΩΡΓΑΚΟΠΟΥΛΟΣ ΦΡ. ΓΕΩΡΓΙΟΣ ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ, Έννοιες, τεχνικές και αλγόριθμοι, Πανεπιστημιακές Εκδόσεις Κρήτης
- Data Structures, Algorithms & Software Principles in C, Thomas A. Standish, Addison Wesley
2Data Structures and Algorithm Analysis in C. Mark Allen Weiss
- Βασικά της γλώσσαs C
- Εισαγωγή στον Προγραμματισμό
Εισάγει τις έννοιες της αφαίρεσης και της απεικόνισης σε γλώσσες προγραμματισμού, στους Αφαιρετικούς Τύπους Δεδομένων (ΑΤΔ) και τον τρόπο που υλοποιούνται στην C με ενότητες, με παράδειγμα τον ΑΤΔ Boolean. Εισαγωγή στην Αξιολόγηση Αλγορίθμων με τον συμβολισμό Ο( ).
Λέξεις κλειδιά: Αφαίρεση, Απεικόνιση, ΑΤΔ, Ενότητες στην C, Αξιολόγηση Αλγορίθμων.
Ορισμός, σχεδιαστικές επιλογές με πίνακα, υλοποίηση με ενότητες με Μερική και Ολική Απόκρυψη. Εφαρμογές μετατροπής ενδο-διατεταγμένης παράστασης σε μετα-διατεταγμένη και υπολογισμός αποτελέσματος.
Λέξεις κλειδιά: Στοίβα, Μερική Απόκρυψη, Ολική Απόκρυψη, μετα-διατεταγμένη παράσταση.
Ορισμός, σχεδιαστικές επιλογές με πίνακα, υλοποίηση με ενότητες με Μερική και Ολική Απόκρυψη. Εφαρμογή Ουράς Αναμονής σε Ταμείο Τράπεζας.
Λέξεις κλειδιά: Ουρά, Μερική Απόκρυψη, Ολική Απόκρυψη.
Ορισμός, σχεδιαστικές επιλογές με πίνακα και με δυναμικές συνδεδεμένες δομές, μονά-διπλά συνδεδεμένες, με κεφαλή, κυκλικές, με δείκτη τέλους, ταξινομημένες. Σχεδιαστική επιλογή με στατικές συνδεδεμένες δομές με πίνακα.
Λέξεις κλειδιά: Λίστα, συνδεδεμένες δομές.
Πλεονεκτήματα-μειονεκτήματα των τριών σχεδιαστικών επιλογών, κριτήρια επιλογής σχεδιασμού, τεχνικές ελέγχου προγραμμάτων, ανάπτυξη ενοτήτων, τεχνική αναδρομής.
Λέξεις κλειδιά: Σχεδιαστικές επιλογές, ενότητες, έλεγχος προγραμμάτων, αναδρομή.
Ορισμός, Ιδιότητες Δένδρου και Δυαδικού Δένδρου. Επικέντρωση στο Δυαδικό Δένδρο Αναζήτησης, εναλλακτικές υλοποιήσεις. Εφαρμογή Δένδρου Huffman. AVL δένδρα.
Λέξεις κλειδιά: Δένδρο, Δυαδικό Δένδρο, Δυαδικό Δένδρο Αναζήτησης, Δένδρα Huffman, AVL.
Ορισμός, σχεδιασμός και υλοποίηση με πίνακα, με λίστες κορυφών και λίστες ακμών. Αναζήτηση κατά βάθος και κατά πλάτος, Δένδρα επικάλυψης. Πίνακες Μετάβασης και συντομότερο μονοπάτι.
Λέξεις κλειδιά: Γράφημα, κατά βάθος, κατά πλάτος, δένδρα επικάλυψης, πίνακες μετάβασης, συντομότερο μονοπάτι.
Ασκήσεις για όλες τις ενότητες του μαθήματος.
Ανοικτό Ακαδ. Μάθημα
Αρ. Επισκέψεων : 0
Αρ. Προβολών : 0
Ημερολόγιο
Ανακοινώσεις
- - Δεν υπάρχουν ανακοινώσεις -
