Εκπαιδευτικό Αντικείμενο:
Σκοπός της θεματικής ενότητας είναι η εισαγωγή του / της φοιτητή/-τριας να έχουν :
1) Αλγόριθμοι και Πολυπλοκότητα
2) Θεωρία υπολογισμού
3) Αυτόματα και Τυπικές Γλώσσες.
Τα Μαθησιακά Αποτελέσματα διαμερίζονται σε 3 βαθμίδες
Α) Γνώση και Κατανόηση,
Β) Δεξιότητες Εφαρμογής
Γ) Δεξιότητες Ανάλυσης και Σύνθεσης.
Εμπειρία:
Ο καθηγητής θα πρέπει να μπορεί να γνωρίζει
1.Να περιγράφουν απλούς αλγορίθμους σε ψευδοκώδικα και να εξηγούν τη λειτουργία τους, να χρησιμοποιούν ασυμπτωτικούς συμβολισμούς, να υπολογίζουν χρόνο εκτέλεσης χειρότερης περίπτωσης, να διατυπώνουν και επιλύουν αναδρομικές εξισώσεις να διατυπώνουν τις αρχές σχεδιασμού αλγορίθμων Διαίρει και βασίλευε, Απληστίας, Δυναμικού Προγραμματισμού και τις τεχνικές διάσχισης γραφημάτων Πρώτα σε Βάθος και Πρώτα σε Πλάτος.
2. Να περιγράφουν και να ορίζουν τυπικά μια μηχανή Turing και τις σχετικές με αυτή έννοιες (Υπολογισμοί, Συνάρτηση, Γραμματική Χωρίς Περιορισμούς, Μ-Αναδρομική Συνάρτηση), να καταγράφουν τα διαδοχικά βήματα υπολογισμού, να ορίζουν διαισθητικά και τυπικά την έννοια του αλγορίθμου, να διατυπώνουν το πρόβλημα του τερματισμού, να περιγράφουν την καθολική μηχανή Turing, να αναφέρουν μερικά γνωστά μη επιλύσιμα προβλήματα, να περιγράφουν τη διαδικασία της χελιδονοουράς και τις πολυπλοκότητες χρόνου, να ορίζουν τις κλάσεις πολυπλοκότητας χρόνου DTIME ΚΑΙ NTIME και τις κλάσεις P, NP, και EXP, να ορίζουν ισοδύναμα την κλάση NP μέσω ενός πολυωνυμικού επαληθευτή και σύντομου πιστοποιητικού, τις έννοιες της πληρότητας, της ευκολίας και της σκληρότητας προβλημάτων, να περιγράφουν το ρόλο και τη χρήση των αναγωγών, να ορίζουν τις κλάσεις πολυπλοκότητας χώρου PSPACE και EXPSPACE, τι είναι μια χώρο κατασκευάσιμη και μια χρόνο κατασκευάσιμη συνάρτηση, να διατυπώνουν και να αποδεικνύουν τα θεωρήματα ιεραρχίας χώρου και χρόνου, να περιγράφουν τον προσεγγιστικό αλγόριθμο, τι είναι μια πιθανοκρατική μηχανή Turing, να διακρίνουν τα χαρακτηριστικά των πιθανοκρατικών αλγορίθμων Monte Carlo και Las Vegas.
3. Να περιγράφουν την έννοια της γλώσσας, να περιγράφουν τις βασικές πράξεις τους και τι είναι κανονική έκφραση, να αναφέρουν τα βασικά χαρακτηριστικά μιας μηχανής πεπερασμένων καταστάσεων και να περιγράφουν τη διαδικασία αναγνώρισης μιας συμβολοσειράς, να ορίζουν ένα πεπερασμένο αυτόματο και να εξηγούν τι είναι η συνάρτηση μετάβασης, να περιγράφουν τη γλώσσα που γίνεται δεκτή από ένα αυτόματο, τη γλώσσα που γίνεται δεκτή από ένα μη ντετερμινιστικό αυτόματο, να αναφέρουν τι είναι το Λήμμα Άντλησης και πώς χρησιμοποιείται, τι είναι μια γραμματική ανεξάρτητη συμφραζόμενων (ΑΣ), τι είναι μεταβλητές, τερματικά σύμβολα και παραγωγές, να καταγράφουν βασικά χαρακτηριστικά ενός ΑΣ και να περιγράφουν τη διαδικασία αναγνώρισης μιας συμβολοσειράς, να εξηγούν πώς ορίζεται η συνάρτηση μετάβασης του, να αναφέρουν τα δύο είδη αναγνώρισης συμβολοσειρών καθώς και τις αντίστοιχες γλώσσες που γίνονται δεκτές από αυτά τα αυτόματα, να αναφέρουν πώς ορίζεται ένα ντετερμινιστικό αυτόματο στοίβας, τι είναι το Λήμμα Άντλησης και πως χρησιμοποιείται, πώς μπορεί να μετατραπεί μια γραμματική σε μια ισοδύναμη που δεν περιέχει μοναδιαίους κανόνες και να εξηγούν πώς χρησιμοποιείται το Λήμμα Άντλησης για γραμματικές ανεξάρτητες συμφραζομένων.
4. Να χρησιμοποιούν την ασυμπτωτική ανάλυση σε υπολογισμούς πολυπλοκότητας επαναληπτικών και αναδρομικών αλγορίθμων, να υπολογίζουν ακριβείς ασυμπτωτικές εκτιμήσεις για τη λύση αναδρομικών εξισώσεων, να εφαρμόζουν τη μέθοδο «διαίρει και βασίλευε» για την επίλυση προβλημάτων ενδιάμεσου βαθμού δυσκολίας, να εφαρμόζουν τη μέθοδο του δυναμικού προγραμματισμού και τη μέθοδο της, να αναπαριστούν ένα γράφημα με την λίστες γειτονιάς και τον πίνακα γειτονιάς, να εφαρμόζουν τις τεχνικές Ψαξίματος Πρώτα σε Βάθος και του Ψαξίματος Πρώτα σε Πλάτος.
5. Να αποδεικνύουν ότι το πρόβλημα τερματισμού είναι μη επιλύσιμο με τη μέθοδο της διαγωνιοποίησης, να αποδεικνύουν σημαντικές ιδιότητες των Turing αποφασίσιμων και των Turing αποδεκτών γλωσσών, να αποδεικνύουν ότι είναι NP- πλήρες το πρόβλημα της ικανοποιησιμότητας SAT, να αποδεικνύουν ότι ένα πρόβλημα είναι Turing αποφασίσιμο ή όχι, να κατατάσσουν ένα πρόβλημα στις κλάσεις P, NP και NPC, να αποδεικνύουν την ύπαρξη PSPACE- πλήρη προβλημάτων με αναγωγές πολυωνυμικού χρόνου (πρόβλημα QSAT), να κατατάσσουν προβλήματα στις κλάσεις λογαριθμικού χρόνου.
6. Να αποδεικνύουν τις ιδιότητες κλειστότητας κανονικών γλωσσών κάτω από ένωση, τομή, παράθεση και αστερίσκο Kleene, να αποδεικνύουν αν δύο εκφράσεις αντιστοιχούν στην ίδια γλώσσα, να εξηγούν γιατί κάθε πεπερασμένη γλώσσα είναι κανονική, να αποδεικνύουν αν μια γλώσσα είναι κανονική ή όχι, να μετατρέπουν ένα μη ντετερμινιστικό πεπερασμένο αυτόματο σε ντετερμινιστικό, να αποδεικνύουν αν μια γλώσσα είναι ανεξάρτητη συμφραζόμενων ή όχι, να σχεδιάζουν αυτόματα στοίβας, να εφαρμόζουν το Λήμμα άντλησης για γλώσσες ανεξάρτητες συμφραζομένων.
Γνωστικά αντικείμενα της ΘΕ:
Ρόλος στην εκπαίδευση: