ΠΛΗ30 ΜΑΘΗΜΑ 6.2Dimitris Psounis1) Εισαγώγή
1.1) Σχήμα Απόδειξης Αναγωγής
1.2) Αναγωγές της Προτασιακής Λογικής
2) Το πρόβλημα 3SAT είναι NP-πλήρες
2.1) 3SAT ανήκει στο NP
2.2) SAT ανάγεται στο 3SAT
3) Το πρόβλημα 1-IN-3-SAT είναι NP-πλήρες
3.1) 1-IN-3-SAT ανήκει στο NP
3.2) 3SAT ανάγεται στο 1-IN-3-SAT
4) Το πρόβλημα NAE-3SAT είναι NP-πλήρες
4.1) NAE-3SAT ανήκει στο NP
4.2) 3SAT ανάγεται στο NAE-3SAT
Ασκήσεις
1) To NOT-ALL-ZERO-SAT είναι NP-πλήρες
2) Το 5SAT είναι NP-πλήρες
3) Το AtLeast3SAT είναι NP-πλήρες
4) To AlmostSAT είναι NP-πλήρες
ΠΛΗ30 ΜΑΘΗΜΑ 6.3Dimitris Psounis1) Εισαγώγή
1.1) Σχήμα Απόδειξης Αναγωγής
1.2) Αναγωγές της Προτασιακής Λογικής
2) Το πρόβλημα INDEPENDENT-SET είναι NP-πλήρες
2.1) INDEPENDENT-SET ανήκει στο NP
2.2) 3SAT ανάγεται στο INDEPENDENT-SET
3) Το πρόβλημα CLIQUE είναι NP-πλήρες
3.1) CLIQUE ανήκει στο NP
3.2) INDEPENDENT-SET ανάγεται στο CLIQUE
4) Το πρόβλημα VERTEX-COVER είναι NP-πλήρες
4.1) VERTEX-COVER ανήκει στο NP
4.2) INDEPENDENT-SET ανάγεται στο VERTEX-COVER
5) Το πρόβλημα SUBGRAPH-ISOMORPHISM είναι NP-πλήρες
5.1) SUBGRAPH-ISOMORPHISM ανήκει στο NP
5.2) CLIQUE ανάγεται στο SUBGRAPH-ISOMORPHISM
Ασκήσεις
1) To (n/2)-CLIQUE είναι NP-πλήρες
2) Το KITE είναι NP-πλήρες
3) Το k-DENSEST-SUBGRAPH είναι NP-πλήρες
4) Το k-LIGHTEST-SUBGRAPH είναι NP-πλήρες
ΠΛΗ30 ΜΑΘΗΜΑ 6.1 (ΕΚΤΥΠΩΣΗ)Dimitris PsounisEl documento describe un resumen de tres oraciones de un documento sobre la gestión de proyectos. La primera oración explica que el documento proporciona un resumen de un proyecto de gestión. La segunda oración resume que el proyecto involucraba la planificación, ejecución y control de varias tareas. La tercera oración resume que el proyecto se completó según lo programado y dentro del presupuesto.
ΠΛΗ30 ΜΑΘΗΜΑ 6.1Dimitris Psounis1) Εισαγωγή
1.1) Είδη Προβλημάτων
1.2) Μοντέλα Υπολογισμού
2) Το πρόβλημα της ικανοποιησιμότητας - SAT
2.1) Διατυπωση του προβλήματος
2.2) To SAT λύνεται σε ντετερμιιστικό εκθετικό χρόνο.
2.3) To SAT λύνεται σε ντετερμινιστικό πολυωνυμικό χρόνο?
2.4) Το SAT λύνεται σε μη ντετερμινιστικό πολυωνυμικό χρόνο.
2.5) Σύνοψη για το πρόβλημα SAT
3) Θεωρία Πολυπλοκότητας
3.1) Η κλάση P
3.2) Η κλάση NP
3.3) Η κλάση EXP
3.4) P ⊆푵NP푷⊆퐄EXP퐗퐏
3.5) NP-πληρότητα
4) NP-πληρότητα
4.1) Αποδείξεις NP-πληρότητας
4.2) Ιδιότητες NP-Complete προβλημάτων
4.3) Το ανοικτό πρόβλημα P=NP
4.4) Η κλάση NP-Complete
4.5) Ιεραρχία κλάσεων αν P ≠ NP푷
4.6) Ιεραρχία κλάσεων αν P = NP푷
Ασκήσεις
ΠΛΗ30 ΜΑΘΗΜΑ 6.4 (ΕΚΤΥΠΩΣΗ)Dimitris PsounisThis document discusses the relationships between three concepts: ABC=;?: B?A, ABC=;?: 9D9;E, and 316/-/:,0;. It states that ABC=;?: B?A is related to ABC=;?: 9D9;E, and provides examples to illustrate their connection. It also explains how 316/-/:,0; is different from the other two concepts.
ΠΛΗ30 ΜΑΘΗΜΑ 6.4Dimitris Psounis1) Εισαγώγή
1.1) Σχήμα Απόδειξης Αναγωγής
1.2) Αναγωγές της Προτασιακής Λογικής
2) Το πρόβλημα HAMILTON-PATH είναι NP-πλήρες
2.1) HAMILTON-PATH ανήκει στο NP
2.2) 3SAT ανάγεται στο HAMILTON-PATH
3) Το πρόβλημα HAMILTON-CYCLE είναι NP-πλήρες
3.1) HAMILTON-CYCLE ανήκει στο NP
3.2) HAMILTON-PATH ανάγεται στο HAMILTON-CYCLE
4) Το πρόβλημα 3-COLORING είναι NP-πλήρες
4.1) 3-COLORING ανήκει στο NP
4.2) 3SAT ανάγεται στο 3-COLORING
Ασκήσεις
1) To 7-COLORING είναι NP-πλήρες
2) Το TSP είναι NP-πλήρες
ΠΛΗ30 ΜΑΘΗΜΑ 6.5Dimitris Psounis1) Εισαγώγή
1.1) Σχήμα Απόδειξης Αναγωγής
1.2) Αναγωγές της Προτασιακής Λογικής
2) Το πρόβλημα PARTITION είναι NP-πλήρες
3) Το πρόβλημα KNAPSACK είναι NP-πλήρες
3.1) KNAPSACK ανήκει στο NP
3.2) PARTITION ανάγεται στο KNAPSACK
4) Το πρόβλημα 3PM είναι NP-πλήρες
5) Το πρόβλημα x3C είναι NP-πλήρες
5.1) X3C ανήκει στο NP
5.2) 3PM ανάγεται στο X3C
6) Το πρόβλημα EXACT-COVER είναι NP-πλήρες
7) Το πρόβλημα SET-COVER είναι NP-πλήρες
7.1) SET-COVER ανήκει στο NP
7.2) EXACT-COVER ανάγεται στο SET-COVER
ΠΛΗ30 ΜΑΘΗΜΑ 5.4Dimitris Psounis1) Η αποδεικτική διαδικασία της αναγωγής
1.1) Σκεπτικό: Η γλώσσα Halting
1.2) Το Θεώρημα Αναγωγής
1.3) Σχήμα Απόδειξης Αναγωγής
2) Παραδείγματα Αναγωγών
2.1) Ο πιο συχνά χρησιμοποιούμενος μετασχημαισμός
2.2) Τερματίζει ένα πρόγραμμα με οποιαδήποτε είσοδο;
2.3) Τερματίζει ένα πρόγραμμα με είσοδο την κενή συμβολοσειρά;
2.4) Τερματίζει ένα πρόγραμμα με είσοδο έστω μία συμβολοσειρά;
2.5) Είναι δύο προγράμματα ισοδύναμα;
2.6) Το πρόγραμμα δεν τερματίζει για καμία είσοδο
3) Άλλες Μη Επιλύσιμες Γλώσσες
3.1) Αναγνώριση συνόλου γλώσσας
3.2) Ασκ.Αυτ.2.2 και Δραστ.2.2
3.3) Μη Επιλύσιμες Γλώσσες για Γλώσσες Χωρίς Συμφραζόμενα
ΠΛΗ30 ΜΑΘΗΜΑ 5.3Dimitris Psounis1) Μηχανές Turing που αποδέχονται γλώσσες
1.1) Ορισμός Αποδεκτής Γλώσσας
1.2) Κάθε Αποφασίσιμη Γλώσσα είναι Αποδεκτή
2) Καθολική Μηχανή Turing
2.1) Ορισμός του Αλγορίθμου
2.2) Η θέση Church-Turing
2.3) Μηχανές που τρέχουν μηχανές
2.4) Καθολική Μηχανή Turing
3) Η γλώσσα Halting
3.1) Ορισμός
3.2) Απόδειξη ότι δεν είναι αποφασίσιμη
3.3) Απόδειξη ότι είναι αποδεκτή
4) Κλειστότητα στις Αποδεκτές Γλώσσες
4.1) Κλειστότητα στην Ένωση
4.2) Κλειστότητα στην Τομή
4.3) Κλειστότητα στην Παράθεση
4.4) Κλειστότητα στο Αστέρι Kleene
4.5) ΌΧΙ Κλειστότητα στο Συμπλήρωμα
Ασκήσεις
Η ΓΛΩΣΣΑ C++ - ΜΑΘΗΜΑ 4 - ΚΛΑΣΕΙΣ ΚΑΙ ΑΝΑΦΟΡΕΣDimitris PsounisΠΕΡΙΕΧΟΜΕΝΑ ΜΑΘΗΜΑΤΟΣ
Α. Θεωρία
1. Αναφορές
1.1 Τι είναι αναφορά
1.2 Παράδειγμα χρήσης αναφοράς
1.3. ...και το πιο συνηθισμένο λάθος
2 Αναφορές και Συναρτήσεις
2.1 Διοχέτευση ορίσματος μέσω τιμής (by value)
2.2.Διοχέτευση ορίσματος μέσω δείκτη (by pointer)
2.3 Διοχέτευση ορίσματος μέσω αναφοράς (by reference)
3 Κατασκευαστής αντιγράφου
3.1 Αντίγραφα Αντικειμένων
3.2 Ορισμός Κατασκευαστή Αντιγράφου (copy constructor)
3.3 Κλήση όταν διοχετεύεται αντικείμενο σε συνάρτηση μέσω τιμής
3.4 Επιστροφη αντικειμένου από συνάρτηση μέσω τιμής
3.5 Δήλωση και αρχικοποίηση μέσω άλλου αντικειμένου Ασκήσεις
Β. Ασκήσεις
Η ΓΛΩΣΣΑ C++ - ΜΑΘΗΜΑ 4 - ΚΛΑΣΕΙΣ ΚΑΙ ΑΝΑΦΟΡΕΣ (4διαφ)Dimitris PsounisΠΕΡΙΕΧΟΜΕΝΑ ΜΑΘΗΜΑΤΟΣ
Α. Θεωρία
1. Αναφορές
1.1 Τι είναι αναφορά
1.2 Παράδειγμα χρήσης αναφοράς
1.3. ...και το πιο συνηθισμένο λάθος
2 Αναφορές και Συναρτήσεις
2.1 Διοχέτευση ορίσματος μέσω τιμής (by value)
2.2.Διοχέτευση ορίσματος μέσω δείκτη (by pointer)
2.3 Διοχέτευση ορίσματος μέσω αναφοράς (by reference)
3 Κατασκευαστής αντιγράφου
3.1 Αντίγραφα Αντικειμένων
3.2 Ορισμός Κατασκευαστή Αντιγράφου (copy constructor)
3.3 Κλήση όταν διοχετεύεται αντικείμενο σε συνάρτηση μέσω τιμής
3.4 Επιστροφη αντικειμένου από συνάρτηση μέσω τιμής
3.5 Δήλωση και αρχικοποίηση μέσω άλλου αντικειμένου Ασκήσεις
Β. Ασκήσεις
ΓΛΩΣΣΑ C++ - ΜΑΘΗΜΑ 3 - ΚΛΑΣΕΙΣ ΚΑΙ ΔΕΙΚΤΕΣ (4δ)Dimitris PsounisΠΕΡΙΕΧΟΜΕΝΑ ΜΑΘΗΜΑΤΟΣ
Α. Θεωρία
1.Διαχείριση Μνήμης
1.1.Στατική Δέσμευση Μνήμης
1.2.Στατική Δέσμευση Μνήμης για Συνήθεις Μεταβλητές
1.3.Στατική Δέσμευση Μνήμης για Αντικείμενα
2.Δυναμική Δέσμευση Μνήμης
2.1.Δείκτες (Υπενθύμιση από C)
2.2.Οι τελεστές new και delete
2.3.Δυναμική Δέσμευση για Συνήθεις Μεταβλητές
2.4.Δυναμική Δέσμευση για Αντικείμενα
2.5.Δυναμική Δέσμευση και Κατασκευαστές
3.Κλάσεις που περιέχουν δείκτες
3.1.Παράδειγμα κλάσης που περιέχει δείκτες
3.2.…και ένα πρόβλημα (χωρίς λύση για την ώρα)
4..Δυναμική Δέσμευση Μνήμης για Πίνακες
4.1.Μονοδιάστατοι πίνακες
4.2.Παράδειγμα δέσμευσης μνήμης για μονοδιάστατους πίνακες
4.3.Διδιάστατοι πίνακες
4.4.Παράδειγμα δέσμευσης μνήμης για διδιάστατους πίνακες
B. Ασκήσεις
ΓΛΩΣΣΑ C++ - ΜΑΘΗΜΑ 3 - ΚΛΑΣΕΙΣ ΚΑΙ ΔΕΙΚΤΕΣDimitris PsounisΠΕΡΙΕΧΟΜΕΝΑ ΜΑΘΗΜΑΤΟΣ
Α. Θεωρία
1.Διαχείριση Μνήμης
1.1.Στατική Δέσμευση Μνήμης
1.2.Στατική Δέσμευση Μνήμης για Συνήθεις Μεταβλητές
1.3.Στατική Δέσμευση Μνήμης για Αντικείμενα
2.Δυναμική Δέσμευση Μνήμης
2.1.Δείκτες (Υπενθύμιση από C)
2.2.Οι τελεστές new και delete
2.3.Δυναμική Δέσμευση για Συνήθεις Μεταβλητές
2.4.Δυναμική Δέσμευση για Αντικείμενα
2.5.Δυναμική Δέσμευση και Κατασκευαστές
3.Κλάσεις που περιέχουν δείκτες
3.1.Παράδειγμα κλάσης που περιέχει δείκτες
3.2.…και ένα πρόβλημα (χωρίς λύση για την ώρα)
4..Δυναμική Δέσμευση Μνήμης για Πίνακες
4.1.Μονοδιάστατοι πίνακες
4.2.Παράδειγμα δέσμευσης μνήμης για μονοδιάστατους πίνακες
4.3.Διδιάστατοι πίνακες
4.4.Παράδειγμα δέσμευσης μνήμης για διδιάστατους πίνακες
B. Ασκήσεις
Η ΓΛΩΣΣΑ C++ - ΜΑΘΗΜΑ 2 - ΕΙΣΑΓΩΓΗ ΣΤΙΣ ΚΛΑΣΕΙΣDimitris PsounisΑ. Θεωρία
1. Κλάσεις
1.1 Γενικά
1.2 Ορισμός Κλάσης
1.3 Δημόσια (public) στοιχεία της κλάσης
1.4 Ιδιωτικά (private) στοιχεία της κλάσης
1.5 Παράδειγμα (προδιαγραφές)
2 Περισσότερα για τις κλάσεις
2.1 Ορισμός Συναρτήσεων έξω από την Κλάση
2.2 Παρουσίαση Ιδιωτικών – Δημόσιων Μέλων μιας κλάσης
2.3 Χωρισμός σε Αρχεία
3. Ειδικές Μεθόδοι Κλάσεων
3.1 Γενικά
3.2 Κατασκευαστής (constructor)
3.3 Καταστροφέας (destructor)
3.4 Ελεγκτές Πρόσβασης (accessors)
B. Ασκήσεις
Η ΓΛΩΣΣΑ C++ - ΜΑΘΗΜΑ 2 - ΕΙΣΑΓΩΓΗ ΣΤΙΣ ΚΛΑΣΕΙΣ (4 διαφ)Dimitris PsounisΑ. Θεωρία
1. Κλάσεις
1.1 Γενικά
1.2 Ορισμός Κλάσης
1.3 Δημόσια (public) στοιχεία της κλάσης
1.4 Ιδιωτικά (private) στοιχεία της κλάσης
1.5 Παράδειγμα (προδιαγραφές)
2 Περισσότερα για τις κλάσεις
2.1 Ορισμός Συναρτήσεων έξω από την Κλάση
2.2 Παρουσίαση Ιδιωτικών – Δημόσιων Μέλων μιας κλάσης
2.3 Χωρισμός σε Αρχεία
3. Ειδικές Μεθόδοι Κλάσεων
3.1 Γενικά
3.2 Κατασκευαστής (constructor)
3.3 Καταστροφέας (destructor)
3.4 Ελεγκτές Πρόσβασης (accessors)
B. Ασκήσεις
C++ - ΜΑΘΗΜΑ 1 - ΕΙΣΑΓΩΓΗ ΚΑΙ ΣΧΕΣΗ ΜΕ ΤΗ CDimitris PsounisΠΕΡΙΕΧΟΜΕΝΑ ΜΑΘΗΜΑΤΟΣ
Α. Θεωρία
1. Η Γλώσσα C++
1.1. Γενικά
1.2. Ιστορία – Εκδόσεις
1.3. Η αναγκαιότητα της C
1.4. Μεταγλωττιστές
2. Hello World!
2.1. Πηγαίος Κώδικας
2.2. Σχόλια
2.3. Βιβλιοθήκη iostream
2.4. main, block κώδικα, return
2.5 Είσοδος/Έξοδος
2.5.1. Έξοδος με την cout
2.5.2. Οδηγία using
2.5.3. Περισσότερα για την cout
2.5.4. Είσοδος με την cin
3. Στοιχεία της C
3.1. Μεταβλητές
3.2. Σταθερές
3.3. Τελεστές και η Δομή Ελέγχου
3.4. Δομές Επανάληψης
3.5. Συναρτήσεις
3.5.1. Πολυμορφισμός Συναρτήσεων
3.6. Πίνακες
3.7. Συμβολοσειρές
3.8. Δείκτες
B.Ασκήσεις
Εφαρμογή 1
Εφαρμογή 2
Εφαρμογή 3
C++ - ΜΑΘΗΜΑ 1 - ΕΙΣΑΓΩΓΗ ΚΑΙ ΣΧΕΣΗ ΜΕ ΤΗ C (4sl/p)Dimitris PsounisΠΕΡΙΕΧΟΜΕΝΑ ΜΑΘΗΜΑΤΟΣ
Α. Θεωρία
1. Η Γλώσσα C++
1.1. Γενικά
1.2. Ιστορία – Εκδόσεις
1.3. Η αναγκαιότητα της C
1.4. Μεταγλωττιστές
2. Hello World!
2.1. Πηγαίος Κώδικας
2.2. Σχόλια
2.3. Βιβλιοθήκη iostream
2.4. main, block κώδικα, return
2.5 Είσοδος/Έξοδος
2.5.1. Έξοδος με την cout
2.5.2. Οδηγία using
2.5.3. Περισσότερα για την cout
2.5.4. Είσοδος με την cin
3. Στοιχεία της C
3.1. Μεταβλητές
3.2. Σταθερές
3.3. Τελεστές και η Δομή Ελέγχου
3.4. Δομές Επανάληψης
3.5. Συναρτήσεις
3.5.1. Πολυμορφισμός Συναρτήσεων
3.6. Πίνακες
3.7. Συμβολοσειρές
3.8. Δείκτες
B.Ασκήσεις
Εφαρμογή 1
Εφαρμογή 2
Εφαρμογή 3
Emotional Intelligence in Yoga philosophyRashmiTiwari72Yoga philosophy emphasizes self-awareness, self-regulation, motivation and empathy, which are key components of emotional intelligence. Yoga practices like chitta-prasadana, kriyayoga and astangayoga help you develop these skills.