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

ΠεριγραφήΔιαλέξειςΕργαστήριοΕργασίεςΥλικόΣύνδεσμοι
Αλγόριθμοι και Πολυπλοκότητα
Εξάμηνο 7ο
Κωδικός Λ11Ε
ECTS 3
Διδακτικές Μονάδες 4
Ώρες Θεωρίας 2
Ώρες Ασκήσεων 1
Ώρες Εργαστηρίου 2
Τομέας Λογισμικού και Ανάπτυξης Εφαρμογών
Διδάσκοντες Παύλος Εφραιμίδης
Syllabus
Βασικές έννοιες αλγορίθμων. Ταξινόμηση και Αναζήτηση. Υπολογιστικά Μοντέλα. Η μηχανή Turing και η Random Access Machine. Πολυπλοκότητα Αλγορίθμων. Τεχνικές Σχεδιασμού Αλγορίθμων. Διαίρει και Βασίλευε. Αναδρομή και Απαλοιφή Αναδρομής. Δυναμικός Προγραμματισμός. Απληστία. Αλγόριθμοι Γραφημάτων και Δέντρων. Αλγόριθμοι με χρήση Τυχαιότητας. Κλάσεις Πολυπλοκότητας. Οι κλάσεις P και NP. Προβλήματα πλήρη για την κλάση NP. Αναγωγές. Αναφορά σε Ευρετικές Τεχνικές και Αλγόριθμους Προσέγγισης. Σχεδιασμός και υλοποίηση βασικών Αλγορίθμων σε σύγχρονα περιβάλλοντα Προγραμματισμού.
Θεωρία
Θα ασχοληθούμε με επιλεγμένα θέματα Αλγορίθμων και Πολυπλότητας. Θα χρησιμοποιήσουμε ως εφαρμογή παραδείγματα και έννοιες από την Αλγοριθμική Θεωρία Παινγίων.
Εργαστήριο
Θα υλοποιήσουμε πολιτικές παικτών-agents που θα συναγωνιστούν σε απλά (δικτυακά) παίγνια.
Διδάσκων
Παύλος Εφραιμίδης, Επίκ. Καθηγητής.
Ώρες γραφείου
Παύλος (για οποιοδήποτε θέμα): Πέμπτη 09:00 – 12:00.

Ημερομηνία Τύπος Σχόλια Αρχεία
Δευτέρα, 29 Σεπτ. 2014 Παρουσίαση μαθήματοςBraess Paradox, Prisoner’s Dillemma (εισαγωγή)
Δευτέρα, 06 Οκτ. 2014 The Prisoner’s DillemmaThe Hotelling game
Τρίτη, 14 Οκτ. 2014 Βασικές Έννοιες Θεωρίας Παιγνίων
Τρίτη, 21 Οκτ. 2014 Βασικές Έννοιες Θεωρίας Παιγνίων (συνέχεια)Ιστορικά στοιχεία
Τρίτη, 28 Οκτ. 2014 ΑΡΓΙΑ 28ης Οκτωβρίου
Τετάρτη, 29 Οκτ. 2014 Εργαστήριο Gambit: Game Examples
Τρίτη, 04 Νοε. 2014 Ultimatum Game. Complexity of NE. The NetGame tool.
Τρίτη, 11 Νοε. 2014 Mechanisms of the NetGame.
Τετάρτη, 12 Νοε. 2014 Εργαστήριο NetGame: Εκτέλεση του NetGame. Δημιουργία ενός FlowController.
Τρίτη, 18 Νοε. 2014 NetGame. Opinion Dynamics (intro).
Τρίτη, 25 Νοε. 2014 Δεν θα γίνει μάθημα.
Τετάρτη, 26 Νοε. 2014 Εργαστήριο NetGame: 1η αγωνιστική NetGame.
Τρίτη, 02 Δεκ. 2014 Asymmetric Binary Search. Learning.
Τετάρτη, 03 Δεκ. 2014 Εργαστήριο NetGame: 2η αγωνιστική NetGame.
Τρίτη, 09 Δεκ. 2014 Auctions,Opinion Dynamics
Τετάρτη, 10 Δεκ. 2014 Εργαστήριο NetGame: 3η αγωνιστική NetGame.
Τρίτη, 16 Δεκ. 2014 Κουίζ (πρόοδος),Opinion Dynamics
Τετάρτη, 17 Δεκ. 2014 Εργαστήριο Opinion Dynamics
Τρίτη, 23 Δεκ. 2014 ???
Τρίτη, 30 Δεκ. 2014 ΑΡΓΙΑ
Τρίτη, 06 Ιαν. 2015 ΑΡΓΙΑ
Τετάρτη, 07 Ιαν. 2015 Αγωνιστική Opinion Dynamics ???
Τρίτη, 13 Ιαν. 2015 Παρουσίαση Εργασιών ???

