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

ΚΑΠΟΡΗΣ, ΑΛΕΞΙΟΣ (ΔΙΔΑΚΤΩΡ ΤΜΗΜΑΤΟΣ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ, ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ)

ΣΚΟΔΡΑΣ, ΑΘΑΝΑΣΙΟΣ (ΚΑΘΗΓΗΤΗΣ, ΣΧΟΛΗ ΘΕΤΙΚΩΝ ΕΠΙΣΤΗΜΩΝ ΚΑΙ ΤΕΧΝΟΛΟΓΙΑΣ, ΕΛΛΗΝΙΚΟ ΑΝΟΙΚΤΟ ΠΑΝΕΠΙΣΤΗΜΙΟ)

ΑΛΕΒΙΖΟΣ, ΠΑΝΑΓΙΩΤΗΣ (ΕΠΙΚΟΥΡΟΣ ΚΑΘΗΓΗΤΗΣ, ΤΜΗΜΑ ΜΑΘΗΜΑΤΙΚΩΝ, ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ)

ΧΑΤΖΗΛΑΚΟΣ, ΑΘΑΝΑΣΙΟΣ (ΑΝΑΠΛΗΡΩΤΗΣ ΚΑΘΗΓΗΤΗΣ, ΕΛΛΗΝΙΚΟ ΑΝΟΙΚΤΟ ΠΑΝΕΠΙΣΤΗΜΙΟ)

Ο κύριος στόχος είναι να παρουσιάσει και να οριοθετήσει τις βασικές γραμμές δύο ισχυρών μεθοδολογιών. Η πρώτη κατεύθυνση είναι ο φοιτητής να αποκτήσει ικανότητα αντιμετωπίσεως μεγάλου φάσματος προβλημάτων που επιλύονται με αλγόριθμους Δυναμικού Προγραμματισμού. Ως προς την δεύτερη κατεύθυνση, το υλικό αναπτύσσει την ικανότητα του φοιτητή να επιλύει προβλήματα που αφορούν Μη Κανονικές Γλώσσες με χρήση του Λήμματος Άντλησης, διδάσκοντας του κατάλληλο τρόπο μεθοδικής εργασίας.

Το ΕΔΥ αποτελείται από δύο κεφάλαια. Το πρώτο κεφάλαιο παρουσιάζει μεθοδολογία επίλυσης με Δυναμικό Προγραμματισμό μιας σειράς από τα πλέον αντιπροσωπευτικά προβλήματα που μπορεί να βρει ένας φοιτητής ανατρέχοντας στη διεθνή ξένη βιβλιογραφία. Το δεύτερο κεφάλαιο παρουσιάζει τρόπο μεθοδικής εργασίας με χρήση του Λήμματος Άντλησης για να δείξουμε ότι μια γλώσσα είναι μη κανονική. Έχουν επιλεγεί αντιπροσωπευτικά παραδείγματα μη κανονικών γλωσσών. Και στα δύο κεφάλαια τα παραδείγματα είναι κλιμακωτής δυσκολίας. Σχεδόν σε κάθε παράδειγμα, παρουσιάζουμε και ένα λανθασμένο τρόπο επίλυσης, καταδεικνύοντας τη «λογική» που συχνά οδηγεί στο λάθος.

Hypertext

Κεφάλαιο Α: δυναμικός προγραμματισμός, πρόβλημα βελτιστοποίησης, ιδιότητα βέλτιστων επιμέρους δομών, ιδιότητα επικαλυπτόμενων επιμέρους προβλημάτων, στρατηγικές 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

Ελληνικό Ανοικτό Πανεπιστήμιο

Ιδρυματικό Αποθετήριο Ελληνικου Ανοικτού Πανεπιστημίου

Ελληνική γλώσσα

2013-12-13T14:48:36Z

2008

2009-03-09T09:23:41Z

http://apothesis.eap.gr/handle/eap/653

Υ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 Εικόνες)