HY 280

• Περιεχόμενο του Μαθήματος
• Διδάσκων
• Μεταπτυχιακοί Βοηθοί
• Βιβλιογραφία
• Για αναζήτηση σε δικτυακούς τόπους
• Σημειώσεις
• Ασκήσεις
• Βαθμοί
• Τρόπος Εξέτασης
• Ανακοινώσεις
• Ροη Μαθημάτων



---

Περιεχόμενο τουΜαθήματος:

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

Το μάθημα πέραν της εισαγωγής, χωρίζεται σε τρία μέρη:

• την θεωρία των πεπερασμένων αυτομάτων και κανονικών γραμματικών
• την θεωρία των αυτομάτων με στοίβα και των γραμματικών χωρίς συμφραζόμενα
• την βασική θεωρία υπολογισιμότητας

Το όλο «πνεύμα» του μαθήματος είναι να καταδειχθεί ότι για την θεμελίωση της έννοιας του «υπολογισμού» των σχετικών προγραμματικών συμβολισμών (και της σχετικής τεχνολογίας) αρκούν ελάχιστες βάσεις - για την ακρίβεια αρκεί η θεωρία των φυσικών αριθμών - και ότι η περιοχή αυτή περιέχει πολλά απροσδόκητα και ενδιαφέροντα αποτελέσματα για τον μελετητή.

Διδάσκων:

Το μάθημα θα διδαχθεί από τον κ. Γρηγόρη Αντωνίου (ga@csd.uoc.gr), μόνιμο Καθηγητή του Τμήματος Επιστήμης Υπολογιστών του Πανεπιστημίου Κρήτης.
 

Μεταπτυχιακοί Βοηθοί:

• Κωνσταντίνος Παπαθεοδώρου (cpapath@csd.uoc.gr)
• Χρυσή Φιλιππάκη (filipaki@csd.uoc.gr)

Βιβλιογραφία:

Προτείνεται το παρακάτω βιβλίο:
Hopcroft, Motwani, Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley 2001.

Για αναζήτησησε δικτυακούς τόπους οι εξής λέξεις κλειδιά ίσως σας φανούν χρήσιμες:

• finite automata
• regular grammars
• regular expressions
• push down automata
• context free grammars
• formal languages
• theory of computation
• recursive functions
• uncomputability


  και μερικές μηχανές αναζήτησης:

• www.altavista.com
• www.google.com
• www.go.com

        Τα παρακάτω links είναι on-line simulators για διάφορες από τις μηχανές που θα μελετηθούν στο μάθημα:

• Για finite automata:
  http://www. cosc.canterbury.ac.nz/people/mukundan/thco/DFA.html 
  http://www.sims.berkeley.edu/~christin/dfa/
  http://www.users.csbsju.edu/~cburch/proj/autosim/
  http://www.cs.montana.edu/~dynalab/fsa/fsa.html


• Για push-down automata:
  http://www.cs.iitm.ernet.in/tell/automata/Automata/pda.html


• Για Turing machines:
  http://www.turing.org.uk/turing/scrapbook/tmjava.html
  http://wap03.informatik.fh-wiesbaden.de/weber1/turing/tm.html
  http://www.scit.wlv.ac.uk/~cm1970/tmachine.html

Σημειώσεις:

0. Εισαγωγή, σε pdf και ps
1. Γραμματικές Chomsky, σε pdf και ps - Λύσεις Παραδειγμάτων
2. Γλώσσες Τύπου 3 (Κανονικές Γλώσσες), σε pdf και ps
3. Γλώσσες Τύπου 2 (Γλώσσες Χωρίς Συμφραζόμενα), σε pdf και ps
4. Υπολογισιμότητα, σε pdf και ps

Ασκήσεις:

Σετ ασκήσεων 1 - Λύσεις

Σετ ασκήσεων 2 - Λύσεις 1ης άσκησης - Λύσεις 2ης άσκησης - Επιπλέον Παραδείγματα με Πεπερασμένα Αυτόματα


Σετ ασκήσεων 3 - Λύσεις 3ης άσκησης

Βαθμοί:

Βαθμολογία Προόδου

Τελική Βαθμολογία




Βαθμολογία Εξεταστικής Σεπτεμβρίου




Τρόπος εξέτασης:

Θα υπάρξει εξέταση προόδου με βάρος 50%

Το βάρος της τελικής εξέτασης θα είναι 50%

Κατά την διάρκεια των γραπτών εξετάσεων δεν επιτρέπεται κανένα βοήθημα.



Ανακοινώσεiς:





Ροή Μαθημάτων:

21/9	Μ	Εισαγωγή, οργανωτικά
23/9	Μ	Γλώσσες και γραμματικές
25/9	Μ	Ορισμός γραμματικής
28/9	Μ	Παραδείγματα γραμματικών
30/9	Μ	Απόδειξη ορθότητας γραμματικών
7/10	Μ	Ιεραρχία Chomsky, γλώσσες τύπου 0
9/10	Μ	Γλώσσες τύπου 1
12/10	Μ	Πεπερασμένα αυτόματα
14/10	Μ	Πεπερασμένα αυτόματα (2)
19/10	Φ	Γλώσσες και γραμματικές
23/10	Φ	Γλώσσες και γραμματικές (2)
30/10	Φ	Πεπερασμένα Αυτόματα
2/11	Μ	Ντετερμινιστικά & μη αυτόματα, ιδιότητες κλειστότητας κανονικών γλωσσών
4/11	Μ	Λήμμα άντλησης κανονικών γλωσσών
6/11	Μ	Λήμμα άντλησης κανονικών γλωσσών (2)
9/11	Φ	Λήμμα άντλησης
13/11	Μ	TEST: Εξέταση προόδου προηγούμενης χρονιάς
14/11	Μ	Εξέταση προόδου
18/11	Μ	Κανονικές μορφές γραμματικών τύπου 2
20/11	Μ	Ιδιότητες κλειστότητας γλωσσών τύπου 2
25/11	Φ	Λύσεις θεμάτων εξέτασης προόδου
27/11	Μ	Λήμμα Άντλησης για γλώσσες τύπου 2
30/11	Μ	Λήμμα Άντλησης για γλώσσες τύπου 2 (2)
2/12	Μ	Αυτόματα με στοίβα


* όπου: Μ: Μάθημα, Φ: Φροντιστήριο , Ε: Εξέταση

---

Για τυχόν απορίες στείλτε e-mail στην λίστα →