Αποκεντρωμένος Υπολογισμός & Μοντελοποίηση (CEID_NE589)

Ύλη:

Μέγιστο Ανεξάρτητο σύνολο (Maximal Independent Set - MIS):

1. Βασικές έννοιες
2. Ο σειριακός αλγόριθμος και μία άμεση προσαρμογή του σε κατανεμημένο περιβάλλον
3. Αδυναμία επίλυσης του MIS χωρίς τυχαιοκρατία
4. Αλγόριθμος για MIS βασισμένος σε χρωματισμό
5. Ένας τυχαιοκρατικός αλγόριθμος και μία πιο γρήγορη παραλλαγή του βασισμένη στον αλγόριθμο του Luby
6. Σύνδεση ενός βιολογικού μηχανισμού με το πρόβλημα του MIS

Υλικό:

Διαφάνειες

Η εγγραφή της διάλεξης σε zoom

Δείτε τις αναφορές στην τελευταία διαφάνεια.

Ύλη:

Έγινε μία παρουσίαση της ύλης του μαθήματος και των σχετικών διαδικασιών. Επίσης, έγινε παρουσίαση εννοιών που θα δούμε στο μάθημα. Επίσης αναφέρθηκαν τα εξής θέματα.

1. Κατανεμημένος Υπολογισμός - Αποκεντρωμένος Υπολογισμός
2. Μοντέλα (Port Numbering Model, LOCAL, CONGEST)
3. Ο αλγόριθμος άπληστης μείωσης χρωμάτων (Greedy Color Reduction)
4. Τυχαιοκρατικός Αλγόριθμος Χρωματισμού. Την απόδειξη πολυπλοκότητας μπορείτε να τη βρείτε εδώ.

Υλικό:

Διαφάνειες

Η εγγραφή της διάλεξης σε zoom. 

Στην καρτέλα "Σ