Ειδικά Κεφάλαια Αλγορίθμων και Προγραμματισμού

Ειδικά Κεφάλαια Αλγορίθμων και Προγραμματισμού

Ακαδημαϊκό Έτος 2010 - 2011, Χειμερινό Εξάμηνο

Διδάσκων :

Παύλος Εφραιμίδης, Επίκ. Καθηγητής
Γραφείο 4, Κτίριο Α, Πανεπιστημιούπολη
pefraimi <at> ee.duth.gr
τηλ/fax: 25410 79756

ΠΕΡΙΓΡΑΦΗ

Θεωρία:
Θα ασχοληθούμε με Αλγοριθμική Θεωρία Παιγνίων.

Εργαστήριο:
Θα υλοποιήσουμε πολιτικές παίκτών-agents που θα συναγωνιστούν σε απλά (δικτυακά) παίγνια.

ΩΡΕΣ Διδασκαλίας - Εργαστηρίου

Διδασκαλία	Παρασκευή 09:00 - 11:00, Αίθουσα 2.1
Εργαστήριο	Πέμπτη 11:00 - 13:00 Αίθουσα Υπολογιστών ΑΥ1

Διδασκαλίες - Ύλη Μαθήματος (ενδεικτικές)

Ενότητα	Περιεχόμενο	Διδασκαλίες	Παρατηρήσεις
1	Περιεχόμενα - Στόχοι - Απαιτήσεις του Μαθήματος
2	Γνωριμία με τη θεωρία παιγνίων Η εφαρμογή NetGame
3	Παραδείγματα Παιγνίων
4	Βασικές έννοιες και ορισμοί
5	GamBit NetGame
6	Μοντέλα των Cournot και Bertrand
7	Tragedy of the Commons
8	Διαδικτυακά Παίγνια
9	Μηχανισμοί για το δικτυακό παίγνιο
10	Δείκτες δικαιοσύνης στην κατανομή πόρων
11	Solution Concepts
12	Δημοπρασίες (auctions)
13	Μη-συμμετρική δυαδική αναζήτηση
14	Παίγνια με Οικονομικές Συναλλαγές
15	Παρουσίαση εργασίας: ο παίκτης για το NetGame Το παίγιο Market στο NetGame
16	Quiz

Ενδεικτικά εργαστήρια

1	Επίλυση απλών παιγνίων με την εφαρμογή Gambit	EKAPLab01.pdf
2	Σύνοψη Java - Eclipse	EKAPLab02.pdf
3	Γνωριμία με το NetGame	EKAPLab03.pdf
4	Εκτέλεση ενός παιγνίου στο NetGame	EKAPLab04.pdf
5	Δημιουργία παίκτη/πολιτικής ενός flow	EKAPLab05.pdf
6	Δημιουργία μιας πολιτικής ουράς	EKAPLab06.pdf
7	Αρχιτεκτονική της εφαρμογής NetGame	EKAPLab07.pdf

Πρωτάθλημα 2010/11

Θα εκτελεστεί ένα πρωτάθλημα με 4 ή περισσότερες αγωνιστικές. Σε κάθε αγωνιστική θα εκτελούνται συγκεκριμένα παίγνια του NetGame. Για κάθε συγκεκριμένο παίγνιο θα καθορίζονται εξαρχής τα χαρακτηριστικά του router (αλγοριθμικού μηχανισμού) όπως πολιτική ουράς, μέγεθος ουράς, ταχύτητα εξυπηρέτησης πακέτων κτλ.

Όροι για κάθε παίγνιο:

Το score υπολογίζεται (NetGame v0.34+) ως:
- Packet OK : +1
- Packet Lost: -1
Κάθε παίγνιο θα διαρκεί πχ 180 δευτερόλεπτα και αν χρειαστεί θα επαναληφθεί αρκετές φορές ώστε να βγει το μέσο σκορ.
Ρυθμίσεις: Πριν την έναρξη κάθε παίγνιου μπορείτε να ρυθμίσετε τις παραμέτρους των flows/παικτών
Βαθμολογία: Για κάθε εκτέλεση του παιχνιδιού οι παίκτες συγκεντρώνεται βαθμούς σύμφωνα με τον ακόλουθο κανόνα:
- Θέση 1: 30 βαθμοί
- Θέση 2: 25 βαθμοί
- Θέση 3: 22 βαθμοί
- Θέση 4: 20 βαθμοί
- Θέση 5: 18 βαθμοί
- Θέσεις 6-20: (21-θέση) βαθμοί

Οδηγίες (ενδεικτικά):

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

