Adobe PDF (5.33 MB)
Brochure
Download
Title Details:
Θεωρία υπολογισμού και εφαρμογές
Authors: Katsaros, Panagiotis
Reviewer: Stamelos, Ioannis
Subject: MATHEMATICS AND COMPUTER SCIENCE > COMPUTER SCIENCE > COMPUTATIONAL SCIENCE
Keywords:
Languages
Automata
Grammars
Computability
Computational Complexity
Description:
Abstract:
Η Θεωρία Υπολογισμού αναπτύχθηκε για να μελετηθούν θεμελιώδη ζητήματα σχετικά με την έννοια του υπολογισμού και τις δυνατότητες των υπολογιστικών μας μηχανών. Ο υπολογισμός είναι ένα φυσικό φαινόμενο, που εκτελείται σε ένα κλειστό σύστημα που το ονομάζουμε υπολογιστή. Ποιοι υπολογισμοί είναι πραγματοποιήσιμοι και ποιοι υπολογισμοί είναι αδύνατοι; Πώς μπορούμε να ξέρουμε αν ένα δοθέν πρόβλημα μπορεί να επιλυθεί και αν αυτό μπορεί να γίνει επαρκώς γρήγορα;
Για να απαντηθούν τα παραπάνω ερωτήματα, οι επιστήμονες εμπνέυστηκαν αφαιρετικά μοντέλα υπολογισμού, όπως οι αναδρομικές συναρτήσεις, ο λογισμός-λ, οι μηχανές Turing και οι μηχανές πεπερασμένων καταστάσεων. Ο ορισμός των μοντέλων υπολογισμού χαρακτηρίζεται από μία μαθηματική αυστηρότητα, που είναι αναγκαία για την απόδειξη αποτελεσμάτων που απαντούν στα ερωτήματα που τέθηκαν.
Η Μηχανή Turing, ένα θεωρητικό μοντέλο μηχανής, που πρότεινε ο Alan Turing το 1936 έχει αποδειχθεί ως το μέχρι σήμερα πιο εκφραστικό μοντέλο, καθώς αυτό μπορεί να αναπαραστήσει τον οποιοδήποτε υπολογισμό μιας υπολογιστικής μηχανής. Οι μηχανές πεπερασμένων καταστάσεων συνδυάζουν την απλότητα της αναπαράστασης του υπολογισμού με σημαντικές δυνατότητες έκφρασης υπολογισμών και γι αυτό έχουν πολλές εφαρμογές στη σχεδίαση και ανάλυση της συμπεριφοράς συστημάτων όπως οι αυτόματες μηχανές πώλησης, τα ηλεκτρονικά παιχνίδια, οι μονάδες ελέγχου των CPUs και άλλες εφαρμογές όπως η ανάλυση κειμένου, η ανάλυση πρωτοκόλλων δικτύων και η επεξεργασία φυσικής γλώσσας.
Διάφορες επεκτάσεις μοντέλων υπολογισμού όπως αυτά που αναφέρθηκαν βρίσκουν επίσης εφαρμογή στη μελέτη βιολογικών συστημάτων και ενσωματωμένων συστημάτων, που αλληλεπιδρούν με το περιβάλλον σε πραγματικό χρόνο.
Το ηλεκτρονικό βιβλίο "Θεωρία Υπολογισμού και Εφαρμογές" είναι μία πρωτότυπη παρουσίαση των βασικών αποτελεσμάτων της Θεωρίας Υπολογισμού διανθισμένη με πλήθος εφαρμογών από διάφορα πεδία, προσομοιώσεις, κριτήρια αξιολόγησης, καθώς και εκτεταμένο πολυμεσικό και διαδραστικό περιεχόμενο.
Linguistic Editors: Pappas, Vasileios
Technical Editors: Stachtiari, Emmanouela
Type: Undergraduate textbook
Creation Date: 2015
Item Details:
ISBN 978-960-603-406-0
License: http://creativecommons.org/licenses/by-nc-nd/3.0/gr
Handle http://hdl.handle.net/11419/5744
Bibliographic Reference: Katsaros, P. (2015). Θεωρία υπολογισμού και εφαρμογές [Undergraduate textbook]. Kallipos, Open Academic Editions. http://hdl.handle.net/11419/5744
Language: Greek
Consists of: 1. Κανονικές Γλώσσες και Πεπερασμένα Αυτόματα
2. Ελαχιστοποίηση και Μη Κανονικές Γλώσσες
3. Γλώσσες και Γραμματικές Χωρίς Συμφραζόμενα
4. Αυτόματα Στοίβας και Γλώσσες που δεν είναι Χωρίς Συμφραζόμενα
5. Μηχανές Turing
6. Υπολογίσιμες Συναρτήσεις
7. Επιλυσιμότητα και Μη Επιλυσιμότητα
8. Υπολογιστική Πολυπλοκότητα
9. NP-πληρότητα
10. Γλώσσες και Υπολογισμοί
Publication Origin: Kallipos, Open Academic Editions