mycourses .ntua.gr
Αλγόριθμοι και Πολυπλοκότητα

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

 

Περιγραφή

ΑΝΑΚΟΙΝΩΣΗ

ΕΞΕΤΑΣΗ ΤΟΥ ΜΑΘΗΜΑΤΟΣ «Αλγόριθμοι και Πολυπλοκότητα»

Μάθημα: Αλγόριθμοι και Πολυπλοκότητα
Εξάμηνο: 7ο
Διδάσκων: Α. Συμβώνης
Εξέταση: Επαναληπτική, Σεπτέμβριος 2021
Τρόπος εξέτασης: Εξ αποστάσεως
Ημερομηνία εξέτασης: Δευτέρα 20/9/21 @ 10:00
Μέθοδος εξέτασης: Γραπτή εξέταση στο σπίτι (take home exam) (σύμφωνα με την από 29/5/2020 απόφαση της Συγκλήτου του ΕΜΠ).
Εύρος Βαθμολογίας: Δεκαδική κλίμακα βαθμολογίας (0-10)

***Προϋποθέσεις συμμετοχής στην εξέταση

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

  2. ******Απαιτείται εγγραφή στην τάξη/ομάδα «Αλγόριθμοι και Πολυπλοκότητα – Σεπτ. 2021» που έχει δημιουργηθεί στην εφαρμογή Microsoft Teams έως την Κυριακή 19 Σεπτεμβρίου, 23:59 Η εγγραφή γίνεται ακολουθώντας τον  σύνδεσμο

    (Στην πραγματικότητα, αυτό που κάνετε είναι να στείλετε ένα αίτημα για να γίνετε μέλη της συγκεκριμένης ομάδας το οποίο εγώ θα εγκρίνω. Με τον τρόπο αυτό δηλώνετε συμμετοχή στο διαγώνισμα μέσω της πλατφόρμας Teams.)
  3. Η συμμετοχή κάθε σπουδαστή/στριας σε αυτή την εξεταστική διαδικασία αποτελεί αυτομάτως Υπεύθυνη Δήλωση ότι «συμμετέχει προσωπικά ο/η συγκεκριμένος/η σπουδαστής/στρια χωρίς καμία εξωτερική βοήθεια από άλλα πρόσωπα, είτε με προσωπική επικοινωνία είτε με επικοινωνία μέσω άλλων μέσων επικοινωνίας και ανταλλαγής πληροφοριών.» Η αντίστοιχη δήλωση θα αναγράφεται και στις εκφωνήσεις των θεμάτων.
  4. Ο υπολογιστής του κάθε εξεταζόμενου διαθέτει κάμερα, μικρόφωνο και ηχείο τα οποία θα χρησιμοποιηθούν κατά την διάρκεια ταυτοποίησης των εξεταζόμενων. 

***Διαδικασία εξέτασης

  1. Οι σπουδαστές/τριες πρέπει να συνδεθούν στην τάξη/ομάδα «Αλγόριθμοι και Πολυπλοκότητα – Σεπτ. 2021» της εφαρμογής Teams τουλάχιστον 30 λεπτά πριν την έναρξη της εξέτασης.
  2. Πριν την έναρξη της εξέτασης ή κατά την διάρκεια της εξέτασης θα γίνει ταυτοποίηση των εξεταζόμενων μέσω της κάμερας του υπολογιστή τους. Θα πρέπει να επιδείξουν την φοιτητική τους ταυτότητα.
  3. Την ώρα έναρξης της εξέτασης θα δοθεί πρόσβαση από στην πλατφόρμα Teams στο διαγώνισμα (ως  “assignment”, σε μορφή MS Forms) . Σχετική ειδοποίηση θα εμφανιστεί στο Teams, είτε στο σύνδεσμο «Activity» ή στο σύνδεσμο «Posts» του καναλιού «General».Ακολουθώντας το σύνδεσμο του Διαγωνίσματος, εμφανίζονται οι ερωτήσεις του διαγωνίσματος τις οποίες καλείστε να απαντήσετε κάνοντας την κατάλληλη επιλογή(ές) εάν πρόκειται για ερώτηση πολλαπλών επιλογών, ή να αναρτήσετε αρχείο σε  μορφή pdf το οποίο περιέχει την απάντησή σας (εάν πρόκειται για ερώτηση ελεύθερου κειμένου).
  4. Οι φοιτητές έχουν στην διάθεσή τους 1 ώρα και 15 λεπτά για να υποβάλλουν το διαγώνισμά τους. Η υποβολή πρέπει να γίνει πατώντας το πλήκτρο “Submit” που βρίσκεται στο τέλος του διαγωνίσματος.
    Σημαντική σημείωση:
    1. Στο διάστημα της 1 ώρας και 15 λεπτών που διαρκεί το διαγώνισμα συμπεριλαμβάνεται ο χρόνος που χρειάζεστε για τη «σάρωση και την ανάρτηση των χειρόγραφων απαντήσεων σας.
    2. Η υποβολή του διαγωνίσματός σας (μέσω του πλήκτρου “submit”) πρέπει να γίνει μέσα στα χρονικά όρια του διαγωνίσματος. Μετά την λήξη του διαγωνίσματος ΔΕΝ είναι δυνατή η υποβολή του.
  5. Οι πρώτες ερωτήσεις του διαγωνίσματος αφορούν τα στοιχεία του φοιτητή (Επώνυμο, Όνομα, Όνομα Πατρός, Σχολή, Αριθμό Μητρώου) και είναι υποχρεωτική η απάντησή τους. Σε περίπτωση μη απάντησης δεν μπορεί να υποβληθεί το διαγώνισμα.