Αγωνιστική	Ημερομηνία	Queue Parameters			Clients	Επιπλέον Χαρακτηριστικά
Αγωνιστική	Ημερομηνία	Policy	QueueSize	Time/pack	Default Timeout
Δοκιμαστική	02/12/2010	CHOKe	100	50	5100
		PrinceGentle	100	50	5100
		Prince (Severe)	100	50	5100
1η	21/12/2010	DropTail	50	50	2550
		PrinceGentle	50	50	2050
		CHOKe	80	50	2550
		Prince	70	20	1450
		MaxMin	50	20	1050
2η	13/01/2011	DropTail	100	50	5050	Σε κάθε παίγνιο θα δημιουργείται και επιπλέον φόρτος στον router με την κλάση ClientTraffic. Η διάρκεια κάθε παιγνίου/πειράματος μπορεί να είναι μέχρι και 300sec.
		PrinceGentle	100	50	5050
		CHOKe	100	50	3550
		Prince	100	50	5050
		MaxMin	100	50	5050
3η (ενδεικτικά)	20/01/2011	DropTail	100	50	5050	Σε κάθε παίγνιο θα δημιουργείται και επιπλέον φόρτος στον router με την κλάση ClientTraffic. Η διάρκεια κάθε παιγνίου/πειράματος μπορεί να είναι μέχρι και 300sec.
		PrinceGentle	100	50	5050
		CHOKe	100	50	3550
		Prince	100	50	5050
		MaxMin	100	50	5050

ClientTraffic: Η κλάση exp.ClientTraffic δημιουργεί τυχαία κίνηση στον server.

NetGame v0.48b

NetGameAlgProject0.48b.zip : archive με το eclipse project

GameScoreBoard improvements: PolicyName, About and Version are now shown in the Score Board

Updated: 17-01-2011

NetGame v0.48α

NetGameAlgProject0.48a.zip : archive με το eclipse project

Packets Sent counter: Now takes into account the "packets in flight" when initializing.
QueuePolicy and FlowController xml files updated.
CHOKe queue policy is now more conservative at rejecting packets.

Updated: 10-01-2011

NetGame v0.48

NetGameAlgProject0.48.zip : archive με το eclipse project

The packetOldACK(CPacket cPacket) method of the basic FlowController class is now abstract: "abstract public void packetOldACK(CPacket cPacket);"
The effect: Every FlowController has to implement a corresponding method.

Updated: 14-11-2010

Βιβλιογραφία

Δεν θα υπάρχει ένα αποκλειστικό βιβλίο για το μάθημα, αλλά θα χρησιμοποιηθούν σημειώσεις, papers και υλικό από διάφορα βιβλία. Το υλικό αυτό μπορείτε να το ζητάτε από τους χειριστές στην αίθουσα υπολογιστών.

Βιβλιογραφία:

An introduction to Game Theory, M. Osborne, Oxford University Press, 2004.
Στην ιστοσελίδα του βιβλίου δίνονται σε pdf τα πρώτα κεφάλαια.
Σχεδιασμός Αλγορίθμων, J.Kleinberg and E.Tardos. Είναι μετάφραση του βιβλίου: Algorithm Design, Pearson Education, επιμέλεια ελληνικής έκδοσης: Χ. Ζαρολιάγκης.

Υλικό

Σημειώσεις: Μια εισαγωγή στην αλγοριθμική θεωρία παιγνίων με έμφαση στη θεωρητική θεμελίωσή της δίνεται στις σημειώσεις του μαθήματος "Οικονομική Θεωρία και Αλγόριθμοι" του τμήματος Μηχ ΗΥ και Πληροφορικής, της Πολυτεχνικής Σχολής του Πανεπιστημίου Πατρών.

On-Line Υλικό

Το "The Java Tutorial" είναι μία κλασική, ενημερωμένη πηγή με εκπαιδευτικό υλικό για τη γλώσσα Java. Υπάρχει τόσο on-line όσο και σε off-line για download με τη μορφή html και WinHelp
Το βιβλίο "Thinking in Java" του BRuce Eckel είναι μια ολοκληρωμένη εισαγωγή στον αντικειμενοστραφή προγραμματισμό και τη γλώσσα Java, και διατίθεται δωρεάν από τη σελίδα του εκδότη (Book Site)
Java Lecture Notes (Polytechnic University, Brooklyn)
Java Lecture Notes (San Diego State University)

Σελίδες από παλαιότερα έτη

2009/2010
2008/2009
2007/2008
2006/2007
2005/2006
2004/2005
2003/2004
2002/2003