View on GitHub

dituoi_dsa

Data Structures and Algorithms

Δομές Δεδομένων και Αλγόριθμοι

Πανεπιστήμιο Ιωαννίνων - Τμήμα Πληροφορικής και Τηλεπικοινωνιών

Γκόγκος Χρήστος - Άρτα@2020

Τελευταία ενημέρωση: 5/6/2020

Θεωρία

Παρουσιάσεις



Εργαστήριο (C++)

Εργαστήριο 1 - Βασικές έννοιες στη C και στη C++

Δείκτες, δέσμευση-αποδέσμευση μνήμης, πίνακες, πέρασμα παραμέτρων με τιμή και με αναφορά σε συναρτήσεις, δομές - εγγραφές , κλάσεις - αντικείμενα, ανάγνωση - εγγραφή αρχείων.

Εργαστήριο 2 - Εισαγωγή στα templates και στην STL (Standard Template Library)

Templates, STL containers, STL iterators, STL αλγόριθμοι, lambdas.

Εργαστήριο 3 - Αλγόριθμοι αναζήτησης και ταξινόμησης

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

Εργαστήριο 4 - Γραμμικές λίστες

Στατικές λίστες (υλοποίηση στατικής γραμμικής λίστας), συνδεδεμένες λίστες (υλοποίηση απλά συνδεδεμένης λίστας), λίστες της STL (std::array, std::bitset, std::forward_list, std::list, std::vector, std::deque).

Εργαστήριο 5 - Στοίβες και ουρές

Στοίβα (υλοποίηση στοίβας στη C++), Ουρά (υλοποίηση ουράς στη C++), στοίβες και ουρές στην STL (οι adaptors std::stack και std::queue).

Εργαστήριο 6 - Σωροί

Σωροί ελαχίστων (MINHEAPS) και σωροί μεγίστων (MAXHEAPS), η ταξινόμηση heapsort, σωροί μεγίστων και σωροί ελαχίστων στην STL (std::priority_queue).

Εργαστήριο 7 - Κατακερματισμός

Συναρτήσεις κατακερματισμού (hash functions), κατακερματισμός με ανοικτή διευθυνσιοδότηση (γραμμική ανίχνευση), κατακερματισμός με αλυσίδες, δομές κατακερματισμού στην STL (std::unordered_map, std::unordered_set), η std::hash.

Εργαστήριο 8 - Γραφήματα

Αναπαράσταση γραφημάτων (πίνακες γειτνίασης, λίστες γειτνίασης), ανάγνωση δεδομένων γραφήματος από αρχείο, αλγόριθμος του Dijkstra για την εύρεση των συντομότερων διαδρομών από μια κορυφή προς όλες τις άλλες κορυφές του γραφήματος.

Εργαστήριο 9 - Δένδρα

Δυαδικά δένδρα, τρόποι διάσχισης δένδρων (προ-διατακτική, ένδο-διατακτική, μέτα-διατακτική, κατά πλάτος), ισοζυγισμένα δυαδικά δένδρα. Δυαδικά δένδρα αναζήτησης.

Θέματα εξετάσεων