HY 280

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



---

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

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

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

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

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

Διδάσκων:

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

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

• Βασίλης Ευθυμίου (vefthym@csd.uoc.gr)
• Ηλίας Ταχμαζίδης (tahmazid@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
Extra ασκήσεις με αυτόματα - Λύσεις
Σετ ασκήσεων 3 - Λύσεις

Βαθμοί:

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




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

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

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

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

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

Η εξέταση προόδου θα γίνει την Πέμπτη 3/11/2011 στις

19:00 έως 20:30 στα Αμφιθέατρα A, B και στις αίθουσες Θ201, Θ202, Θ206, Θ207, Λ202, Λ206.

---

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