Διαγωνισμός – εκτέλεση παίγνιου στο NetGame
Θα εκτελεστεί ένα πρωτάθλημα με πιθανότατα 3 αγωνιστικές.
Όροι του παίγνιου:

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

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

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

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

Αγωνιστική
Ημερομηνία
Queue Parameters
Clients
Επιπλέον Χαρακτηριστικά
Policy
QueueSize
Time/pack
Default Timeout
Δοκιμαστική
26/11/2014
 DropTail
100
50
5100
PrinceGentle
100
50
5100
MaxMin
100
50
5100
1η
26/11/2014
 DropTail
100
50
5100
PrinceGentle
100
50
5100
MaxMin
100
50
5100
2η
03/12/2014
 DropTail
100
50
5100
PrinceGentle
100
50
5100
CHOKe
100
50
2800
PrinceSevere
100
50
5100
MaxMin
100
50
5100
3η
10/12/2014
 PrinceGentle
100
50
5100
PrinceSevere
100
50
5100
CHOKe
100
50
2800
RED with ECN (gentle)
100
50
  2800

 

Εργαστήριο SocialInfluence

https://euclid.ee.duth.gr/wp-content/uploads/2014/12/SocialInfluenceProjectV1.0.zip

Αγωνιστική Ημερομηνία Παράμετροι Κώδικας/πληροφορίες Σχόλια
Δοκιμαστική 17/12/2014 Cycle graph SocialInfluenceProject v1.0
Επίσημη 07/01/2015 Two wheels graphScale-free graph

Unknown graph

Εργασίες

Α/Α
Όνομα ή Ομάδα
Θέμα
Υλικό (eClass)
1
Team (29A)16
 The games genes play
  • A mixability theory of the role of sex in evolution – MixabilityTheory-1.pdf
  • Sex, mixability, and modularity – SMM-2010.pdf
2
  Team (29A)16 – ΓΠ Complexity of NE
  • The Complexity of Computing a Nash Equilibrium
3
Team (45)16
 Opinion Dynamics
  • Algorithmic Techniques for Influence Dynamics in Social Networks
  • Can Google fix an election?
4
Team 42
 Corruption – A game-theoretical analysis Corruption – A game-theoretical analysis

  • Introduction
  • A Bribee Initiated Corrupt Transaction
5
Team 00
 Corruption – A game-theoretical analysis Corruption – A game-theoretical analysis

  • A Briber Initiated Corrupt Transaction
  • Spurious- Insider Middleman
6
Team 158
 Experiments in Social Computation Experiments in Social Computation – p56-kearns.pdf

  • Behavioral Experiments on a Network Formation Game – p690
7
Team 39
 Experiments in Social Computation Experiments in Social Computation – p56-kearns.pdf

  • Behavioral experiments on biased voting in networks – behvoting

 

Παρουσίαση εργασιών:

  • 20 λεπτά μικτός χρόνος
  • περίπου 17 λεπτά καθαρός χρόνος
  • περίπου 12-15 διαφάνειες

Αναφορά:

  • περίπου 1500 λέξεις

  1. eClass του μαθήματος
  2. Χώρος συζητήσεων στο DUTh EECE forum