Πιθανοτικές Τεχνικές και Τυχαιοκρατικοί Αλγόριθμοι¶

Επιλογής μάθημα του τομέα ΕΘ πάνω στη λεγόμενη «πιθανοτική μέθοδο»: μη κατασκευαστικές αποδείξεις ύπαρξης συνδυαστικών δομών, μέθοδος θετικής πιθανότητας, γραμμικότητα μέσης τιμής, μέθοδος δεύτερης ροπής, τοπικό θεώρημα Lovász, ανισότητα Janson, φράγματα Chernoff, τυχαίοι περίπατοι και μαρκοβιανές αλυσίδες. Είναι στην ουσία «μαθηματικά» γεμάτο αποδείξεις, όχι μάθημα προγραμματισμού. Ιστορικά εξεταζόταν προφορικά· από το 2025-26 η εξέταση έγινε γραπτή.

Θέματα Τι λένε οι φοιτητές Περίγραμμα ⬇ Κατέβασε για AI

Με μια ματιά¶


Κωδικός	CEID_NE5017
Εξάμηνο / τύπος	Χειμερινό, επιλογής Κατάλογος
ECTS	5 Κατάλογος
Ώρες / εβδομάδα	2 θεωρία + 2 φροντιστήριο + 1 εργαστήριο Κατάλογος
Τομέας	ΕΘ Κατάλογος
Διδάσκων 2025-26	Σ. Νικολετσέας Κατάλογος
Αξιολόγηση	Ιστορικά προφορική εξέταση· από το 2025-26 γραπτή· υποχρεωτική εργασία εξαμήνου Discord 2020-12 (διαθέσιμο στο πλήρες πακέτο), Discord 2026-02 (διαθέσιμο στο πλήρες πακέτο)
Συνιστώμενα προαπαιτούμενα	Πιθανότητες (κατά φοιτητές) Discord 2020-10 (διαθέσιμο στο πλήρες πακέτο)

Τι θα μάθεις¶

Η επίσημη περιγραφή της σελίδας του μαθήματος αναφέρει: μη κατασκευαστικές αποδείξεις ύπαρξης συνδυαστικών δομών, τη μέθοδο της θετικής πιθανότητας, τη γραμμικότητα της μέσης τιμής, τη μέθοδο της δεύτερης ροπής, το τοπικό θεώρημα του Lovász, την ανισότητα Janson, ακολουθίες διατήρησης, τυχαίους περιπάτους και μαρκοβιανές αλυσίδες, φράγματα Chernoff, καθώς και εισαγωγή σε πιθανοτικούς αλγορίθμους Κατάλογος. Οι διαλέξεις είναι στα αγγλικά και ξεκινούν με τη μέθοδο της θετικής πιθανότητας, τους αριθμούς Ramsey και το βασικό επιχείρημα eClass (διαθέσιμο στο πλήρες πακέτο). Στην πράξη το μάθημα είναι μια σειρά θεωρημάτων και αποδείξεων γύρω από αυτές τις τεχνικές.

Πώς βαθμολογείται¶

Ιστορικά η αξιολόγηση ήταν προφορική εξέταση στο τέλος με ερωτήσεις κατανόησης πάνω στις διαφάνειες, όπου ο διδάσκων άνοιγε τυχαία διαλέξεις από τη σελίδα του μαθήματος Discord 2021-02 (διαθέσιμο στο πλήρες πακέτο), Discord 2021-09 (διαθέσιμο στο πλήρες πακέτο).
Χειμερινό 2020-21: ανακοινώθηκε υποχρεωτική εργασία 1–2 ατόμων που αναλογούσε στο 30% του τελικού βαθμού, με την τελική εξέταση στο υπόλοιπο 70%, προθεσμία 25/1/2021 και υποβολή μέσω eClass Discord 2020-12 (διαθέσιμο στο πλήρες πακέτο).
Από το χειμερινό 2025-26 η εξέταση έγινε γραπτή· φοιτητής σημειώνει ότι «είναι η πρώτη φορά που το μάθημα έχει γραπτή εξέταση, τις άλλες χρονιές ήταν προφορικά» Discord 2026-02 (διαθέσιμο στο πλήρες πακέτο).
Ο κατάλογος 2025-26 δεν δίνει ποσοστά βαρών ή βαθμολογική κλίμακα Κατάλογος.

Εργασίες & εργαστήρια¶

