ΠΛΗ30 – Θεμελιώσεις Επιστήμης Η/Υ

ΠΛΗ 30: Θεμελιώσεις Επιστήμης Η/Υ
Γνωριμία με το αντικείμενο της Θ.Ε ΠΛΗ 30
4 Θέματα
Εισαγωγή στη Θ.Ε ΠΛΗ 30  (00:07:08)
Τι να προσέξω  (00:06:14)
Πλάνο μελέτης  (00:04:50)
Συμβουλές για τις εργασίες  (00:04:02)
1. Αλγόριθμοι και Πολυπλοκότητα - 1η Εργασία
* Καθοδήγηση 1ης Εργασίας
3 Θέματα
1η Εβδομάδα – μελέτη έως 13/10/19
2η Εβδομάδα – μελέτη έως 20/10/19
3η Εβδομάδα – μελέτη έως 27/10/19
Μάθημα 1ο: Ασυμπτωτικός Συμβολισμός και ταξινόμηση συναρτήσεων
10 Θέματα
Σημειώσεις [Ασυμπτωτικός Συμβολισμός Συναρτήσεων]
Επανάληψη σε δυνάμεις, λογαρίθμους, κανόνα de l’ Hospital  (00:19:45)
Ασυμπτωτικός Συμβολισμός (Ο, Ω, Θ)  (00:18:40)
Ασυμπτωτικός Συμβολισμός (ο, ω)  (00:09:22)
Ιεραρχία Βασικών Συναρτήσεων  (00:13:22)
Ταξινόμηση Συναρτήσεων – Μεθοδολογία  (00:10:33)
Άσκηση (Σύγκριση Συναρτήσεων – Παράδειγμα 2)  (00:17:38)
Άσκηση (Ταξινόμηση Συναρτήσεων – Παράδειγμα 3)  (00:15:59)
Άσκηση (Ασυμπτωτικός Υπολογισμός Αθροίσματος – Παράδειγμα 4)  (00:11:15)
Άσκηση (Σύγκριση Συναρτήσεων – Παράδειγμα 5)  (00:07:41)
Μάθημα 2ο:Αναδρομικές εξισώσεις
9 Θέματα
Εισαγωγή στις Αναδρομικές Εξισώσεις  (00:05:13)
Η Μέθοδος Επανάληψης  (00:17:22)
Άσκηση (Μέθοδος Επανάληψης – Παράδειγμα 2)  (00:18:10)
Η Μέθοδος του Δένδρου της Αναδρομής  (00:14:59)
Άσκηση (Δένδρο Αναδρομής – Παράδειγμα 4)  (00:10:39)
Άσκηση (Δένδρο Αναδρομής)  (00:15:22)
Θεώρημα Κυριαρχίας  (00:20:40)
Γενική Αντιμετώπιση Αναδρομικών Εξισώσεων  (00:08:42)
Άσκηση (Υπολογισμός Φραγμάτων – Παράδειγμα 8)  (00:11:59)
Μάθημα 3ο: Αλγόριθμοι ταξινόμησης
3 Θέματα
Τι είναι ένας ‘αλγόριθμος’; – Selection Sort  (00:24:25)
Insertion Sort  (00:19:00)
Merge Sort  (00:19:47)
Μάθημα 4ο: Διαίρει και Βασίλευε [Τεχνικές σχεδίασης αλγορίθμων]
5 Θέματα
Σημειώσεις [Διαίρει-και-Βασίλευε]
Γενική μορφή της μεθόδου – Quick Sort  (00:33:22)
Αλγόριθμος του Strassen για τον πολλαπλασιασμό πινάκων – Άλλοι Δ-&-Β αλγόριθμοι  (00:27:12)
Άσκηση (Διαίρει-και-Βασίλευε – Άσκηση1)  (00:11:05)
Άσκηση (Διαίρει-και-Βασίλευε – Άσκηση 2)  (00:17:09)
Μάθημα 5ο: Δυναμικός προγραμματισμός [Τεχνικές σχεδίασης αλγορίθμων]
7 Θέματα
Σημειώσεις [Δυναμικός Προγραμματισμός]
Γενική μορφή της μεθόδου – Ακολουθία Fibonacci  (00:16:23)
Πολλαπλασιασμός ακολουθίας πινάκων  (00:24:43)
Μέγιστη Κοινή Υπακολουθία  (00:25:51)
Άσκηση (Δυναμικός Προγραμματισμός – Άσκηση 1)  (00:20:47)
Άσκηση (Δυναμικός Προγραμματισμός – Άσκηση 2)  (00:20:17)
Άσκηση (Δυναμικός Προγραμματισμός – Άσκηση 3)  (00:20:54)
Μάθημα 6ο: Άπληστοι αλγόριθμοι[Τεχνικές σχεδίασης αλγορίθμων]
7 Θέματα
Σημειώσεις [Άπληστοι Αλγόριθμοι]
Γενική μορφή της μεθόδου – Επιλογή Ανταγωνιστικών Δραστηριοτήτων  (00:28:41)
Κωδικοποίηση Huffman  (00:13:58)
Ελάχιστο Συνδετικό Δενδρο (Prim – Kruskal)  (00:14:08)
Άσκηση (Άπληστοι Αλγόριθμοι – Άσκηση 1)  (00:08:42)
Άσκηση (Άπληστοι Αλγόριθμοι – Άσκηση 2)  (00:06:21)
Άσκηση (Άπληστοι Αλγόριθμοι – Άσκηση 3)  (00:12:02)
Μάθημα 7ο: Επανάληψη
5 Θέματα
Επαναληπτικό Διαγώνισμα [Ασυμπτωτικός Συμβολισμός – Αναδρομικές Εξισώσεις]
Λύσεις Διαγωνίσματος
Λύση Ερωτήματος 1  (00:30:06)
Λύση Ερωτήματος 2  (00:11:21)
Λύση Ερωτήματος 3  (00:03:54)
2. Κανονικές Γλώσσες - 2η Εργασία
Μάθημα 1ο: Κανονικές Εκφράσεις
9 Θέματα
Σωημειώσεις Μέρος 1 – Κανονικές Εκφράσεις
Αλφάβητα, Γλώσσες & Πράξεις Γλωσσών  (00:19:51)
Άσκηση (Πράξεις Γλωσσών – Παράδειγμα 1)  (00:09:03)
Κανονικές Εκφράσεις & Κανονικές Γλώσσες  (00:11:28)
Άσκηση (Κανονικές Εκφράσεις – Παράδειγμα 2)  (00:18:54)
Άσκηση (Κανονικές Εκφράσεις – Παράδειγμα 3)  (00:12:36)
Άσκηση (Κανονικές Εκφράσεις – Άσκηση 1)  (00:15:23)
Άσκηση (Κανονικές Εκφράσεις – Άσκηση 2)  (00:11:26)
Άσκηση (Κανονικές Γλώσσες – Άσκηση 3)  (00:09:02)
Μάθημα 2ο: Ντετερμινιστικά Πεπερασμένα Αυτόματα
8 Θέματα
Σημειώσεις Μέρος 2 – ΝΠΑ
Ντετερμινηστικά Πεπερασμένα Αυτόματα – Εισαγωγή  (00:20:51)
Τυπικός Ορισμός -Συνάρτηση δ  (00:25:44)
Άσκηση (ΝΠΑ – Παράδειγμα 6)  (00:07:22)
ΝΠΑ για το συμπλήρωμα, την τομή, την ένωση και τη διαφορά γλωσσών  (00:17:34)
Άσκηση (Κατασκευή ΝΠΑ – Άσκηση 1)  (00:23:55)
Άσκηση (Κατασκευή ΝΠΑ – Άσκηση 2)  (00:06:13)
Άσκηση (ΝΠΑ για την τομή, την ένωση & τη διαφορά – Άσκηση 3)  (00:11:55)
Μάθημα 3ο: Μη Ντετερμινιστικά Πεπερασμένα Αυτόματα και Μετατροπές Αυτομάτων
15 Θέματα
Σημειώσεις Μέρος 3ο ΜΠΑ
Σημειώσεις Μέρος 4ο ΜΠΑ – Μετατροπές
Μη Ντετερμινηστικά Πεπερασμένα Αυτόματα  (00:29:44)
Μη Ντετερμινηστικά Πεπερασμένα Αυτόματα με ε-κινήσεις  (00:20:03)
Μετατροπή κ.ε. σε ΜΠΑ-ε  (00:13:08)
Άσκηση (Μετατροπή κ.ε. σε Αυτόματο – Ασκήσεις 1, 2 & 3)  (00:15:41)
Μετατροπή ΜΠΑ-ε σε ΜΠΑ  (00:19:03)
Μετατροπή ΜΠΑ σε ΝΠΑ  (00:16:08)
Άσκηση (Μετατροπές Αυτομάτων – Άσκηση 4)  (00:08:08)
Άσκηση (Μετατροπές Αυτομάτων – Άσκηση 5)  (00:15:44)
Άσκηση (Μετατροπές Αυτομάτων – Άσκηση 6)  (00:19:23)
Άσκηση (Μετατροπές Αυτομάτων – Άσκηση 7)  (00:14:39)
Άσκηση (Μετατροπές Αυτομάτων – Άσκηση 8)  (00:04:24)
Άσκηση (Μετατροπές Αυτομάτων – Άσκηση 9)  (00:16:56)
Απλοποίηση Αυτομάτου  (00:15:39)
Μάθημα 4ο: Λήμμα Άντλησης για Κανονικές Γλώσσες
6 Θέματα
Σημειώσεις Μέρος 5ο Μη Μανονικές Γλώσσες
Λήμμα Άντλησης (για κανονικές γλώσσες)  (00:18:46)
Άσκηση (Λήμμα Άντλησης – Άσκηση 1)  (00:07:54)
Άσκηση (Λήμμα Άντλησης – Άσκηση 2)  (00:06:39)
Άσκηση (Λήμμα Άντλησης – Άσκηση 3)  (00:06:54)
Άσκηση (Λήμμα Άντλησης – Άσκηση 4)  (00:10:44)
Μάθημα 5ο: Τεχνικές απόδειξης για Μη Κανονικές Γλώσσες
7 Θέματα
Ιδιότητες Κλειστότητας Κανονικών Γλωσσών & Μη Κανονικές Γλώσσες  (00:07:46)
Άσκηση (Κλειστότητα Κανονικών Γλωσσών – Άσκηση 5)  (00:06:02)
Άσκηση (Κλειστότητα Κανονικών Γλωσσών – Άσκηση 6)  (00:07:20)
Άσκηση (Μη Κανονικές Γλώσσες – Άσκηση 7)  (00:17:28)
Διακρινόμενες Συμβολοσειρές  (00:26:40)
Άσκηση (Διακρινόμενες Συμβολοσειρές – Παράδειγμα 4)  (00:08:26)
Άσκηση (Διακρινόμενες Συμβολοσειρές – Άσκηση 8)  (00:12:00)
3. Γλώσσες Ανεξάρτητες Συμφραζομένων - 3η Εργασία
Μάθημα 1ο: Γλώσσες χωρίς συμφραζόμενα
10 Θέματα
Γλώσσες ΑΣ – Σημειώσεις
Γραμματικές & Γλώσσες Χωρίς Συμφραζόμενα  (00:19:25)
Ιδιότητες Κλειστότητας Γλωσσών Χωρίς Συμφραζόμενα  (00:11:15)
Άσκηση (Γλώσσες Χωρίς Συμφραζόμενα – Άσκηση 1)  (00:10:03)
Άσκηση (Γλώσσες Χωρίς Συμφραζόμενα – Άσκηση 2)  (00:03:06)
Άσκηση (Γλώσσες Χωρίς Συμφραζόμενα – Άσκηση 3)  (00:03:19)
Άσκηση (Γλώσσες Χωρίς Συμφραζόμενα – Άσκηση 4)  (00:04:40)
Άσκηση (Γλώσσες Χωρίς Συμφραζόμενα – Άσκηση 5)  (00:03:21)
Άσκηση (Γλώσσες Χωρίς Συμφραζόμενα – Άσκηση 6)  (00:03:40)
Απλοποίηση Γραμματικής  (00:10:43)
Μάθημα 2ο: Κανονικές Γραμματικές
3 Θέματα
Κανονικές Γλώσσες & Κανονικές Γραμματικές  (00:12:06)
Άσκηση (Κανονικές Γραμματικές – Άσκηση 7)  (00:02:46)
Άσκηση (Κανονικές Γραμματικές – Άσκηση 8)  (00:04:46)
Μάθημα 3ο: Ντετερμινιστικά Αυτόματα στοίβας
5 Θέματα
Ντετερμινηστικά Αυτόματα Στοίβας  (00:26:59)
Άσκηση (Ντετερμινιστικά Αυτόματα Στοίβας – Παράδειγμα 2)  (00:11:20)
Άσκηση (Ντετερμινιστικά Αυτόματα Στοίβας – Άσκηση 1)  (00:10:10)
Άσκηση (Ντετερμινιστικά Αυτόματα Στοίβας – Άσκηση 2)  (00:07:12)
Άσκηση (Ντετερμινιστικά Αυτόματα Στοίβας – Άσκηση 3)  (00:07:59)
Μάθημα 4ο: Μη ντετερμινιστικά αυτόματα στοίβας
4 Θέματα
Μη Ντετερμινηστικά Αυτόματα Στοίβας  (00:13:10)
Άσκηση (Μη Ντετερμινιστικά Αυτόματα Στοίβας – Άσκηση 4)  (00:05:53)
Άσκηση (Μη Ντετερμινιστικά Αυτόματα Στοίβας – Άσκηση 5)  (00:05:14)
Άσκηση (Μη Ντετερμινιστικά Αυτόματα Στοίβας – Άσκηση 6)  (00:07:41)
Μάθημα 5ο: Λήμμα Άντλησης για γλώσσες ΑΣ
3 Θέματα
Λήμμα Άντλησης (για γλώσσες χωρίς συμφραζόμενα)  (00:15:15)
Άσκηση (Λήμμα Άντλησης για Γραμματικές – Άσκηση 9)  (00:09:22)
Άσκηση (Λήμμα Άντλησης για Γραμματικές – Άσκηση 10)  (00:19:42)
4. Μηχανές Turing και Αποφασισιμότητα - 4η Εργασία
Μάθημα 1ο: Στοιχειώδεις ΜΤ και αναδρομικές συναρτήσεις
9 Θέματα
Σημειώσεις [Μηχανές Turing]
Εισαγωγή – Βασικοί Ορισμοί  (00:26:16)
Διαγράμματα Καταστάσεων & Στοιχειώδεις Μηχανές Turing  (00:23:13)
Άσκηση (Μηχανές Turing – Άσκηση 6)  (00:07:40)
Αναδρομικές Συναρτήσεις  (00:06:56)
Άσκηση (Αναδρομικές Συναρτήσεις – Άσκηση 1)  (00:03:51)
Άσκηση (Αναδρομικές Συναρτήσεις – Άσκηση 2)  (00:02:23)
Άσκηση (Αναδρομικές Συναρτήσεις – Άσκηση 3)  (00:07:26)
Άσκηση (Αναδρομικές Συναρτήσεις)  (00:14:58)
Μάθημα 2ο: Turing Αποφασίσιμες Γλώσσες
7 Θέματα
Σημειώσεις [Αποφασίσιμες Γλώσσες]
Turing-Αποφασίσιμες & Turing-Αποδεκτές Γλώσσες  (00:29:22)
Άσκηση (Turing-Αποφασίσιμες Γλώσσες – Άσκηση 4)  (00:04:42)
Άσκηση (Turing-Αποφασίσιμες Γλώσσες – Άσκηση 5)  (00:09:19)
Άσκηση (Turing-Αποφασίσιμες Γλώσσες – Άσκηση 6)  (00:06:25)
Άσκηση (Turing-Αποφασίσιμες Γλώσσες – Άσκηση 7)  (00:09:28)
Άσκηση (Turing-Αποφασίσιμες Γλώσσες)  (00:15:42)
Μάθημα 3ο: Καθολική ΜΤ
4 Θέματα
Σημειώσεις [Καθολική ΜΤ – κλειστότητα – η Γλώσσα Halt ]
Επεκτάσεις ΜΤ – Η θέση των Church & Turing – Καθολική ΜΤ  (00:11:02)
Η γλώσσα HALT  (00:06:53)
Αποδείξεις ιδιοτήτων κλειστότητας Turing-αποδεκτών γλωσσών  (00:12:47)
Μάθημα 4ο: Αναγωγές
7 Θέματα
Σημειώσεις [Μη αποφασίσιμες Γλώσσες]
Μη Επιλυσιμότητα & Αναγωγές  (00:31:25)
Μη Επιλυσιμότητα της EMPTY  (00:14:45)
Μη Επιλυσιμότητα της EXISTS  (00:09:46)
Μη Επιλυσιμότητα της ALL  (00:10:32)
Μη Επιλυσιμότητα της EQUAL  (00:11:36)
Απαριθμήσιμες & Λεξικογραφικά Απαριθμήσιμες Γλώσσες  (00:29:15)
Μάθημα 5ο: Sipser – [Νέο Βιβλίο]
2 Θέματα
Διαγνώσιμες Γλώσσες – Κανονικές και ΑΣ
Μη διαγνώσιμες Γλώσσες
5. Χρονική Πολυπλοκότητα - 5η Εργασία
Μάθημα 1ο: Κλάσεις πολυπλοκότητας
4 Θέματα
Κλάσεις Πολυπλοκότητας [Σημειώσεις]
Εισαγωγή στη Χρονική Πολυπλοκότητα – Το πρόβλημα της Ικανοποιησιμότητας (SAT)  (00:32:41)
Οι κλάσεις πολυπλοκότητας P, NP, NP-complete, EXP  (00:27:36)
Παραλλαγές του SAT – NP-πληρότητα των 3SAT, 1in3SAT & NAESAT  (00:33:16)
Μάθημα 2ο: Αναγωγές σε προβλήματα Λογικής
6 Θέματα
Αναγωγές σε προβλήματα Λογικής [Σημειώσεις]
NP-πληρότητα του 5SAT  (00:09:21)
NP-πληρότητα του NotAllZeroSAT  (00:08:12)
NP-πληρότητα του not-equal-to-t-SAT  (00:11:34)
NP-πληρότητα του MAXSAT  (00:05:11)
NP-πληρότητα του ALMOST SAT  (00:07:17)
Μάθημα 3ο: Αναγωγές σε προβλήματα Γραφημάτων
9 Θέματα
Αναγωγές σε προβλήματα Γραφημάτων [Σημειώσεις]
NP-πληρότητα του INDEPENDENT SET  (00:11:37)
NP-πληρότητα του CLIQUE  (00:06:58)
NP-πληρότητα του VERTEX COVER  (00:07:52)
NP-πληρότητα του GRAPH ISOMORPHISM  (00:06:27)
NP-πληρότητα του HAMILTON CYCLE  (00:08:20)
NP-πληρότητα του 7-COLORING  (00:12:31)
NP-πληρότητα του k-DENSEST SUBGRAPH  (00:05:40)
NP-πληρότητα του TRAVELING SALESMAN PROBLEM (TSP)  (00:07:06)
*Εβδομαδιαία Καθοδήγηση
Θεωρία Υπολογισμού
3 Θέματα
25η Εβδομάδα – [25-31 Μαρτίου]
28η Εβδομάδα – [15-21 Απριλίου]
Ολοκλήρωση ύλης
Ι : Αλγόριθμοι
Κεφ. 1ο: Μαθηματικό Υπόβαθρο
20 Θέματα
Σημειώσεις [Ασυμπτωτικός Συμβολισμός Συναρτήσεων]
Σημειώσεις [Αναδρομικές Εξισώσεις]
Επανάληψη σε δυνάμεις, λογαρίθμους, κανόνα de l’ Hospital  (00:19:45)
Ασυμπτωτικός Συμβολισμός (Ο, Ω, Θ)  (00:18:40)
Ασυμπτωτικός Συμβολισμός (ο, ω)  (00:09:22)
Ιεραρχία Βασικών Συναρτήσεων  (00:13:22)
Ταξινόμηση Συναρτήσεων – Μεθοδολογία  (00:10:33)
Άσκηση (Σύγκριση Συναρτήσεων – Παράδειγμα 2)  (00:17:38)
Άσκηση (Ταξινόμηση Συναρτήσεων – Παράδειγμα 3)  (00:15:59)
Άσκηση (Ασυμπτωτικός Υπολογισμός Αθροίσματος – Παράδειγμα 4)  (00:11:15)
Άσκηση (Σύγκριση Συναρτήσεων – Παράδειγμα 5)  (00:07:41)
Εισαγωγή στις Αναδρομικές Εξισώσεις  (00:05:13)
Η Μέθοδος Επανάληψης  (00:17:22)
Άσκηση (Μέθοδος Επανάληψης – Παράδειγμα 2)  (00:18:10)
Η Μέθοδος του Δένδρου της Αναδρομής  (00:14:59)
Άσκηση (Δένδρο Αναδρομής – Παράδειγμα 4)  (00:10:39)
Άσκηση (Δένδρο Αναδρομής)  (00:15:22)
Θεώρημα Κυριαρχίας  (00:20:40)
Γενική Αντιμετώπιση Αναδρομικών Εξισώσεων  (00:08:42)
Άσκηση (Υπολογισμός Φραγμάτων – Παράδειγμα 8)  (00:11:59)
Κεφ. 1ο: Λυμένα Θέματα Εξετάσεων & Επαναληπτικές Ασκήσεις
33 Θέματα
Επαναληπτικό Διαγώνισμα [Ασυμπτωτικός Συμβολισμός – Αναδρομικές Εξισώσεις]
Λύσεις Διαγωνίσματος
Λύση Ερωτήματος 1  (00:30:06)
Λύση Ερωτήματος 2  (00:11:21)
Λύση Ερωτήματος 3  (00:03:54)
Θέματα Ασυμπτωτικής Ιεράρχησης ΕΑΠ (Ιούνιος 2007 – Ιούλιος 2009)
Θέμα 1 (Ταξινόμηση Συναρτήσεων – Ιούνιος 2007)  (00:09:57)
Θέμα 2 (Ταξινόμηση Συναρτήσεων – Ιούλιος 2007)  (00:10:11)
Θέμα 3 (Ταξινόμηση Συναρτήσεων – Ιούνιος 2008)  (00:05:12)
Θέμα 4 (Ταξινόμηση Συναρτήσεων – Ιούλιος 2008)  (00:04:05)
Θέμα 5 (Ασυμπτωτικός Συμβολισμός – Ιούνιος 2009)  (00:07:18)
Θέμα 6 (Ταξινόμηση Συναρτήσεων – Ιούνιος 2009)  (00:09:49)
Θέμα 7 (Ταξινόμηση Συναρτήσεων – Ιούλιος 2009)  (00:09:13)
Θέμα 8 (Ταξινόμηση Συναρτήσεων – Ιούνιος 2010)  (00:10:15)
Θέματα Ασυμπτωτικής Ιεράρχησης ΕΑΠ (Ιούνιος 2010 – Ιούλιος 2012)
Θέμα 9 (Ταξινόμηση Συναρτήσεων – Ιούλιος 2010)  (00:07:41)
Θέμα 10 (Ταξινόμηση Συναρτήσεων – Ιούνιος 2011)  (00:13:39)
Θέμα 11 (Ταξινόμηση Συναρτήσεων – Ιούλιος 2011)  (00:16:53)
Θέμα 12 (Ταξινόμηση Συναρτήσεων – Ιούνιος 2012)  (00:08:52)
Θέμα 13 (Ταξινόμηση Συναρτήσεων – Ιούλιος 2012)  (00:07:21)
Θέματα Αναδρομικές Εξισώσεις ΕΑΠ (Ιούνιος 2006 – Ιούλιος 2009)
Θέμα 14 (Αναδρομικές Εξισώσεις – Ιούνιος 2006)  (00:11:16)
Θέμα 15 (Αναδρομικές Εξισώσεις – Ιούλιος 2006)  (00:09:01)
Θέμα 16 (Αναδρομικές Εξισώσεις – Ιούνιος 2007)  (00:19:52)
Θέμα 17 (Αναδρομικές Εξισώσεις – Ιούνιος 2008 & Ιούνιος 2009)  (00:07:47)
Θέμα 18 (Αναδρομικές Εξισώσεις – Ιούλιος 2008 Α)  (00:05:58)
Θέμα 19 (Αναδρομικές Εξισώσεις – Ιούλιος 2008 Β)  (00:06:03)
Θέματα Αναδρομικές Εξισώσεις ΕΑΠ (Ιούνιος 2010 – Ιούλιος 2012)
Θέμα 20 (Αναδρομικές Εξισώσεις – Ιούνιος 2010)  (00:15:10)
Θέμα 21 (Αναδρομικές Εξισώσεις – Ιούλιος 2010)  (00:16:36)
Θέμα 22 (Αναδρομικές Εξισώσεις – Ιούνιος 2011)  (00:15:27)
Θέμα 23 (Αναδρομικές Εξισώσεις – Ιούλιος 2011)  (00:13:00)
Θέμα 24 (Αναδρομικές Εξισώσεις – Ιούνιος 2012)  (00:26:46)
Κεφ. 2o: Αλγόριθμοι Ταξινόμησης
3 Θέματα
Τι είναι ένας ‘αλγόριθμος’; – Selection Sort  (00:24:25)
Insertion Sort  (00:19:00)
Merge Sort  (00:19:47)
Κεφ. 3ο: Τεχνικές Σχεδίασης Αλγορίθμων
20 Θέματα
Σημειώσεις [Διαίρει-και-Βασίλευε]
Σημειώσεις [Δυναμικός Προγραμματισμός]
Σημειώσεις [Άπληστοι Αλγόριθμοι]
Γενική μορφή της μεθόδου – Quick Sort  (00:33:22)
Αλγόριθμος του Strassen για τον πολλαπλασιασμό πινάκων – Άλλοι Δ-&-Β αλγόριθμοι  (00:27:12)
Άσκηση (Διαίρει-και-Βασίλευε – Άσκηση1)  (00:11:05)
Άσκηση (Διαίρει-και-Βασίλευε – Άσκηση 2)  (00:17:09)
Άσκηση (Διαίρει-και-Βασίλευε – Άσκηση 2)  (00:17:09)
Γενική μορφή της μεθόδου – Ακολουθία Fibonacci  (00:16:23)
Πολλαπλασιασμός ακολουθίας πινάκων  (00:24:43)
Μέγιστη Κοινή Υπακολουθία  (00:25:51)
Άσκηση (Δυναμικός Προγραμματισμός – Άσκηση 1)  (00:20:47)
Άσκηση (Δυναμικός Προγραμματισμός – Άσκηση 2)  (00:20:17)
Άσκηση (Δυναμικός Προγραμματισμός – Άσκηση 3)  (00:20:54)
Γενική μορφή της μεθόδου – Επιλογή Ανταγωνιστικών Δραστηριοτήτων  (00:28:41)
Κωδικοποίηση Huffman  (00:13:58)
Ελάχιστο Συνδετικό Δενδρο (Prim – Kruskal)  (00:14:08)
Άσκηση (Άπληστοι Αλγόριθμοι – Άσκηση 1)  (00:08:42)
Άσκηση (Άπληστοι Αλγόριθμοι – Άσκηση 2)  (00:06:21)
Άσκηση (Άπληστοι Αλγόριθμοι – Άσκηση 3)  (00:12:02)
Κεφ. 3ο: Λυμένα Θέματα Εξετάσεων & Επαναληπτικές Ασκήσεις
7 Θέματα
Επαναληπτικό Διαγώνισμα [Τεχνικές Σχεδίασης Αλγορίθμων]
Διαγώνισμα [Τεχνικές Σχεδίασης Αλγορίθμων] – Λύση Ερωτήματος 1  (00:21:13)
Διαγώνισμα [Τεχνικές Σχεδίασης Αλγορίθμων] – Λύση Ερωτήματος 2  (00:33:03)
Διαγώνισμα [Τεχνικές Σχεδίασης Αλγορίθμων] – Λύση Ερωτήματος 3  (00:13:23)
Θέμα 01 (Τεχνικές Σχεδίασης Αλγορίθμων – Ιούνιος 2011)  (00:28:31)
Θέμα 02 (Τεχνικές Σχεδίασης Αλγορίθμων – Ιούλιος 2011)  (00:31:18)
Θέμα 03 (Τεχνικές Σχεδίασης Αλγορίθμων – Ιούνιος 2012)  (00:33:52)
ΙΙ : Αυτόματα & Τυπικές Γλώσσες
Κεφ. 1ο: Κανονικές Γλώσσες & Πεπερασμένα Αυτόματα
45 Θέματα
Σημειώσεις [Γλώσσες – Πράξεις Γλωσσών – Κανονικές Εκφράσεις & Κανονικές Γλώσσες]
Σημειώσεις [Ντετερμινηστικά Πεπερασμένα Αυτόματα]
Σημειώσεις [Μη Ντετερμινηστικά Πεπερασμένα Αυτόματα (μέρος Α’)]
Σημειώσεις [Μη Ντετερμινηστικά Πεπερασμένα Αυτόματα (μέρος Β’)]
Σημειώσεις [Μη Κανονικές Γλώσσες – Λήμμα Άντλησης – Διακρινόμενες Καταστάσεις]
Αλφάβητα, Γλώσσες & Πράξεις Γλωσσών  (00:19:51)
Άσκηση (Πράξεις Γλωσσών – Παράδειγμα 1)  (00:09:03)
Κανονικές Εκφράσεις & Κανονικές Γλώσσες  (00:11:28)
Άσκηση (Κανονικές Εκφράσεις – Παράδειγμα 2)  (00:18:54)
Άσκηση (Κανονικές Εκφράσεις – Παράδειγμα 3)  (00:12:36)
Άσκηση (Κανονικές Εκφράσεις – Άσκηση 1)  (00:15:23)
Άσκηση (Κανονικές Εκφράσεις – Άσκηση 2)  (00:11:26)
Άσκηση (Κανονικές Γλώσσες – Άσκηση 3)  (00:09:02)
Ντετερμινηστικά Πεπερασμένα Αυτόματα – Εισαγωγή  (00:20:51)
Τυπικός Ορισμός -Συνάρτηση δ  (00:25:44)
Άσκηση (ΝΠΑ – Παράδειγμα 6)  (00:07:22)
ΝΠΑ για το συμπλήρωμα, την τομή, την ένωση και τη διαφορά γλωσσών  (00:17:34)
Άσκηση (Κατασκευή ΝΠΑ – Άσκηση 1)  (00:23:55)
Άσκηση (Κατασκευή ΝΠΑ – Άσκηση 2)  (00:06:13)
Άσκηση (ΝΠΑ για την τομή, την ένωση & τη διαφορά – Άσκηση 3)  (00:11:55)
Μη Ντετερμινηστικά Πεπερασμένα Αυτόματα  (00:29:44)
Μη Ντετερμινηστικά Πεπερασμένα Αυτόματα με ε-κινήσεις  (00:20:03)
Μετατροπή κ.ε. σε ΜΠΑ-ε  (00:13:08)
Άσκηση (Μετατροπή κ.ε. σε Αυτόματο – Ασκήσεις 1, 2 & 3)  (00:15:41)
Μετατροπή ΜΠΑ-ε σε ΜΠΑ  (00:19:03)
Μετατροπή ΜΠΑ σε ΝΠΑ  (00:16:08)
Άσκηση (Μετατροπές Αυτομάτων – Άσκηση 4)  (00:08:08)
Άσκηση (Μετατροπές Αυτομάτων – Άσκηση 5)  (00:15:44)
Άσκηση (Μετατροπές Αυτομάτων – Άσκηση 6)  (00:19:23)
Άσκηση (Μετατροπές Αυτομάτων – Άσκηση 7)  (00:14:39)
Άσκηση (Μετατροπές Αυτομάτων – Άσκηση 8)  (00:04:24)
Άσκηση (Μετατροπές Αυτομάτων – Άσκηση 9)  (00:16:56)
Απλοποίηση Αυτομάτου  (00:15:39)
Λήμμα Άντλησης (για κανονικές γλώσσες)  (00:18:46)
Άσκηση (Λήμμα Άντλησης – Άσκηση 1)  (00:07:54)
Άσκηση (Λήμμα Άντλησης – Άσκηση 2)  (00:06:39)
Άσκηση (Λήμμα Άντλησης – Άσκηση 3)  (00:06:54)
Άσκηση (Λήμμα Άντλησης – Άσκηση 4)  (00:10:44)
Ιδιότητες Κλειστότητας Κανονικών Γλωσσών & Μη Κανονικές Γλώσσες  (00:07:46)
Άσκηση (Κλειστότητα Κανονικών Γλωσσών – Άσκηση 5)  (00:06:02)
Άσκηση (Κλειστότητα Κανονικών Γλωσσών – Άσκηση 6)  (00:07:20)
Άσκηση (Μη Κανονικές Γλώσσες – Άσκηση 7)  (00:17:28)
Διακρινόμενες Συμβολοσειρές  (00:26:40)
Άσκηση (Διακρινόμενες Συμβολοσειρές – Παράδειγμα 4)  (00:08:26)
Άσκηση (Διακρινόμενες Συμβολοσειρές – Άσκηση 8)  (00:12:00)
Κεφ. 1ο: Θέματα Εξετάσεων & Επαναληπτικές Ασκήσεις
29 Θέματα
Θέματα σε Μη Κανονικές Γλώσσες ΕΑΠ (Ιούνιος 2006 – Ιούλιος 2012)
Θέμα 1 (Λήμμα Άντλησης – Ιούνιος 2006)  (00:08:47)
Θέμα 2 (Λήμμα Άντλησης – Ιούλιος 2006)  (00:06:40)
Θέμα 3 (Λήμμα Άντλησης – Ιούνιος 2007)  (00:05:51)
Θέμα 4 (Λήμμα Άντλησης – Ιούνιος 2007)  (00:06:31)
Θέμα 5 (Λήμμα Άντλησης – Ιούλιος 2007)  (00:08:03)
Θέμα 6 (Λήμμα Άντλησης – Ιούνιος 2008)  (00:05:27)
Θέμα 7 (Λήμμα Άντλησης – Ιούλιος 2008)  (00:04:58)
Θέμα 8 (Λήμμα Άντλησης – Ιούνιος 2009)  (00:13:12)
Θέμα 9 (Λήμμα Άντλησης – Ιούνιος 2010)  (00:06:29)
Θέμα 10 (Λήμμα Άντλησης – Ιούνιος 2011)  (00:16:54)
Θέμα 11 (Λήμμα Άντλησης – Ιούλιος 2011)  (00:04:31)
Θέμα 12 (Ιδιότητες Κλειστότητας – Ιούλιος 2011)  (00:09:32)
Θέματα σε Πεπερασμένα Αυτόματα (Ιούνιος 2006 – Ιούλιος 2009)
Θέμα 13 (Πεπερασμένα Αυτόματα – Ιούνιος 2006)  (00:29:13)
Θέμα 14 (Πεπερασμένα Αυτόματα – Ιούλιος 2006)  (00:15:48)
Θέμα 15 (Πεπερασμένα Αυτόματα – Ιούνιος 2007)  (00:11:55)
Θέμα 16 (Πεπερασμένα Αυτόματα – Ιούλιος 2007)  (00:12:11)
Θέμα 17 (Πεπερασμένα Αυτόματα – Ιούνιος 2008)  (00:13:37)
Θέματα σε Πεπερασμένα Αυτόματα (Ιούνιος 2010 – Ιούλιος 2012)
Θέμα 18 (Πεπερασμένα Αυτόματα – Ιούλιος 2008)  (00:09:03)
Θέμα 19 (Πεπερασμένα Αυτόματα – Ιούνιος 2009)  (00:09:31)
Θέμα 20 (Πεπερασμένα Αυτόματα – Ιούλιος 2009)  (00:07:04)
Θέμα 21 (Πεπερασμένα Αυτόματα – Ιούνιος 2010)  (00:20:50)
Θέμα 22 (Πεπερασμένα Αυτόματα – Ιούλιος 2010)  (00:17:49)
Θέμα 23 (Πεπερασμένα Αυτόματα – Ιούνιος 2011)  (00:22:38)
Θέμα 24 (Πεπερασμένα Αυτόματα – Ιούλιος 2011)  (00:20:40)
Θέμα 25 (Πεπερασμένα Αυτόματα – Ιούνιος 2012)  (00:23:53)
Θέμα 26 (Πεπερασμένα Αυτόματα – Ιούλιος 2012)  (00:17:27)
Κεφ. 2ο: Γλώσσες Ανεξάρτητες Συμφραζομένων & Αυτόματα Στοίβας
26 Θέματα
Σημειώσεις [Γλώσσες Ανεξάρτητες Συμφραζομένων – Γραμματικές – Λήμμα Άντλησης]
Σημειώσεις [Αυτόματα Στοίβας]
Γραμματικές & Γλώσσες Χωρίς Συμφραζόμενα  (00:19:25)
Ιδιότητες Κλειστότητας Γλωσσών Χωρίς Συμφραζόμενα  (00:11:15)
Άσκηση (Γλώσσες Χωρίς Συμφραζόμενα – Άσκηση 1)  (00:10:03)
Άσκηση (Γλώσσες Χωρίς Συμφραζόμενα – Άσκηση 2)  (00:03:06)
Άσκηση (Γλώσσες Χωρίς Συμφραζόμενα – Άσκηση 3)  (00:03:19)
Άσκηση (Γλώσσες Χωρίς Συμφραζόμενα – Άσκηση 4)  (00:04:40)
Άσκηση (Γλώσσες Χωρίς Συμφραζόμενα – Άσκηση 5)  (00:03:21)
Άσκηση (Γλώσσες Χωρίς Συμφραζόμενα – Άσκηση 6)  (00:03:40)
Απλοποίηση Γραμματικής  (00:10:43)
Κανονικές Γλώσσες & Κανονικές Γραμματικές  (00:12:06)
Άσκηση (Κανονικές Γραμματικές – Άσκηση 7)  (00:02:46)
Άσκηση (Κανονικές Γραμματικές – Άσκηση 8)  (00:04:46)
Ντετερμινηστικά Αυτόματα Στοίβας  (00:26:59)
Άσκηση (Ντετερμινιστικά Αυτόματα Στοίβας – Παράδειγμα 2)  (00:11:20)
Άσκηση (Ντετερμινιστικά Αυτόματα Στοίβας – Άσκηση 1)  (00:10:10)
Άσκηση (Ντετερμινιστικά Αυτόματα Στοίβας – Άσκηση 2)  (00:07:12)
Άσκηση (Ντετερμινιστικά Αυτόματα Στοίβας – Άσκηση 3)  (00:07:59)
Μη Ντετερμινηστικά Αυτόματα Στοίβας  (00:13:10)
Άσκηση (Μη Ντετερμινιστικά Αυτόματα Στοίβας – Άσκηση 4)  (00:05:53)
Άσκηση (Μη Ντετερμινιστικά Αυτόματα Στοίβας – Άσκηση 5)  (00:05:14)
Άσκηση (Μη Ντετερμινιστικά Αυτόματα Στοίβας – Άσκηση 6)  (00:07:41)
Λήμμα Άντλησης (για γλώσσες χωρίς συμφραζόμενα)  (00:15:15)
Άσκηση (Λήμμα Άντλησης για Γραμματικές – Άσκηση 9)  (00:09:22)
Άσκηση (Λήμμα Άντλησης για Γραμματικές – Άσκηση 10)  (00:19:42)
Κεφ. 2ο: Θέματα Εξετάσεων & Επαναληπτικές Ασκήσεις
18 Θέματα
Θέματα σε Γραμματικές και Αυτόματα Στοιβας (Ιούνιος 2007 – Ιούλιος 2009)
Θέμα 1 (Γραμματικές & Αυτόματα Στοίβας – Ιούνιος 2007)  (00:23:37)
Θέμα 2 (Γραμματικές & Αυτόματα Στοίβας – Ιούλιος 2007)  (00:12:10)
Θέμα 3 (Γλώσσες Ανεξάρτητες Συμφραζομένων – Ιούλιος 2007)  (00:06:34)
Θέμα 4 (Γραμματικές & Αυτόματα Στοίβας – Ιούνιος 2008)  (00:13:17)
Θέμα 5 (Γραμματικές & Αυτόματα Στοίβας – Ιούλιος 2008)  (00:08:33)
Θέμα 6 (Γραμματικές & Αυτόματα Στοίβας – Ιούνιος 2009)  (00:12:16)
Θέμα 7 (Γραμματικές & Αυτόματα Στοίβας – Ιούλιος 2009)  (00:05:46)
Θέμα 8 (Λ. Άντλησης για Ανεξάρτητες Συμφραζομένων Γλώσσες – Ιούλιος 2009)  (00:08:18)
Θέματα σε Γραμματικές και Αυτόματα Στοιβας (Ιούνιος 2010 – Ιούλιος 2012)
Θέμα 9 (Γραμματικές & Αυτόματα Στοίβας – Ιούνιος 2010)  (00:23:31)
Θέμα 10 (Γραμματικές & Αυτόματα Στοίβας – Ιούλιος 2010)  (00:09:26)
Θέμα 11 (Λ. Άντλησης για Ανεξάρτητες Συμφραζομένων Γλώσσες – Ιούλιος 2010)  (00:06:23)
Θέμα 12 (Γραμματικές & Αυτόματα Στοίβας – Ιούνιος 2011)  (00:26:49)
Θέμα 13 (Γραμματικές – Ιούλιος 2011)  (00:09:08)
Θέμα 14 (Αυτόματα Στοίβας – Ιούλιος 2011)  (00:12:34)
Θέμα 15 (Γραμματικές & Αυτόματα Στοίβας – Ιούνιος 2012)  (00:26:52)
Θέμα 16 (Γραμματικές & Αυτόματα Στοίβας – Ιούλιος 2012)  (00:13:12)
ΙΙΙ: Θεωρία Υπολογισμού
Κεφ. 1ο: Μηχανές Turing & Αποφασισιμότητα
29 Θέματα
Σημειώσεις [Μηχανές Turing]
Διαφάνειες (Turing-Αποφασίσιμες & Turing-Αποδεκτές Γλώσσες)
Διαφάνειες (Καθολική ΜΤ – Ιδιότητες Κλειστότητας Αποφασίσιμων & Αποδεκτών Γλωσσών)
Διαφάνειες (Μη Επιλυσιμότητα – Αναγωγές – Απαριθμησιμότητα)
Εισαγωγή – Βασικοί Ορισμοί  (00:26:16)
Διαγράμματα Καταστάσεων & Στοιχειώδεις Μηχανές Turing  (00:23:13)
Άσκηση (Μηχανές Turing – Άσκηση 6)  (00:07:40)
Αναδρομικές Συναρτήσεις  (00:06:56)
Άσκηση (Αναδρομικές Συναρτήσεις – Άσκηση 1)  (00:03:51)
Άσκηση (Αναδρομικές Συναρτήσεις – Άσκηση 2)  (00:02:23)
Άσκηση (Αναδρομικές Συναρτήσεις – Άσκηση 3)  (00:07:26)
Άσκηση (Αναδρομικές Συναρτήσεις)  (00:14:58)
Turing-Αποφασίσιμες & Turing-Αποδεκτές Γλώσσες  (00:29:22)
Άσκηση (Turing-Αποφασίσιμες Γλώσσες – Άσκηση 4)  (00:04:42)
Άσκηση (Turing-Αποφασίσιμες Γλώσσες – Άσκηση 5)  (00:09:19)
Άσκηση (Turing-Αποφασίσιμες Γλώσσες – Άσκηση 6)  (00:06:25)
Άσκηση (Turing-Αποφασίσιμες Γλώσσες – Άσκηση 7)  (00:09:28)
Άσκηση (Turing-Αποφασίσιμες Γλώσσες)  (00:15:42)
Επεκτάσεις ΜΤ – Η θέση των Church & Turing – Καθολική ΜΤ  (00:11:02)
Κλειστότητα Turing-αποφασίσιμων & Turing-αποδεκτών Γλωσσών  (00:15:58)
Η γλώσσα HALT  (00:06:53)
Αποδείξεις ιδιοτήτων κλειστότητας Turing-αποφασίσιμων γλωσσών  (00:18:43)
Αποδείξεις ιδιοτήτων κλειστότητας Turing-αποδεκτών γλωσσών  (00:12:47)
Μη Επιλυσιμότητα & Αναγωγές  (00:31:25)
Μη Επιλυσιμότητα της EMPTY  (00:14:45)
Μη Επιλυσιμότητα της EXISTS  (00:09:46)
Μη Επιλυσιμότητα της ALL  (00:10:32)
Μη Επιλυσιμότητα της EQUAL  (00:11:36)
Απαριθμήσιμες & Λεξικογραφικά Απαριθμήσιμες Γλώσσες  (00:29:15)
Κεφ. 2ο: Χρονική Πολυπλοκότητα
19 Θέματα
Διαφάνειες (Εισαγωγή στη Χρονική Πολυπλοκότητα)
Διαφάνειες (NP-πλήρη προβλήματα Λογικής)
Διαφάνειες (NP-πλήρη προβλήματα Θεωρίας Γραφημάτων)
Εισαγωγή στη Χρονική Πολυπλοκότητα – Το πρόβλημα της Ικανοποιησιμότητας (SAT)  (00:32:41)
Οι κλάσεις πολυπλοκότητας P, NP, NP-complete, EXP  (00:27:36)
Παραλλαγές του SAT – NP-πληρότητα των 3SAT, 1in3SAT & NAESAT  (00:33:16)
NP-πληρότητα του 5SAT  (00:09:21)
NP-πληρότητα του NotAllZeroSAT  (00:08:12)
NP-πληρότητα του not-equal-to-t-SAT  (00:11:34)
NP-πληρότητα του MAXSAT  (00:05:11)
NP-πληρότητα του ALMOST SAT  (00:07:17)
NP-πληρότητα του INDEPENDENT SET  (00:11:37)
NP-πληρότητα του CLIQUE  (00:06:58)
NP-πληρότητα του VERTEX COVER  (00:07:52)
NP-πληρότητα του GRAPH ISOMORPHISM  (00:06:27)
NP-πληρότητα του HAMILTON CYCLE  (00:08:20)
NP-πληρότητα του 7-COLORING  (00:12:31)
NP-πληρότητα του k-DENSEST SUBGRAPH  (00:05:40)
NP-πληρότητα του TRAVELING SALESMAN PROBLEM (TSP)  (00:07:06)
Προηγούμενο Θέμα
Επόμενο Μάθημα

Συμβουλές για τις εργασίες

ΠΛΗ30 – Θεμελιώσεις Επιστήμης Η/Υ Γνωριμία με το αντικείμενο της Θ.Ε ΠΛΗ 30 Συμβουλές για τις εργασίες
Προηγούμενο Θέμα
Πίσω στο Μάθημα
Επόμενο Μάθημα