Αλγόριθμοι και Πολυπλοκότητα 2016-17

ΠεριγραφήΔιαλέξειςNetGameΕργασίεςΣύνδεσμοι
Αλγόριθμοι και Πολυπλοκότητα
Εξάμηνο 8ο
Κωδικός Λ11Ε
ECTS 3
Διδακτικές Μονάδες 4
Ώρες Θεωρίας 2
Ώρες Ασκήσεων 1
Ώρες Εργαστηρίου 2
Τομέας Λογισμικού και Ανάπτυξης Εφαρμογών
Διδάσκοντες Παύλος Εφραιμίδης
Περίληψη
Βασικές έννοιες αλγορίθμων. Ταξινόμηση και Αναζήτηση. Υπολογιστικά Μοντέλα. Η μηχανή Turing και η Random Access Machine. Πολυπλοκότητα Αλγορίθμων. Τεχνικές Σχεδιασμού Αλγορίθμων. Διαίρει και Βασίλευε. Αναδρομή και Απαλοιφή Αναδρομής. Δυναμικός Προγραμματισμός. Απληστία. Αλγόριθμοι Γραφημάτων και Δέντρων. Αλγόριθμοι με χρήση Τυχαιότητας. Κλάσεις Πολυπλοκότητας. Οι κλάσεις P και NP. Προβλήματα πλήρη για την κλάση NP. Αναγωγές. Αναφορά σε Ευρετικές Τεχνικές και Αλγόριθμους Προσέγγισης. Σχεδιασμός και υλοποίηση βασικών Αλγορίθμων σε σύγχρονα περιβάλλοντα Προγραμματισμού.
Θεωρία
Θα ασχοληθούμε με επιλεγμένα θέματα Αλγορίθμων και Πολυπλότητας. Θα χρησιμοποιήσουμε ως εφαρμογή παραδείγματα και έννοιες από την Αλγοριθμική Θεωρία Παινγίων.
Εργαστήριο
Θα υλοποιήσουμε πολιτικές παικτών-agents που θα συναγωνιστούν σε απλά (δικτυακά) παίγνια.
Διδάσκων
Παύλος Εφραιμίδης, Αναπλ. Καθηγητής.
Ώρες γραφείου
Παύλος (για οποιοδήποτε θέμα): Τετάρτη 09:00 – 12:00.
Ημερομηνία Τύπος Σχόλια Αρχεία
Παρουσίαση μαθήματοςBraess Paradox, Prisoner’s Dillemma (εισαγωγή)
The Prisoner’s DillemmaThe Hotelling game
Βασικές Έννοιες Θεωρίας Παιγνίων
Βασικές Έννοιες Θεωρίας Παιγνίων (συνέχεια)Ιστορικά στοιχεία
Εργαστήριο Gambit: Game Examples
Ultimatum Game. Complexity of NE. The NetGame tool.
Mechanisms of the NetGame.
Εργαστήριο NetGame: Εκτέλεση του NetGame. Δημιουργία ενός FlowController.
NetGame. Opinion Dynamics (intro).
Εργαστήριο NetGame: 1η αγωνιστική NetGame.
Asymmetric Binary Search. Learning.
Εργαστήριο NetGame: 2η αγωνιστική NetGame.
Auctions,Opinion Dynamics
Εργαστήριο NetGame: 3η αγωνιστική NetGame.
Διαγωνισμός – εκτέλεση παίγνιου στο NetGame
Θα εκτελεστεί ένα πρωτάθλημα με μία ή περισσότερες αγωνιστικές.
Όροι του παίγνιου:

  • Το score κάθε παίκτη υπολογίζεται με βάση τον αριθμό των πακέτων που έστειλε με επιτυχία και τον αριθμό των πακέτων που απορρίφθηκαν (dropped packets). Συγκεκριμένα:
    • Packet OK : +1
    • Packet Lost: -3
  • Κάθε παίγνιο θα διαρκεί περίπου 200 δευτερόλεπτα και αν χρειαστεί θα επαναληφθεί αρκετές φορές ώστε να βγει το μέσο σκορ.
  • Ρυθμίσεις: Πριν την έναρξη κάθε παίγνιου μπορείτε να ρυθμίσετε τις παραμέτρους των flows/παικτών
  • Βαθμολογία: Για κάθε εκτέλεση του παιχνιδιού οι παίκτες συγκεντρώνεται βαθμούς σύμφωνα με αυτές που δίνονται στη Formula 1: Ο πρώτος 10 βαθμούς, κτλ

Εργαστήρια

  • 30/03, 18:00. Gambit, Παρουσίαση NetGame
  • 31/03, 12:00. Εκτέλεση Παιγνίου NetGame
  • 06/04, 12:00. Πακέτα, FlowControllers και Queue Policies στο NetGame
  • 27/04, 18:00. Δοκιμαστική αγωνιστική NetGame
  • 04/05, 18:00. Αγωνιστική NetGame
  • 11/05, 18:00. Αγωνιστική NetGame
  • 18/05, 18:00. Αγωνιστική NetGame

Πρωτάθλημα
Ορισμένοι κανόνες (ενδεικτικά):

  • Για κάθε παίγνιο, μπορείτε να έχετε διαφορετικό παίκτη/flow.
  • Στη διάρκεια του παίγνιου δεν επιτρέπεται παρέμβαση στη λειτουργία του παίκτη/flow.
  • Το μέγεθος της ουράς και το bandwidth του router θα ορίζονται την ώρα της εκτέλεσης του παιγνίου. Επίσης θα ορίζεται μια αρχική τιμή για το timeout των παικτών το οποίο όμως μπορεί να τροποποιηθεί από τα ίδια τα flows.

Χώρος συζητήσεων για απορίες που αφορούν το NetGame και το πρωτάθλημα 2016-17.

https://www.deece.edu.gr/forum/viewtopic.php?f=222&t=8983

Αγωνιστική
Ημερομηνία
Queue Parameters
Clients
Επιπλέον Χαρακτηριστικά
Policy
QueueSize
Time/pack
Default Timeout
 Δοκιμαστική 27/04/2017  DropTail  100  50  5100
RED with ECN
100
50
5100
PrinceGentle
100
50
5100

Ομάδες: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19

04/05/2017 DropTail 100  50 5100
 RED with ECN  100  50  5100
 PrinceGentle  100  50  5100

Ομάδες: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20

11/05/2017  DropTail  100 50  5100
 RED with ECN  100  50  5100
 PrinceGentle  100  50  5100

18:00 – 19:00: Ομάδες 01-10

19:00 – 20:00: Ομάδες 11-20

25/05/2017  PrinceGentle 20 – 500 10 – 100 5100 Δεν θα ανακοινωθεί το μέγεθος ουράς, ούτε η ταχύτητα του router.
 PrinceGentle  20 – 500 10 – 100  5100  Δεν θα ανακοινωθεί το μέγεθος ουράς, ούτε η ταχύτητα του router.
MaxMin  20 – 500 10 – 100  5100  Δεν θα ανακοινωθεί το μέγεθος ουράς, ούτε η ταχύτητα του router.
 MaxMin  20 – 500 10 – 100  5100  Δεν θα ανακοινωθεί το μέγεθος ουράς, ούτε η ταχύτητα του router.
Δεν θα γίνουν βιβλιογραφικές εργασίες το 2016-17.