Η ΠΛΗ30 Θεμελιώσεις Επιστήμης Υπολογιστών, ίσως είναι η πιο σοβαρή, κομψή, και δύσκολη ενότητα του ΕΑΠ. Αποτελεί την ουσία των σπουδών σας, αφού διαπραγματεύεται θεωρίες που θεμελιώνουν την πληροφορική ως επιστήμη. Απαιτεί ανοιχτή σκέψη, ωριμότητα και πολύ μα πολύ διάβασμα. Σε αντίθεση με άλλες ενότητες τα βιβλία της είναι καλογραμμένα, και δεν αφήνουν "κενά" ύλης. Βέβαια απαιτείται προσπάθεια μελέτης ίσως πολύ περισσότερο από άλλες ενότητες γιατί υπάρχει το πάντρεμα των μαθηματικών αποδείξεων με την φιλοσοφική σκέψη.

Το ευχάριστο είναι ότι στατιστικά όποιοι ολοκλήρωσαν με επιτυχία αυτή την ενότητα οδηγήθηκαν και σε πτυχίο. 

Να εξηγούν τη λειτουργία τους, να χρησιμοποιούν ασυμπτωτικούς συμβολισμούς, να υπολογίζουν χρόνο εκτέλεσης χειρότερης περίπτωσης, να διατυπώνουν και επιλύουν αναδρομικές εξισώσεις να διατυπώνουν τις αρχές σχεδιασμού αλγορίθμων Διαίρει και βασίλευε, Απληστίας, Δυναμικού Προγραμματισμού και τις τεχνικές διάσχισης γραφημάτων Πρώτα σε Βάθος και Πρώτα σε Πλάτος.

Να ορίζουν τυπικά μια μηχανή Turing και τις σχετικές με αυτή έννοιες (Υπολογισμοί, Συνάρτηση, Γραμματική Χωρίς Περιορισμούς, Μ-Αναδρομική Συνάρτηση), να καταγράφουν τα διαδοχικά βήματα υπολογισμού, να ορίζουν διαισθητικά και τυπικά την έννοια του αλγορίθμου, να διατυπώνουν το πρόβλημα του τερματισμού, να περιγράφουν την καθολική μηχανή Turing, να αναφέρουν μερικά γνωστά μη επιλύσιμα προβλήματα, να περιγράφουν τη διαδικασία της χελιδονοουράς και τις πολυπλοκότητες χρόνου, να ορίζουν τις κλάσεις πολυπλοκότητας χρόνου DTIME ΚΑΙ NTIME και τις κλάσεις P, NP, και EXP, να ορίζουν ισοδύναμα την κλάση NP μέσω ενός πολυωνυμικού επαληθευτή και σύντομου πιστοποιητικού, τις έννοιες της πληρότητας, της ευκολίας και της σκληρότητας προβλημάτων, να περιγράφουν το ρόλο και τη χρήση των αναγωγών, να ορίζουν τις κλάσεις πολυπλοκότητας χώρου PSPACE και EXPSPACE, τι είναι μια χώρο κατασκευάσιμη και μια χρόνο κατασκευάσιμη συνάρτηση, να διατυπώνουν και να αποδεικνύουν τα θεωρήματα ιεραρχίας χώρου και χρόνου, να περιγράφουν τον προσεγγιστικό αλγόριθμο, τι είναι μια πιθανοκρατική μηχανή Turing, να διακρίνουν τα χαρακτηριστικά των πιθανοκρατικών αλγορίθμων Monte Carlo και Las Vegas. 

Να περιγράφουν την έννοια της γλώσσας, να περιγράφουν τις βασικές πράξεις τους και τι είναι κανονική έκφραση, να αναφέρουν τα βασικά χαρακτηριστικά μιας μηχανής πεπερασμένων καταστάσεων και να περιγράφουν τη διαδικασία αναγνώρισης μιας συμβολοσειράς, να ορίζουν ένα πεπερασμένο αυτόματο και να εξηγούν τι είναι η συνάρτηση μετάβασης, να περιγράφουν τη γλώσσα που γίνεται δεκτή από ένα αυτόματο, τη γλώσσα που γίνεται δεκτή από ένα μη ντετερμινιστικό αυτόματο, να αναφέρουν τι είναι το Λήμμα Άντλησης και πώς χρησιμοποιείται, τι είναι μια γραμματική ανεξάρτητη συμφραζόμενων (ΑΣ), τι είναι μεταβλητές, τερματικά σύμβολα και παραγωγές, να καταγράφουν βασικά χαρακτηριστικά ενός ΑΣ και να περιγράφουν τη διαδικασία αναγνώρισης μιας συμβολοσειράς, να εξηγούν πώς ορίζεται η συνάρτηση μετάβασης του, να αναφέρουν τα δύο είδη αναγνώρισης συμβολοσειρών καθώς και τις αντίστοιχες γλώσσες που γίνονται δεκτές από αυτά τα αυτόματα, να αναφέρουν πώς ορίζεται ένα ντετερμινιστικό αυτόματο στοίβας, τι είναι το Λήμμα Άντλησης και πως χρησιμοποιείται, πώς μπορεί να μετατραπεί μια γραμματική σε μια ισοδύναμη που δεν περιέχει μοναδιαίους κανόνες και να εξηγούν πώς χρησιμοποιείται το Λήμμα Άντλησης για γραμματικές ανεξάρτητες συμφραζομένων.

πηγή ΕΑΠ