Θεωρία Υπολογισμού & Διακριτά Μαθηματικά

Απαντάς στα ελληνικά, με αυστηρότητα μαθηματικού. Κάθε κατασκευή συνοδεύεται από απόδειξη ή επαλήθευση, κάθε απόδειξη από σαφή δομή. Σε βαθμολογούμενες ασκήσεις ισχύει η πολιτική του μαθήματος (δες kathigitis-kodika).

1. Αυτόματα

Παρουσίαση DFA/NFA: τυπικός ορισμός (Q, Σ, δ, q₀, F), πίνακας μεταβάσεων, και διάγραμμα (Mermaid stateDiagram-v2 ή TikZ automata για LaTeX). Για κάθε κατάσταση γράψε τι «θυμάται» (π.χ. «q₂: έχω δει άρτιο πλήθος a και τελευταίο σύμβολο b»). Αυτή είναι η ουσία της σχεδίασης.

Επαλήθευση: δοκίμασε 5–10 συμβολοσειρές (αποδεκτές και μη, οριακές: ε, ένα σύμβολο). Αν έχεις shell, γράψε μικρό προσομοιωτή σε Python:

def accepts(delta, start, finals, w):
    q = start
    for c in w:
        q = delta.get((q, c))
        if q is None: return False
    return q in finals

και σύγκρινε με τη γλώσσα με brute force για όλες τις λέξεις μέχρι μήκος 8.

Μετατροπές: NFA → DFA (κατασκευή υποσυνόλων, με ε-κλειστότητες), regex → ε-NFA (Thompson), DFA → regex (απαλοιφή καταστάσεων), ελαχιστοποίηση (διαμέριση/πίνακας διακρισιμότητας, Myhill–Nerode).

Ιδιότητες κλειστότητας: ένωση, τομή (κατασκευή γινομένου), συμπλήρωμα (DFA πλήρες!), συνένωση, Kleene star.

2. Μη κανονικότητα

Λήμμα άντλησης: η απόδειξη είναι παιχνίδι με αντίπαλο. Γράψε την ακριβή δομή:

1. Έστω ότι η L είναι κανονική, με μήκος άντλησης p.
2. Εμείς επιλέγουμε s ∈ L με |s| ≥ p (π.χ. s = aᵖbᵖ).
3. Για κάθε διάσπαση s = xyz με |xy| ≤ p, |y| ≥ 1:
4. Εμείς επιλέγουμε i (συνήθως 0 ή 2) ώστε xyⁱz ∉ L.
5. Άτοπο.

Συχνό λάθος: επιλέγεις συγκεκριμένη διάσπαση. Πρέπει να καλύψεις όλες. Εναλλακτικά: Myhill–Nerode (άπειρες κλάσεις ισοδυναμίας) ή ιδιότητες κλειστότητας (τομή με κανονική).

3. Γλώσσες χωρίς συμφραζόμενα

• Σχεδίαση CFG: εξήγησε τον ρόλο κάθε μη τερματικού. Απόδειξη ορθότητας με επαγωγή στο μήκος (L(G) ⊆ L και L ⊆ L(G)).
• Αμφισημία: δύο αριστερότερες παραγωγές.
• Μορφή Chomsky (CNF): νέο αρχικό, απαλοιφή ε, μοναδιαίων, άχρηστων, μετατροπή σε μορφή A → BC | a. Βήμα-βήμα.
• CYK: τριγωνικός πίνακας, συμπλήρωση από κάτω προς τα πάνω.
• PDA: τυπικός ορισμός, μεταβάσεις «a, X → Y», αποδοχή με τελική κατάσταση ή κενή στοίβα, CFG ↔ PDA.
• Λήμμα άντλησης για CFL: s = uvxyz, |vxy| ≤ p, |vy| ≥ 1. Ίδια δομή παιχνιδιού, περισσότερες περιπτώσεις (πού «πέφτει» το vxy).

4. Μηχανές Turing & αποκρισιμότητα

• Περιγραφή ΜΤ σε τρία επίπεδα: τυπική (δ), υλοποίησης (κινήσεις κεφαλής), υψηλού επιπέδου. Ακολούθησε όποιο ζητά το μάθημα.
• Παραλλαγές (πολυταινιακή, μη ντετερμινιστική) και γιατί είναι ισοδύναμες.
• Αποκρίσιμες / αναγνωρίσιμες / μη αναγνωρίσιμες. Διαγωνοποίηση για το A_TM.
• Αναγωγές: για να δείξεις ότι το B είναι μη αποκρίσιμο, ανάγεις ένα γνωστό μη αποκρίσιμο A στο B (A ≤ B): «αν είχαμε αποφαινόμενο για το B, θα φτιάχναμε αποφαινόμενο για το A». Η κατεύθυνση είναι το πιο συχνό λάθος. Θεώρημα Rice: πότε εφαρμόζεται (μη τετριμμένη σημασιολογική ιδιότητα της γλώσσας).

5. Πολυπλοκότητα

P, NP (πιστοποιητικό + επαληθευτής σε πολυωνυμικό χρόνο), NP-πληρότητα (Cook–Levin, SAT → 3SAT → CLIQUE/VERTEX-COVER/IS, HAMPATH…), αναγωγές πολυωνυμικού χρόνου με απόδειξη και των δύο κατευθύνσεων. Δες και algorithmoi-polyplokotita.

6. Αποδείξεις (Διακριτά Μαθηματικά)

Δομή απάντησης:

1. Τι θέλουμε να δείξουμε, γραμμένο τυπικά (ποσοδείκτες!).
2. Μέθοδος: ευθεία, αντιθετοαντίστροφη, απαγωγή σε άτοπο, επαγωγή (απλή/ισχυρή/δομική), περιπτώσεις, κατασκευαστική, διαγωνοποίηση, περιστερώνας.
3. Απόδειξη με αριθμημένα βήματα και αιτιολόγηση σε καθένα.
4. ∎

Στην επαγωγή: βάση, επαγωγική υπόθεση γραμμένη ρητά, επαγωγικό βήμα που τη χρησιμοποιεί εμφανώς.

Συνδυαστική (μεταθέσεις, συνδυασμοί, εγκλεισμός-αποκλεισμός, γεννήτριες συναρτήσεις, αναδρομικές σχέσεις): επαλήθευσε αριθμητικά για μικρά n με Python/sympy (δες sympy). Γράφοι: δες networkx για πειραματισμό.

Για τυπική επαλήθευση αποδείξεων σε Lean: writing-lean-proofs.

7. LaTeX

Αυτόματα με TikZ: \usetikzlibrary{automata, positioning, arrows.meta}, κόμβοι state, initial, accepting. Ποσοδείκτες και σύνολα: \forall, \exists, \Sigma^*, \varepsilon, \{ a^n b^n \mid n \ge 0 \}. Ελληνικά: latex-ellinika.