Κεφάλαιο Α: Σχεδιασμός και ανάλυση αλγορίθμων δυναμικού προγραμματισμού - Κεφάλαιο B: Μη κανονικές γλώσσες (Λήμμα Άντλησης)

  1. Ψηφιακό τεκμήριο (Έγγραφο)
  2. ΠΛΗ30 Ψηφιακό Εκπαιδευτικό Υλικό (ΨΕΥ)
  3. Ελληνικά
  4. ΚΑΠΟΡΗΣ, ΑΛΕΞΙΟΣ (ΔΙΔΑΚΤΩΡ ΤΜΗΜΑΤΟΣ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ, ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ)
  5. ΑΛΕΒΙΖΟΣ, ΠΑΝΑΓΙΩΤΗΣ (ΕΠΙΚΟΥΡΟΣ ΚΑΘΗΓΗΤΗΣ, ΤΜΗΜΑ ΜΑΘΗΜΑΤΙΚΩΝ, ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ)
  6. ΣΚΟΔΡΑΣ, ΑΘΑΝΑΣΙΟΣ (ΚΑΘΗΓΗΤΗΣ, ΣΧΟΛΗ ΘΕΤΙΚΩΝ ΕΠΙΣΤΗΜΩΝ ΚΑΙ ΤΕΧΝΟΛΟΓΙΑΣ, ΕΛΛΗΝΙΚΟ ΑΝΟΙΚΤΟ ΠΑΝΕΠΙΣΤΗΜΙΟ)
  7. ΧΑΤΖΗΛΑΚΟΣ, ΑΘΑΝΑΣΙΟΣ (ΑΝΑΠΛΗΡΩΤΗΣ ΚΑΘΗΓΗΤΗΣ, ΕΛΛΗΝΙΚΟ ΑΝΟΙΚΤΟ ΠΑΝΕΠΙΣΤΗΜΙΟ)
  8. Υ1: Διωνυμικός συντελεστής (2 ώρες / 8η εβδ.), Υ2: Μέγιστη αύξουσα υποακολουθία (2 ώρες / 8η εβδ.), Y3: Ανταγωνιστικές εταιρίες (2 ώρες / 8η εβδ.), Y4: Χρονικά εξαρτημένες εργασίες με βάρη (2-2.5 ώρες / 8η εβδ.), Y5: Σάκος πεπ. χωρητικότητας (2-2.5 ώρες / 8η εβδ.), Y6: Σάκος ληστή (2 ώρες / 8η εβδ.) Y7:Προσέγγ.καμπύλης με ευθ. Τμ. (2 ώρες / 8η εβδ), Y8: Πολ/σμός αλληλουχίας πινάκων (2-2.5 ώρες / 9η εβδ.), Y9: RNA δευτερεύουσα δομή (2.5-3 ώρες / 9η εβδ.), Y10: Μονότονο ταίριασμα λέξεων (2.5-3 ώρες / 9η εβδ.), Y11: Βέλτιστο δυαδικό δέντρο αναζήτησης (2.5-3 ώρες / 9η εβδ.), Y12: Εισαγωγή (1.5-2 ώρες / 15η εβδ.), Y13: Η γλώσσα Β= {0n1n : n≥0 } δεν είναι κανονική (1-1.5 ώρες / 15η εβδ.), Y14: Η γλώσσα C= {w: η w έχει ίσο πλήθος από 0’ς και 1’ς} δεν είναι κανονική (1-1.5 ώρες / 15η εβδ.), Y15: Η γλώσσα F= {ww: w λέξη του αλφαβήτου} δεν είναι κανονική (1-1.5 ώρες / 15η εβδ.), Y16: Η γλώσσα D= {1nn: n≥0} δεν είναι κανονική (1.5-2 ώρες / 15η εβδ.), Y17:Η γλώσσα E= {0i1j: i≥j} δεν είναι κανονική (1.5-2 ώρες / 15η εβδ.), Y18: Η γλώσσα A= {a(ab)ncn : n≥0 } δεν είναι κανονική (1.5-2 ώρες / 15η εβδ.), Y19: Αναδρομικός ορισμός μη κανονικής γλώσσας (2-2.5 ώρες / 15η εβδ.), Y20: Αναδρομικός ορισμός μη κανονικής γλώσσας (2-2.5 ώρες / 15η εβδ.). (90 Σελίδες + 38 Εικόνες)
    • Ο κύριος στόχος είναι να παρουσιάσει και να οριοθετήσει τις βασικές γραμμές δύο ισχυρών μεθοδολογιών. Η πρώτη κατεύθυνση είναι ο φοιτητής να αποκτήσει ικανότητα αντιμετωπίσεως μεγάλου φάσματος προβλημάτων που επιλύονται με αλγόριθμους Δυναμικού Προγραμματισμού. Ως προς την δεύτερη κατεύθυνση, το υλικό αναπτύσσει την ικανότητα του φοιτητή να επιλύει προβλήματα που αφορούν Μη Κανονικές Γλώσσες με χρήση του Λήμματος Άντλησης, διδάσκοντας του κατάλληλο τρόπο μεθοδικής εργασίας.
  10. Τόμος Α, Κεφάλαιο 4, Παράγραφοι 4.1-4.2, Τόμος Γ, Κεφάλαιο 6, Παράγραφοι 6.1-6.2 της ΘΕ ΠΛΗ 30.
  11. Κεφάλαιο Α: δυναμικός προγραμματισμός, πρόβλημα βελτιστοποίησης, ιδιότητα βέλτιστων επιμέρους δομών, ιδιότητα επικαλυπτόμενων επιμέρους προβλημάτων, στρατηγικές top-down και bottom-up - Κεφάλαιο B: μη κανονικές γλώσσες, πεπερασμένη μνήμη αυτομάτου, αδυναμία αναγνώρισης γλωσσών που απαιτούν μεγάλη μνήμη, λήμμα άντλησης, αλγόριθμοι και προβλήματα απόφασης. Chapter A: algorithms, dynamic programming algorithm, optimum solution, overlapping subproblems, optimal substructure, memorization, bottom-up and top-down approach, recurrence - Chapter B: formal languages, computability theory, pumping lemma, infinite language, non regular languages, finite automata, finite memory
  12. Το υλικό απευθύνεται σε φοιτητές χωρίς προγενέστερη γνώση των παρακάτω δύο γνωστικών αντικειμένων: Σχεδιασμός και ανάλυση αλγορίθμων Δυναμικού Προγραμματισμού. Μη κανονικές γλώσσες (Λήμμα Άντλησης). Το υλικό δεν προαπαιτεί την χρήση άλλων βιβλίων ή βοηθημάτων. Προτείνουμε όμως, ως προς το πρώτο γνωστικό αντικείμενο, να γίνει μια αρχική μελέτη του Κεφαλαίου 4, τόμος Α της ΘΕ ΠΛΗ 30. Ως προς το δεύτερο γνωστικό αντικείμενο, να γίνει αρχική μελέτη του Κεφαλαίου 6, τόμος Γ της ΘΕ ΠΛΗ 30.