ΠΛΗ30: Θεμελιώσεις Eπιστήμης Υπολογιστών

Κωδικός ΘΕ: ΠΛΗ30

Πιστωτικές Μονάδες ECTS:
18

Τύπος ΘΕ:
Υποχρεωτική

Χαρακτηρισμός ΘΕ:
Επιστημονικής Περιοχής (ΕΠ)

Έτος που προσφέρεται:
Τρίτο (3ο)

Συντονιστής ΘΕ:
ΧΡΗΣΤΟΣ ΖΑΡΟΛΙΑΓΚΗΣ

Γλώσσα Διδασκαλίας:
Ελληνική

Γενική Περιγραφή της ΘΕ:
Ο σκοπός της ΘΕ είναι ο εξής, Όπως όλες οι επιστήμες, η επιστήμη υπολογιστών έχει τα δικά της βασικά ερωτήματα όπως: Τι είναι αλγόριθμος; Ποια προβλήματα είναι δυνατόν να λυθούν με υπολογιστές; Πότε ένας αλγόριθμος είναι πρακτικά υλοποιήσιμος; Σκοπός λοιπόν της ΘΕ είναι να μάθουν οι φοιτητές τις απαντήσεις στα βασικά αυτά ερωτήματα. Οι απαντήσεις αυτές αποτελούν την κομψή και βασική θεμελίωση της επιστήμης υπολογιστών

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

Γνωστικά αντικείμενα της ΘΕ:

1. Αλγόριθμοι και Πολυπλοκότητα
2. Θεωρία Υπολογισμού
3. Αυτόματα και Τυπικές Γλώσσες

Διδακτικό υλικό:
Οι Εκδόσεις του ΕΑΠ για την ΘΕ είναι διαθέσιμες εδώ!

Προαπαιτούμενα: Οι φοιτητές μπορούν να δηλώνουν μαζί τις ΘΕ ΠΛΗ12 και ΠΛΗ20 ή ΠΛΗ20 και ΠΛΗ30, εφόσον έχουν δηλώσει κατά το προηγούμενο ακαδημαϊκό έτος την ΠΛΗ12 ή την ΠΛΗ20 αντίστοιχα και την επαναλαμβάνουν με υποχρέωση μόνο τελικών εξετάσεων.

Μέθοδος Διδασκαλίας:
Εξ αποστάσεως εκπαίδευση με διεξαγωγή πέντε Ομαδικών Συμβουλευτικών Συναντήσεων κατά τη διάρκεια του ακαδημαϊκού έτους σε Σαββατοκύριακα.

Αξιολόγηση: Εκπόνηση γραπτών εργασιών κατά τη διάρκεια του ακαδημαϊκού έτους ο μέσος όρος των βαθμών των οποίων συμμετέχει στη διαμόρφωση του τελικού βαθμού της ΘΕ κατά 30%, εφόσον υπάρξει προβιβάσιμος στις τελικές ή επαναληπτικές εξετάσεις. Τελικές γραπτές εξετάσεις ο βαθμός των οποίων συμμετέχει στη διαμόρφωση του τελικού βαθμού της ΘΕ κατά 70%. Για περισσότερες πληροφορίες πιέστε εδώ!

Main Menu