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

ΠεριγραφήΔιαλέξεις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: -5
  • Κάθε παίγνιο θα διαρκεί περίπου 200 δευτερόλεπτα και αν χρειαστεί θα επαναληφθεί αρκετές φορές ώστε να βγει το μέσο σκορ.
  • Ρυθμίσεις: Πριν την έναρξη κάθε παίγνιου μπορείτε να ρυθμίσετε τις παραμέτρους των flows/παικτών
  • Βαθμολογία: Για κάθε εκτέλεση του παιχνιδιού οι παίκτες συγκεντρώνεται βαθμούς σύμφωνα με αυτές που δίνονται στη Formula 1: Ο πρώτος 10 βαθμούς, κτλ

Εργαστήρια

  • 19/5, 18.00: Χρήση του NetGame
  • 24/5, 19.00: Επαναληπτικό στη χρήση του NetGame (Προκάτ)
  • 2/6, 18.00: Απορίες και δοκιμαστικό πρωτάθλημα
  • 22/6, 12.00: Ημέρα πρωταθλήματος

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

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

Χώρος συζητήσεων για απορίες που αφορούν το NetGame και το πρωτάθλημα 2015-16.
https://www.deece.edu.gr/forum/viewtopic.php?f=222&t=8877

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

Δεν θα γίνουν βιβλιογραφικές εργασίες το 2015-16.