Subject Code: IC470
ECTS: 6
Study Program: Undergraduate Degree Program
Teaching Semester: Semester 7
Type
 Επιλογής
Κατεύθυνση ΓΝΜ: Ελεύθερης Επιλογής
Κατεύθυνση ΘΡΜ: Ελεύθερης Επιλογής
Κατεύθυνση ΕΦΜ: Ελεύθερης Επιλογής
Κατεύθυνση ΠΛΗ: Ελεύθερης Επιλογής
Κατεύθυνση ΣΠΕ: Ελεύθερης Επιλογής
Teaching Hours (Theory / Tutorial / Laboratory): 2-0-2
Erasmus Students: No
Description
Τεχνικές απαρίθμησης (αρχή περιστερώνα, διπλή απαρίθμηση, μέθοδος μέσης τιμής) και εφαρμογές (πυκνότητα 0-1
μητρείων, θεώρημα Lovász-Stein, συστήματα διακριτών αντιπροσώπων).
Συστήματα συνόλων (οικογένειες τομής, αλυσίδες και αντιαλυσίδες, blocking sets και δυικότητα, σχεδιασμοί).
Πιθανοτική μέθοδος (γραμμικότητα της μέσης τιμής, μέθοδος δεύτερης ροπής, Τοπικό Λήμμα του Lovász, συνάρτηση
εντροπίας του Shannon) και εφαρμογές (χρωματισμός γραφημάτων, k-SAT, κάλυμμα κλικών, σύνολα ανεξαρτησίας,
θεώρημα Erdős-Ko-Rado).