Δομές Δεδομένων 2014-15

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

Ημερομηνία Τύπος Σχόλια Αρχεία
Παρασκευή, 3 Οκτ 2014 Παρουσίαση του μαθήματοςΤο πρόβλημα του ευσταθούς ταιριάσματος DSAlg00 welcome.pdf
Παρασκευή, 10 Οκτ 2014 Ο αλγόριθμος των Gale & Shapley DSAlg01 stable-matching.pdf
Παρασκευή, 17 Οκτ 2014 O αλγόριθμος των Gale & Shapley, ανάλυση. Πέντε αντιπροσωπευτικά προβλήματα DSAlg02 five problems.pdf
Παρασκευή, 24 Οκτ 2014 Απλές Δομές Δεδομένων. Αναζήτηση και Ταξινόμηση DSAlg02 data structures.pdf DSAlg02 DS for Gale-Shapley.pdf
Παρασκευή, 24 Οκτ 2014 Φροντιστήριο FacilityGame (Εργασία 1)
Παρασκευή, 31 Οκτ 2014 Ταξινόμηση. DSAlg02 searching.pdf DSAlg02 sorting.pdf
Παρασκευή, 7 Νοε 2014 Ανάλυση Αλγορίθμων. DSAlg03 analysis.pdf
Παρασκευή, 14 Νοε 2014 Heap, Heapsort, Priority Queues. DSAlg02 heap.pdf
Παρασκευή, 14 Νοε 2014 Φροντιστήριο: FacilityGame (Εργασία 1).
Παρασκευή, 21 Νοε 2014 Γραφήματα, BFS, DFS. DSAlg03 graphs.pdf
Παρασκευή, 28 Νοε 2014 Άπληστοι Αλγόριθμοι.
Χρονοπρογραμματισμός Διαστημάτων.
DSAlg04 greedy.pdf
Παρασκευή, 28 Νοε 2014 Φροντιστήριο Moodle (Εργασίες 2 και 3)
Παρασκευή, 05 Δεκ 2014 Minimum Spanning Trees (MST)
Αλγόριθμος Dijkstra
DSAlg04 mst.pdf 

DSAlg04 Dijkstra.pdf

Παρασκευή, 12 Δεκ 2014 Divide and Conquer.
Mergesort.
Closest Pair of Points.
DSAlg05 divide-and-conquer.pdf
Παρασκευή, 19 Δεκ 2014 Closest Pair of Points.Οδηγίες για την εργασία 3.
Παρασκευή, 26 Δεκ 2014 ΑΡΓΙΑ
Παρασκευή, 02 Ιαν 2015 ΑΡΓΙΑ
Παρασκευή, 09 Ιαν 2015 NP-Complete προβλήματα.Οδηγίες για την εργασία 4.

 

Οδηγίες για τη γραπτή εξέταση.

DSAlg08 NP.pdf 

 

DSAlg10 Final Lecture.pdf

  • Εργασία 1: FacilityGame, προθεσμία: 21/11/2014
  • Εργασία 2: Moodle, part A, προθεσμία: 08/12/2014
  • Εργασία 3: Moodle, part B, προθεσμία: 22/12/2014
  • Εργασία 4: GraphSearch, προθεσμία: 14/01/2015