Σκοπός του μαθήματος είναι η ευρεία εισαγωγή στις βασικές έννοιες, τα αποτελέσματα, και τις εφαρμογές της θεωρίας πληροφορίας, η οποία αποτελεί το θεμελιώδες πεδίο μελέτης της μετάδοσης και συμπίεσης σημάτων.
Οι έννοιες της εντροπίας και της πληροφορίας.
Αναπωλειακή συμπίεση σήματος.
Θεωρία: Ιδιότητα της «ασυμπτωτικής ισοκατανομής», ο ρόλος της εντροπίας.
Εφαρμογές: Αλγόριθμοι Huffman, Shannon-Fano, Lempel-Ziv, αριθμητική κωδικοποίηση (arithmetic coding).
Σήματα και θόρυβος. Διακριτά κανάλια. Κωδικοποίηση και χωρητικότητα καναλιού (channel capacity).
Θεωρία: το βασικό θεώρημα του Shannon.
Εφαρμογές: Γραμμικοί, κυκλικοί, και άλλοι κώδικες.
Διαχωρισμός πηγής-καναλιού. Συμπίεση με απώλειες και κβαντοποίηση.
Θεωρία: Συνάρτηση ρυθμού-απώλειας (rate-distortion function) και το δεύτερο θεώρημα του Shannon.
Εφαρμογές: Μέθοδοι κβαντοποίησης, ο αλγόριθμος του Lloyd, πρακτικά παραδείγματα.
Αλγοριθμική πολυπλοκότητα Kolmogorov. Εντροπία και επιστήμη υπολογιστών.
Το μάθημα θα βασιστεί στα παρακάτω βιβλία, κυρίως
στο πρώτο:
"Elements of Information Theory" T.M. Cover and J. Thomas, New York: Wiley, 1991.
"Information Theory, Inference, and Learning Algorithms"
D.J.C. MacKay, Cambridge University Press, 2003.
Βασικά στοιχεία πιθανοτήτων: Διακριτές πιθανότητες, δεσμευμένες πιθανότητες, μέση τιμή, διασπορά, νόμος των μεγάλων αριθμών, ανισότητες Markov, Chebychev, Jensen. Ανεξαρτησία και δεσμευμένη ανεξαρτησία.
