Δομές Δεδομένων 2015-16

ΠεριγραφήΔιαλέξειςΕργασίεςΥλικόΣύνδεσμοι
Δομές Δεδομένων
Εξάμηνο 5ο
Κωδικός Λ08Υ
ECTS 4
Διδακτικές Μονάδες 4
Ώρες Θεωρίας 2
Ώρες Ασκήσεων 1
Ώρες Εργαστηρίου 2
Τομέας Λογισμικού και Ανάπτυξης Εφαρμογών
Διδάσκων Παύλος Εφραιμίδης
Syllabus
Υπολογιστικά μοντέλα. Βασικές έννοιες αλγορίθμων. Πολυπλοκότητα αλγορίθμων. Κλάσεις πολυπλοκότητας. Ασυμπτωτικές προσεγγίσεις και συμβολισμοί. Αναζήτηση και ταξινόμηση. Αναδρομικοί αλγόριθμοι. Δομές Δεδομένων. Στοίβες και ουρές. Συνδεδεμένες λίστες. Βασικές έννοιες δέντρων. Διάσχιση δέντρου. Δυαδικά δέντρα αναζήτησης. Ισοζυγισμένα δέντρα αναζήτησης. Ουρές προτεραιότητας. Κατακερματισμός. Αλγόριθμοι γραφημάτων. Σχεδιασμός και υλοποίηση δομών δεδομένων και αλγορίθμων σε περιβάλλον προγραμματισμού JAVA.
Θεωρία
Θα γνωρίσουμε βασικές έννοιες Αλγορίθμων και Δομών Δεδομένων. Θα χρησιμοποιήσουμε ως εφαρμογή παραδείγματα από πρακτικά υπολογιστικά προβλήματα.
Εργαστήριο
Θα υλοποιήσουμε αλγορίθμους και δομές δεδομένων για υπολογιστικά προβλήματα.
Διδάσκων
Παύλος Εφραιμίδης, Αναπλ. Καθηγητής.
Συνεπικουρούν
Σωτήρης Γυφτόπουλος, Υποψήφιος Διδάκτορας.
Γεώργιος Σταματελάτος, Υποψήφιος Διδάκτορας.
Αντώνιος Δημητριάδης, Υποψήφιος Διδάκτορας.
Ώρες γραφείου
Παύλος (για οποιοδήποτε θέμα): Τετάρτη 09:00 – 12:00.

Ημερομηνία Τύπος Σχόλια Αρχεία
Παρασκευή, 9 Οκτ 2015 Παρουσίαση του μαθήματοςΤο πρόβλημα του ευσταθούς ταιριάσματος DSAlg00 welcome.pdf
Παρασκευή, 16 Οκτ 2015 Ο αλγόριθμος των Gale & Shapley DSAlg01 stable-matching.pdf
Δευτέρα, 19 Οκτ 2015 Φροντιστήριο 1:

Συνοπτική παρουσίαση Java & Eclipse

Εισαγωγή για την εργασία 1 (Moodle μέρος Α)

Παρασκευή, 23 Οκτ 2015 O αλγόριθμος των Gale & Shapley, ανάλυση. Πέντε αντιπροσωπευτικά προβλήματα DSAlg02 five problems.pdf
Δευτέρα, 26 Οκτ 2015 Φροντιστήριο 2: Εργασία 1 (Moodle μέρος Α)
Παρασκευή, 30 Οκτ 2015 Απλές Δομές Δεδομένων. Αναζήτηση και Ταξινόμηση DSAlg02 data structures.pdf
DSAlg02 DS for Gale-Shapley.pdf
Παρασκευή, 06 Νοε 2015 Δεν έγινε μάθημα.
 Παρασκευή, 13 Νοε 2015 Ταξινόμηση. DSAlg02 searching.pdf
DSAlg02 sorting.pdf
Ανάλυση Αλγορίθμων. DSAlg03 analysis.pdf
Heap, Heapsort, Priority Queues. DSAlg02 heap.pdf
Φροντιστήριο: FacilityGame (Εργασία 1).
Γραφήματα, BFS, DFS. DSAlg03 graphs.pdf
Άπληστοι Αλγόριθμοι.
Χρονοπρογραμματισμός Διαστημάτων.
DSAlg04 greedy.pdf
Φροντιστήριο Moodle (Εργασίες 2 και 3)
Minimum Spanning Trees (MST)
Αλγόριθμος Dijkstra
DSAlg04 mst.pdf

DSAlg04 Dijkstra.pdf

Divide and Conquer.
Mergesort.
Closest Pair of Points.
DSAlg05 divide-and-conquer.pdf
Closest Pair of Points.Οδηγίες για την εργασία 3.
ΑΡΓΙΑ
ΑΡΓΙΑ
NP-Complete προβλήματα.Οδηγίες για την εργασία 4.Οδηγίες για τη γραπτή εξέταση. DSAlg08 NP.pdf

DSAlg10 Final Lecture.pdf

  • Εργασία 1: Moodle, part A, προθεσμία: 10/11/2015
  • Εργασία 2: FacilityGame, προθεσμία: 24/11/2015
  • Εργασία 3: Moodle, part B, προθεσμία: 22/12/2015
  • Εργασία 4: GraphSearch, προθεσμία: 19/01/2016