***Οδηγίες για τη σάρωση και την ανάρτηση των απαντήσεων.

Ενδεικτικές οδηγίες έχουν αναρτηθεί στης ενότητα «Εργαλεία --> Έγγραφα» στο mycourses.

 

***Συνοπτικές οδηγίες για χρήση της πλατφόρμας Microsoft Teams.

Απαραίτητη για τη συμμετοχή σας στο διαγώνισμα είναι η ενεργοποίηση της ιδρυματικής σας συνδρομής στο Office 365. Οδηγίες μπορείτε να βρείτε στον παρακάτω σύνδεσμο:

http://www.noc.ntua.gr/el/teleteaching-guide (επιλέξτε το «Οδηγίες χρήσης Microsoft Teams για φοιτητές»).

Συνοπτικά, Θα πρέπει να ταυτοποιηθείτε στο ΔΗΛΟΣ https://delos365.grnet.gr/. Στη σελίδα του  Delos πατήστε το σύνδεσμο «Σύνδεση» (πάνω δεξιά) διαλέξτε τον φορέα πιστοποίησης (National Technical University of Athens). Θα συνδεθείτε μέσω SSO του ΕΜΠ https://login.ntua.gr/. Είναι το ίδιο username και password που χρησιμοποιείτε στο mycourses. 

Όταν ενεργοποιήσετε την ιδρυματική σας συνδρομή, εγκαταστήστε την εφαρμογή Teams στον υπολογιστή σας (μπορεί να τρέξει και μέσω  browser, εκτός του safari, αλλά δεν ενδείκνυται). Συνδεθείτε στο Teams χρησιμοποιώντας κατά την διαδικασία του sing-in το όνομα χρήστη username@ntua.gr  (αντί του username@mail.ntua.gr) και τον κωδικό που χρησιμοποιείται στο mycourses.

Όταν έχετε εγκαταστήσει και συνδεθεί στο teams, μπορείτε να εγγραφείτε στην τάξη/ομάδα «Αλγόριθμοι και Πολυπλοκότητα – Σεπτ. 2021» ακολουθώντας τον  σύνδεσμο που αναφέρθηκε παραπάνω.

 

ΤΕΛΟΣ ΑΝΑΚΟΙΝΩΣΗΣ

 
-------------------------
Εισαγωγή. Δομές δεδομένων και αλγόριθμοι. Ασυμπτωτική ανάλυση.
Γραφήματα. Βασικές έννοιες. Αναζήτηση κατά «βάθος» και κατά «πλάτος». Τοπολογική διάταξη.
Η μέθοδος "Διαίρει‐και‐Βασίλευε". Δυαδική αναζήτηση. Πολλαπλασιασμός πινάκων.
Η μέθοδος της Απληστίας. Το πρόβλημα επιλογής δραστηριοτήτων. Κώδικες Huffman. Ελάχιστα μονοπάτια από κοινή αφετηρία (αλγόριθμος Dijkstra). Ελάχιστα διασυνδετικά δένδρα (Αλγόριθμος Prim).
Δυναμικός Προγραμματισμός. Πολλαπλασιασμός αλυσίδας. Μεγίστη κοινή υπο‐ακολουθία. Ελάχιστα μονοπάτια για κάθε ζεύγος κόμβων.
Κάτω φράγματα. Φράγματα εισόδου‐εξόδου. Φράγματα «αντιπάλου» (adversary). Ταξινόμηση, Κώδικες Huffman.
Προβλήματα γραφημάτων. Έλεγχος ακυκλικότητας γραφήματος. Ισχυρά συνδεδεμένα συστατικά. Ελάχιστα διαδυνδετικά δένδρα: ο αλγόριθμος του Kruskal. Ελάχιστα
μονοπάτια από κοινή αφετηρία: ο αλγόριθμος των Bellman‐Ford. Μέγιστη ροή: ο αλγόριθμός των Ford‐Fulkerson και ο αλγόριθμος των Edmonds‐Karp.
NP και υπολογιστική δυσεπιλυσιμότητα. Αναγωγές πολυωνυμικού χρόνου. Η κλάση NP. NP‐πλήρη προβλήματα.
 
Διδάσκων

Αντώνιος Συμβώνης, Καθηγητής
Κτίριο Μαθηματικού, Γρ. 3.18

Διαλέξεις

·       Τρίτη  17:00 - 19:00, online

·       Πέμπτη  16:00 - 18:00, online

Υλικό διαλέξεων 

Υλικό φροντιστηριακών ασκήσεων

Σύγγράμματα
  • "Εισαγωγή στους Αλγορίθμους (σε έναν τόμο)"
    Cormen, Leiserson,Rivest, Stein
    Πανεπιστημιακές Εκδόσεις Κρήτης, 2012
    Διανομή από το βιβλιοπωλείο: ...

  • "Σχεδιασμός Αλγορίθμων"
    Kleinberg, Tardos
    Εκδόσεις Κλειδάριθμος
    Διανομή από το βιβλιοπωλείο: ...

Αξιολόγηση
  • Προγραμματιστικές/Γραπτές Ασκήσεις: 15% 
  • Τελικό γραπτό διαγώνισμα: 85%