Χειμερινό 2020-21: υποχρεωτική εργασία, 1–2 άτομα, 30% του βαθμού, παράδοση μέσω eClass, με δυνατότητα χειρόγραφης ή ηλεκτρονικής μορφής Discord 2020-12 (διαθέσιμο στο πλήρες πακέτο).
2021-22: «έχει μια εργασία εξαμήνου υποχρεωτική νομίζω αλλά όχι πολύ δύσκολη» και «μόνο εργασία και προφορική εξέταση στο τέλος» — χωρίς εργαστήριο Discord 2021-10 (διαθέσιμο στο πλήρες πακέτο), Discord 2021-11 (διαθέσιμο στο πλήρες πακέτο).
2023-24: φοιτητής ρωτά αν έχει εργασία και σε τι· απάντηση ότι «έχει εργασία, μια παρόμοια με την περσινή» και να δει το eClass Discord 2023-10 (διαθέσιμο στο πλήρες πακέτο).
Ερωτήσεις αν η εργασία παραδίνεται Σεπτέμβριο έμειναν σε «στείλε mail στον διδάσκοντα» Discord 2023-02 (διαθέσιμο στο πλήρες πακέτο).
Ο κατάλογος δίνει 1 ώρα εργαστηρίου Κατάλογος, αλλά στις συζητήσεις δεν βρέθηκε εργαστήριο — μόνο εργασία Discord 2021-11 (διαθέσιμο στο πλήρες πακέτο).

Εξετάσεις¶

Στον φάκελο δεν υπάρχουν μεταγραφές παλιών θεμάτων Εξετάσεις. Οι μορφές των εξετάσεων του 2026 παρακάτω είναι ανακλήσεις φοιτητών, όπως καταγράφονται στο discord_recalls.md.

Γραπτή εξέταση Φεβρουαρίου 2026: 6 θέματα — δειγματοχώρος και μέσος αριθμός κορυφών σε G(n,p), γραμμικότητα μέσης τιμής και αποδείξεις μη-ύπαρξης, κατώφλι ύπαρξης Κ3, εξήγηση συγκεκριμένης διαφάνειας, αναμενόμενος χρόνος random walk σε Line-Graph, εξήγηση διαφανειών απόδειξης Discord 2026-02 (διαθέσιμο στο πλήρες πακέτο).
Γραπτή εξέταση Σεπτεμβρίου 2026: 5 θέματα — μέσος βαθμός κορυφής/αριθμός ακμών σε G(n,p), θεώρημα δεύτερης ροπής, Κ5-κλίκα, αλγόριθμος lazy select (Monte Carlo ή Las Vegas), εξήγηση διαφάνειας διάλεξης Discord 2026-09 (διαθέσιμο στο πλήρες πακέτο).
Επαναλαμβανόμενα θέματα: γραμμικότητα μέσης τιμής (independent/dominating set), τοπικό θεώρημα Lovász και ανισότητα Janson, Van der Waerden, θεώρημα Turán, μαρκοβιανές αλυσίδες Discord 2023-01 (διαθέσιμο στο πλήρες πακέτο), Discord 2026-02 (διαθέσιμο στο πλήρες πακέτο).
Το 2026-02 φοιτητής ζητά παλιά θέματα· απάντηση να κοιτάξει τα pinned του καναλιού Discord 2026-02 (διαθέσιμο στο πλήρες πακέτο).

Δυσκολίες & παγίδες¶

Οι φοιτητές διαφωνούν για τη δυσκολία: το 2020-10 ένας τη χαρακτηρίζει «σχετικά εύκολη» και άλλος απαντά ότι δεν είναι το πιο εύκολο μάθημα και ότι «θέλει να ξέρεις καλά πιθανότητες» Discord 2020-10 (διαθέσιμο στο πλήρες πακέτο).
Κατά φοιτητή (2021-10): δεν είναι δύσκολο αλλά απαιτεί να το παρακολουθείς· αν πας να το δώσεις μόνο στο τέλος «κατά πάσα πιθανότητα δεν θα το περάσεις» Discord 2021-10 (διαθέσιμο στο πλήρες πακέτο).
Ανακοίνωση διδάσκοντα (2021-01): το μάθημα είναι «πολύ απαιτητικό» και η συμμετοχή χωρίς πολύ καλή προετοιμασία και πολυήμερο διάβασμα δεν έχει νόημα Discord 2021-01 (διαθέσιμο στο πλήρες πακέτο).
Στην προφορική εξέταση αναμενόταν να εξηγήσεις τη διαφάνεια που θα σου τύχαινε, μαζί με το γιατί ισχύουν οι ανισότητες Discord 2021-02 (διαθέσιμο στο πλήρες πακέτο), Discord 2021-09 (διαθέσιμο στο πλήρες πακέτο).
Το 2026-09, μετά την αλλαγή σε γραπτή εξέταση, φοιτητής ρωτά τη γνώμη των άλλων για τη δυσκολία — η συζήτηση δεν κατέληξε σε σαφή απάντηση Discord 2026-09 (διαθέσιμο στο πλήρες πακέτο).

Υλικό & τρόπος μελέτης¶

