Κωδικός Μαθήματος: IC470
ECTS: 6
Πρόγραμμα Σπουδών: Προπτυχιακό Πρόγραμμα Σπουδών
Εξάμηνο Διδασκαλίας: Ζ' Εξάμηνο
Τύπος Μαθήματος
 Επιλογής
Κατεύθυνση ΓΝΜ: Ελεύθερης Επιλογής
Κατεύθυνση ΘΡΜ: Ελεύθερης Επιλογής
Κατεύθυνση ΕΦΜ: Ελεύθερης Επιλογής
Κατεύθυνση ΠΛΗ: Ελεύθερης Επιλογής
Κατεύθυνση ΣΠΕ: Ελεύθερης Επιλογής
Ώρες Διδασκαλίας (Θεωρία / Φροντιστήριο / Εργαστήριο): 2-0-2
Σελίδα μαθήματος στο eClass : https://eclass.upatras.gr/courses/MATH1316/
Φοιτητές Erasmus: Όχι
Περιγραφή
Τεχνικές απαρίθμησης (αρχή περιστερώνα, διπλή απαρίθμηση, μέθοδος μέσης τιμής) και εφαρμογές (πυκνότητα 0-1
μητρείων, θεώρημα Lovász-Stein, συστήματα διακριτών αντιπροσώπων).
Συστήματα συνόλων (οικογένειες τομής, αλυσίδες και αντιαλυσίδες, blocking sets και δυικότητα, σχεδιασμοί).
Πιθανοτική μέθοδος (γραμμικότητα της μέσης τιμής, μέθοδος δεύτερης ροπής, Τοπικό Λήμμα του Lovász, συνάρτηση
εντροπίας του Shannon) και εφαρμογές (χρωματισμός γραφημάτων, k-SAT, κάλυμμα κλικών, σύνολα ανεξαρτησίας,
θεώρημα Erdős-Ko-Rado).