Εργαστήριο Σχεδίασης και Ανάλυσης Αλγορίθμων (Design and Analysis of Algorithms Lab)

Υπεύθυνος Εργαστηρίου:

Χ. Τζώρτζης tjortjis (at) cs.uoi.gr

Επιστ. Υπευθ. Εργαστηρίου:

Σ.Δ. Νικολόπουλος stavros (at) cs.uoi.gr

Μεταπτυχιακοί Βοηθοί :

Ν. Βρεττός/Μ. Χρόνη - Μ. Φαρμάκη - Α. Φυλάκης– I. Χιόνης

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

4-02

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

4ο

Ιστοσελίδα εργαστηρίου:

http://www.cs.uoi.gr/~tjortjis/4-02.htm

 

Περιγραφή

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

Η LEDA είναι μια πλατφόρμα ανάπτυξης λογισμικού (υλοποιημένη ως βιβλιοθήκη της C++) για συνδυαστικούς και γεωμετρικούς αλγόριθμους, η οποία έχει πλέον καθιερωθεί τόσο στην ακαδημαϊκή κοινότητα όσο και στη βιομηχανία ως μια από τις πιο σημαντικές βιβλιοθήκες αλγόριθμων, λόγω της θεωρητικής θεμελίωσης των υλοποιήσεων της αλλά και την ευκολία χρήσης της. Η LEDA φιλοδοξεί να αποτελέσει τον ενδιάμεσο κρίκο ανάμεσα στο σχεδιασμό περίπλοκων συνδυαστικών και γεωμετρικών αλγόριθμων, και τον προγραμματισμό αποδοτικών υλοποιήσεων γι' αυτούς.

 

Γενικά στοιχεία για το εργαστήριο

 

·       Εργαστήριο: Τετάρτη 11.00-13.00 στις αίθουσες ΠΕΠ1, ΠΕΠ2 και ΠΕΛΣ

Έναρξη 14/03/12.

 

Το εργαστήριο είναι υποχρεωτικό για τους φοιτητές του 2ου έτους και προαιρετικό για τους υπόλοιπους.

Θα διεξάγεται σε ομάδες των 2. Δηλώσεις ομάδων θα γίνουν στη διάρκεια του πρώτου εργαστηρίου.

Φοιτητές που θέλουν να κατοχυρώσουν το βαθμό από τα περυσινά εργαστήρια θα πρέπει να ενημερώσουν το διδάσκοντα στο tjortjis (at) cs.uoi.gr μέχρι την αρχή του πρώτου εργαστηρίου.

 

 

Αξιολόγηση Μαθήματος Σχεδίασης και Ανάλυσης Αλγορίθμων

 

Ο τελικός βαθμός του μαθήματος της Σχεδίασης και Ανάλυσης Αλγορίθμων, για όσους παρακολουθήσουν το εργαστήριο, προκύπτει από τον τύπο:

1/5*[ΒΑΘΜΟΣ ΕΡΓΑΣΤΗΡΙΟΥ] + 4/5*[ΒΑΘΜΟΣ ΕΞΕΤΑΣΗΣ ΜΑΘΗΜΑΤΟΣ]

υπό τις εξής προϋποθέσεις:

[1] Ο βαθμός της τελικής εξέτασης είναι τουλάχιστον 5.
[2] Ο βαθμός του εργαστηρίου είναι τουλάχιστον 5.
[3] O αριθμός απουσιών από το εργαστήριο είναι το πολύ 1.

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

Ως προς το βαθμό του εργαστηρίου, αυτός θα προκύψει κατά 30% από τα εργαστήρια και κατά 70% από την τελική εξέταση του εργαστηρίου:

ΒΑΘΜΟΣ ΕΡΓΑΣΤΗΡΙΟΥ = 0.3*[Μ.O. ΕΒΔΟΜΑΔΙΑΙΩΝ ΑΣΚΗΣΕΩΝ] + 0.7*[ΒΑΘΜΟΣ ΕΞΕΤΑΣΗΣ]

      

1ο ΕΡΓΑΣΤΗΡΙΟ: Εισαγωγή στη LEDA
-- Ενεργοποίηση λογαριασμών και ένα αρχικό πρόγραμμα σε LEDA.

Εκφώνηση, Makefile1, google-white.txt, word_count.c

Εναλλακτικό Makefile

 

2ο ΕΡΓΑΣΤΗΡΙΟ: Βασικοί Τύποι Δεδομένων της LEDA
-- Ο τύπος της στοίβας και ο τύπος string.
-- Υλοποίηση υπολογιστή αριθμητικών εκφράσεων.

Εκφώνηση, LEDA_strings, calc-template.c, string-input.c.

 

3ο ΕΡΓΑΣΤΗΡΙΟ: Αλγόριθμοι Ταξινόμησης
-- Διαχείριση πινάκων
-- Υλοποίηση αλγορίθμων ταξινόμησης

Εκφώνηση, LEDA_arrays, LEDA_random_source, lab3_template.c

 

4ο ΕΡΓΑΣΤΗΡΙΟ: Διαχείριση Γραφημάτων
--Εισαγωγή και διαχείριση γραφήματος
--Τοπολογική ταξινόμηση

Εκφώνηση, LEDA_queues, LEDA_graph, LEDA_node+edge_array, lab4_template.c

 

5ο ΕΡΓΑΣΤΗΡΙΟ: Tοπολογική Ταξινόμηση
--Δυναμική διαχείριση γραφημάτων
--Υλοποίηση αλγόριθμου τοπολογικής ταξινόμησης

Εκφώνηση, lab5_template.c

 

6ο ΕΡΓΑΣΤΗΡΙΟ: Αλγόριθμοι Αναζήτησης σε γραφήματα Ι
-- Γεννητικά Δέντρα
-- Υλοποίηση Διάσχισης κατά Πλάτος – BFS

Εκφώνηση, lab6_template, LEDA_d_array, LEDA_lists

 

7ο ΕΡΓΑΣΤΗΡΙΟ: Αλγόριθμοι Αναζήτησης σε γραφήματα ΙI
-- Γεννητικά Δέντρα
-- Υλοποίηση Διάσχισης κατά Βάθος - DFS

Εκφώνηση, lab7_template

 

8ο ΕΡΓΑΣΤΗΡΙΟ: Αλγόριθμοι σε γραφήματα
-- Συνεκτικές Συνιστώσες
-- Υλοποίηση μη-κατευθυνόμενης Διάσχισης κατά Πλάτος - DFS

Εκφώνηση, lab8_template

 

Εξέταση Εργαστηρίου

Η εξέταση του εργαστηρίου θα γίνει την Τετάρτη 30/5/2012 στις 11 π.μ. στα εργαστήρια ΠΕΠ-Ι & ΙΙ και θα είναι ατομική. Η λίστα των Α.Μ. των φοιτητών που έχουν δικαίωμα στην εξέταση είναι εδώ.

 

Βαθμοί Εργαστηρίου

Οι βαθμοί του εργαστηρίου είναι εδώ.

 

Χρήσιμο Υλικό

  :p>