Διαφάνειες (αγγλικά): less1.pdf (διαθέσιμο στο πλήρες πακέτο) — 19 σελίδες, «The Probabilistic Method — Probabilistic Techniques», με τη μέθοδο θετικής πιθανότητας και Ramsey eClass (διαθέσιμο στο πλήρες πακέτο). Φοιτητές προτείνουν να διαβάζεις από τις διαφάνειες, γιατί από εκεί ρωτά θεωρία Discord 2021-02 (διαθέσιμο στο πλήρες πακέτο).
Βιβλίο: book.pdf (διαθέσιμο στο πλήρες πακέτο) στο eClass. Κατά φοιτητή (2021-10) τον βοήθησε το βιβλίο του διδάσκοντα· το 2020-10 σημειώνεται ότι το βιβλίο υπάρχει κυρίως στη βιβλιοθήκη και περιέχει ό,τι και οι διαφάνειες στα ελληνικά Discord 2021-10 (διαθέσιμο στο πλήρες πακέτο), Discord 2020-10 (διαθέσιμο στο πλήρες πακέτο).
Το 2023-10 ο διδάσκων δεν πρότεινε κάποιο συγκεκριμένο σύγγραμμα Discord 2023-10 (διαθέσιμο στο πλήρες πακέτο). Στη σελίδα eclass/ (διαθέσιμο στο πλήρες πακέτο) υπάρχει το αρχείο Συγγράμματα μαθήματος.docx (διαθέσιμο στο πλήρες πακέτο).
Σημειώσεις συμφοιτητών: αναφέρεται αρχείο στο ceidnotes Discord 2020-12 (διαθέσιμο στο πλήρες πακέτο).

Συχνές ερωτήσεις¶

Η εξέταση είναι προφορική ή γραπτή; Ιστορικά προφορική Discord 2022-10 (διαθέσιμο στο πλήρες πακέτο)· από το 2025-26, σύμφωνα με φοιτητές, γραπτή Discord 2026-02 (διαθέσιμο στο πλήρες πακέτο).
Χρειάζεται να το παρακολουθώ; Φοιτητής γράφει ότι ναι, αλλιώς είναι δύσκολο να περάσεις Discord 2021-10 (διαθέσιμο στο πλήρες πακέτο).
Έχει εργασία; Ναι, εργασία εξαμήνου Discord 2023-10 (διαθέσιμο στο πλήρες πακέτο)· το 2020-21 ήταν υποχρεωτική και στο 30% Discord 2020-12 (διαθέσιμο στο πλήρες πακέτο).
Από πού διαβάζω; Από τις διαφάνειες του μαθήματος (θεωρία) Discord 2021-02 (διαθέσιμο στο πλήρες πακέτο).
Μπορώ να παραδώσω την εργασία Σεπτέμβριο; Δεν αναφέρθηκε κάτι· συμβουλή να στείλεις mail Discord 2023-02 (διαθέσιμο στο πλήρες πακέτο).
Υπάρχουν παλιά θέματα; Δεν υπάρχουν μεταγραφές στον φάκελο Εξετάσεις· οι φοιτητές παραπέμπονται στα pinned Discord 2026-02 (διαθέσιμο στο πλήρες πακέτο).
Τι ρωτά στην εξέταση; Ερωτήσεις κατανόησης/θεωρίας πάνω στις διαφάνειες Discord 2021-09 (διαθέσιμο στο πλήρες πακέτο).

Πηγές & αξιοπιστία¶

Κατάλογος 2025-26: 5 ECTS, 2+2+1 ώρες, τομέας ΕΘ, διδάσκων Σ. Νικολετσέας Κατάλογος. Η σελίδα του μαθήματος αναφέρει 4 ECTS — απόκλιση υπέρ του καταλόγου.
Η σελίδα του μαθήματος παραπέμπει σε περίγραμμα άλλου μαθήματος («Ανάκτηση Πληροφορίας»)· το περίγραμμα αυτό δεν χρησιμοποιήθηκε Περίγραμμα.
Discord: 223 μηνύματα σε 11 περιόδους (2020-10 έως 2026-09), κυρίως ανεπίσημες γνώμες· μεγάλο μέρος από το 2020-21 και το 2021-22, δηλαδή πριν την αλλαγή σε γραπτή εξέταση.
eClass: 5 αρχεία (διαφάνειες, βιβλίο, σύγγραμμα, βαθμοί Σεπτ 2026) eClass (διαθέσιμο στο πλήρες πακέτο).
Βαθμοί Σεπτεμβρίου 2026 (χωρίς ονόματα): eClass (διαθέσιμο στο πλήρες πακέτο).
Δεν υπάρχουν μεταγραφές παλιών θεμάτων Εξετάσεις, οπότε η μορφή των γραπτών στηρίζεται μόνο σε ανακλήσεις φοιτητών.

Αρχεία του φακέλου¶

Παράγεται αυτόματα από tools/render_readmes.py — αλλαγές εδώ χάνονται στην επόμενη εκτέλεση.

Φάκελος	Περιεχόμενο
`discord/` (διαθέσιμο στο πλήρες πακέτο)	11 περίοδοι συζητήσεων Discord · 223 μηνύματα
`Previous Exams/`	0 συνεδρίες εξετάσεων · ανακλήσεις από Discord
`eclass/` (διαθέσιμο στο πλήρες πακέτο)	5 αρχεία · 3 κείμενα (sidecar)
`other/`	2 αρχεία (1 εικόνες)