Περιγραφή μαθήματος

Κωδικός μαθήματος: ΜΥΥ303

Εβδομαδιαίες ώρες διδασκαλίας: 4,0,2

Εξάμηνο σπουδών: 3ο

Διδακτικές Μονάδες: 5

Μονάδες ECTS: 6

Ιστοσελίδα Μαθήματος: http://ecourse.uoi.gr/enrol/index.php?id=704

Προσφερόμενο: Ακαδημαϊκό έτος 2024-2025

Προαπαιτούμενα:

Περιεχόμενο:

Βασικές έννοιες: Αλγόριθμοι, αφηρημένοι τύποι δεδομένων.

Πίνακες, λίστες και αναδρομή: Πίνακες. Συνδεδεμένες λίστες, απλή, διπλή και κυκλική λίστα, επεξεργασία λιστών. Κατανομή μνήμης, σύνθετες δομές δεδομένων, πολυδιάστατοι πίνακες. Αναδρομή, γραμμική αναδρομή, δυαδική και πολλαπλή αναδρομή. Επεξεργασία πινάκων και λιστών με αναδρομή.

Γραφήματα και δένδρα: Ορισμός και αναπαράσταση γραφήματος, μήτρα γειτνίασης, λίστες γειτνίασης. Διάσχιση γραφήματος, αναζήτηση με προτεραιότητα εύρους, αναζήτηση με προτεραιότητα βάθους. Δένδρα, αναπαραστάσεις δένδρων. Δυαδικά δένδρα, μαθηματικές ιδιότητες δυαδικών δένδρων. Διάσχιση δένδρου. Αναδρομικοί αλγόριθμοι δυαδικού δένδρου.

Ανάλυση αλγορίθμων: Μαθηματική και εμπειρική ανάλυση αλγορίθμων. Αύξηση συναρτήσεων και ανάλυση αλγορίθμων. Ασυμπτωτικοί συμβολισμοί, αναλλοίωτες συνθήκες, επαγωγή. Αναδρομικές σχέσεις. Χρήσιμοι μαθηματικοί τύποι και ορισμοί.

Συλλογές, στοίβες και ουρές: Συλλογές στοιχείων. Στοίβα ώθησης προς τα κάτω. Ουρά FIFO. Γενικευμένες ουρές.

Ουρές προτεραιότητας: Στοιχειώδεις υλοποιήσεις. Δυαδικός σωρός. Ταξινόμηση με σωρό, αλγόριθμος heapsort. d-σωρός. Εφαρμογές.

Λεξικά και δένδρα αναζήτησης: Διατεταγμένα και μη διατεταγμένα λεξικά. Στοιχειώδεις υλοποιήσεις με πίνακες και λίστες. Δυαδικά δένδρα αναζήτησης. Τυχαία κατασκευασμένα δυαδικά δένδρα αναζήτησης.

Ισορροπημένα δένδρα αναζήτησης: Τυχαιοποιημένα δένδρα, αρθρωτά δένδρα, δένδρα AVL, (a,b) δένδρα, κοκκινόμαυρα δένδρα, λίστες παράλειψης.

Κατακερματισμός: Συναρτήσεις κατακερματισμού. Συγκρούσεις, χωριστή αλυσίδωση, ανοικτή διευθυνσιοδότηση. Καθολικές οικογένειες συναρτήσεων κατακερματισμού. Πλήρης κατακερματισμός.

Επεξεργασία κειμένου: Τυπικά tries και συμπιεσμένα tries. Δένδρα και πίνακες καταλήξεων.

Ένωση ξένων μεταξύ τους συνόλων: Αναπαράσταση με λίστες. Αναπαράσταση με πίνακα. Δομή γρήγορης εύρεσης. Δομή γρήγορης ένωσης. Σταθμισμένη γρήγορη ένωση. Συμπίεση διαδρομής.

Διαχείριση μνήμης: Ιεραρχία μνήμης (κρυφή, κύρια και εξωτερική μνήμη). Κατανομή μνήμης στη Java. Β-δένδρα, επεκτάσιμος κατακερματισμός.

Παρατηρήσεις: