- / -

Τα Μαθηματικά, που στο αρχικό στάδιο ανάπτυξής τους αποτελούσαν κυρίως ένα σύνολο εμπειρικών κανόνων για την εκτέλεση πράξεων, σήμερα έχουν γίνει απαραίτητα στη ζωή μας, εισχωρώντας αποφασιστικά με ταχύτατους ρυθμούς σε κάθε σύγχρονο κλάδο επιστημονικής δραστηριότητας. Ο Γραμμικός Προγραμματισμός είναι ένας από τους πιο εφαρμοσμένους κλάδους της επιστήμης των μαθηματικών με πληθώρα εφαρμογών στην επιστήμη των ηλεκτρονικών υπολογιστών και ασχολείται με τη επίλυση του γραμμικού μοντέλου στην Επιχειρησιακή Έρευνα. Για το σκοπό αυτό μελετάει τις ιδιότητες του γραμμικού προβλήματος, κατασκευάζει τρόπους επίλυσης και εξετάζει τρόπους εφαρμογής των αποτελεσμάτων στη λήψη πολύπλοκων αποφάσεων. Από την οικονομική σκοπιά, ο Γραμμικός Προγραμματισμός είναι μια τεχνική που ασχολείται με το πρόβλημα της βέλτιστης κατανομής των περιορισμένων πόρων ενός συστήματος σε ανταγωνιζόμενες δραστηριότητες κατά τον καλύτερο δυνατό τρόπο. Ακόμη χρησιμοποιείται για τη επίλυση προβλημάτων ενέργειας, διοίκησης προσωπικού, προστασία του περιβάλλοντος, καθώς επίσης και προβλημάτων που αφορούν την ανάθεση πεπερασμένων πόρων σε ανταγωνιστικές απαιτήσεις (π.χ. κατανομή εργατικού δυναμικού, πρώτων υλών και τεχνολογικού εξοπλισμού). Η αρχική μαθηματική διατύπωση του προβλήματος καθώς και μια συστηματική διαδικασία λύσης του, η μέθοδος Simplex, οφείλεται στον G. B. Dantzig στα 1947. Νωρίτερα διάφορα προβλήματα τύπου γραμμικού προγραμματισμού είχαν διαμορφωθεί και επιλυθεί. Τα σημαντικότερα από αυτά αφορούν το πρόβλημα μεταφοράς (Hitchcock 1941, Koopmans 1949) και το πρόβλημα της δίαιτας (Stigler 1945). Ο Dantzig ήταν όμως ο άνθρωπος που κατασκεύασε το γενικό πλαίσιο και ταυτόχρονα υπέδειξε τη μέθοδο επίλυσης του. Θεωρείται σαν μια από τις πιο σπουδαίες μαθηματικές ανακαλύψεις των μέσων χρόνων του εικοστού αιώνα και στις μέρες μας αποτελεί ένα μοντέλο ευρείας χρήσης για καθημερινά ζητήματα των περισσότερων μεσαίου και μεγάλου μεγέθους εμπορικών - βιομηχανικών εταιρειών. Στο πρώτο κεφάλαιο της παρούσης εργασίας επιδεικνύεται η ανάγκη δημιουργίας ενός μαθηματικού μοντέλου για την περιγραφή και επίλυση του γραμμικού προβλήματος μας. Ενώ στο δεύτερο κεφάλαιο διατυπώνεται και περιγράφεται ο Αλγόριθμος Simplex στη επίλυση ενός Γραμμικού Προβλήματος Προγραμματισμού. Μια από τις σημαντικότερες πτυχές του Γραμμικού Προγραμματισμού αναπτύσσεται στο 8 τρίτο κεφάλαιο, η έννοια του Δυικού προβλήματος, το οποίο σχετίζεται με τη δομή του αρχικού προβλήματος και τυχαίνει να είναι και αυτό ταυτόχρονα επίλυση. Το κεφάλαιο 4 επικεντρώνεται στις εναλλακτικές μεθόδους επίλυσης του προβλήματος και εισάγει τη βασική έννοια της υπολογιστικής Πολυπλοκότητας. Συγκεκριμένα αναπτύσσεται ο Αλγόριθμος Karmakar και ο πρωτεύον – δυικος αλγόριθμος εσωτερικού σημείου. / Mathematics, which were mostly thought to be a set of empirical rules for the execution of operations and instruments, especially during their initial stage of development, have now become indispensable in our lives, decisively penetrating in each and every contemporary field of scientific activity. Linear programming is one of the most applied fields of this fast-growing science and is characterised by a plethora of applications in the field of computer science and deals with the solution of the linear model in Operational Research. To this end, it studies the properties of the linear problem, develops methods for solving the problem and investigates ways of applying the results in making complex decisions. From a business/economic perspective, Linear Programming is a technique that deals with the problem of optimal distribution of a system’s limited resources to competing activities in the best possible way. In addition to the above, it is used when required to solve varying problems such as energy, human resource management, and protection of the environment as well as problems that have to do with delegating finite resources to competing requirements (i.e. distribution of manpower, raw materials and technological equipment). The initial mathematical formulation of the problem as well as a systematic solution process, known as the Simplex method, is due to G. B. Dantzig, in 1947. Earlier than that various problems of linear programming were developed and solved. The most important of these are concerned with the transfer problem (Hitchcock 1941, Koopmans 1949) and the diet problem (Stigler 1945). Dantzig however, was the first one to construct the general framework and demonstrated the appropriate solving method at the same time. It is considered to be one of the most important mathematical discoveries of the middle ages of the twentieth century. Nowadays it is a model broadly-used for everyday matters of most medium and large commercial - industrial companies. The first chapter of the current project will demonstrate the need for creating a mathematical model for the description and solution of our linear problem. While the second chapter sets out and describes the Simplex Algorithm in solving a Linear Programming Problem. One of the most important aspects of Linear Programming is developed in the third chapter, the concept of the Dual Problem, which relates to the structure of the initial problem and happens to be a solution to the problem at the same time. Finally, chapter 4 concentrates on the alternative methods of solving the problem 10 and introduces the basic concept of Computing Complexity. More specifically, Karmakar algorithm is developed as well as the primal-dual internal-point algorithm.

Η γλώσσα προγραμματισμού Scratch είναι ιδανική για την εισαγωγή στον προγραμματισμό. Η νέα αυτή γλώσσα ανήκει στο παράδειγμα του ταυτόχρονου προγραμματισμού. Στην εργασία αυτή περιγράφεται η σχεδίαση και η αξιολόγηση ενός εξαμηνιαίου μαθήματος για την εκμάθηση της Scratch με σκοπό αφενός να μελετηθεί ο τρόπος με τον οποίο οι αρχάριοι προγραμματιστές προσεγγίζουν το θέμα του συγχρονισμού και αφετέρου να διατυπωθούν προτάσεις για τη βελτίωση του μαθήματος. Η μεθοδολογία που εφαρμόστηκε είναι βασισμένη σε σχεδιασμό ερευνητική μεθοδολογία. / Scratch programming language is ideal for introductory programming courses. This new language follows the concurrent programming paradigm. Ιn the thesis the design and evaluation of a course for learning programming with Scratch is described. The approach that beginners programmers use for the necessary synchronization is studied and a new proposal for the laboratory course is presented. The design based research methodology is followed.

Στην παρούσα εργασία παρουσιάζονται εφαρμογές των στοχαστικών διαδικασιών στα λεγόμενα κοινωνικά συστήματα από τη σκοπιά του προγραμματισμού ανθρώπινου δυναμικού (manpower planning). O προγραμματισμός του ανθρώπινου δυναμικού έχει να κάνει με την κατάλληλη τοποθέτηση των μελών του συστήματος στις σωστές θέσεις, σε αριθμούς οι οποίοι εγγυώνται την ομαλή λειτουργία. Αρχικά αναπτύσσουμε το μη ομογενές Μαρκοβιανό σύστημα (ΜΟΜΣ), το οποίο έχει ως βάση του τις Μαρκοβιανές αλυσίδες: η συμπεριφορά του καθορίζεται από την οριακή ή σε πεπερασμένο χρόνο συμπεριφορά μιας μη ομογενούς Μαρκοβιανής αλυσίδας. Το ΜΟΜΣ, είναι ένα μαθηματικό μοντέλο, το οποίο αποτέλεσε μια θεωρία ενοποίησης μέσα σε ένα κοινό πλαίσιο, πολλών γνωστών στοχαστικών μοντέλων προγραμματισμού ανθρώπινου δυναμικού. Στη συνέχεια επικεντρωνόμαστε στον έλεγχο της συμπεριφοράς του μοντέλου. Για το σκοπό αυτό, ορίζουμε μια σχέση για το αναμενόμενο κόστος λειτουργίας και αμοιβών του ΜΟΜΣ. Στη σχέση αυτή δίνουμε τη γενικότερη δυνατή μορφή, έτσι ώστε να περιλαμβάνει ως ειδικές περιπτώσεις αρκετές από τις παραλλαγές των συναρτήσεων κόστους-αμοιβών που υπάρχουν. Τέλος, με τη βοήθεια του προγραμματισμού στόχων (Goal Programming), ελέγχουμε τις ροές του ΜΟΜΣ προκειμένου να επιτευχθεί μια ικανοποιητική συμπεριφορά σύμφωνα με κάποιους στόχους, καθώς το σύστημα περνάει τις τρεις φάσεις λειτουργίας του, δηλ. την παροδική, την ημι-παροδική και τη φάση στατιστικής ισορροπίας. / Manpower planning deals with aspects of human resources management and has been given considerable attention in the last decades. In the attempt to simulate the evolution of a manpower system and predict its future properties, mathematical models were proved to be extremely helpful both for descriptive and optimization purposes. Manpower systems have been modeled in several ways, deterministic or stochastic. The attempt of determine and regulate future structures in a manpower planning system is based mainly on the selection of appropriate recruitment distribution vectors. This effort gives rise to the control problem in mathematical manpower planning. The control of manpower systems has been of considerable concern in recent times. In a series of articles and books beginning back in the early 70's, the problem of finding appropriate recruitment policies was considered, and various mathematical models were developed according to several criteria and practical considerations. In the present work aspiration levels and priorities using goal programming are employed in a NHMS which evolves in three phases, the transient, the semi-transient and the equilibrium phase. The general goal programming framework is used in several variations which depend on the phase, in order to detect appropriate input policies that can achieve a satisfactory trade off between operational cost and target attainability.

- / -

Ο Ακέραιος Προγραμματισμός είναι κλάδος του Γραμμικού Μαθηματικού Προγραμματισμού, και αποτελεί τμήμα της συνδιαστικής βελτιστοποίησης. Στόχος της χρήσης του είναι η βελτιστοποίηση συστημάτων παραγωγής ή διοίκησης. Ο Ακέραιος Προγραμματισμός χρησιμοποιείται για την επίλυση πρακτικών προβλημάτων, όπως: • Χρονοδιαγράμματα (Scheduling) • Σχεδιασμός παραγωγής • Παράλληλη εκτέλεση εργασιών • Τηλεπικοινωνίες Μπορεί να φαίνεται ότι τα προβλήματα ακεραίου προγραμματισμού είναι εύκολο να λυθούν. Παρ’όλ’αυτά, κάτι τέτοιο δεν ισχύει, διότι οι αστρονομικά μεγάλοι ακέραιοι αριθμοί, καθώς επίσης και η στρογγυλοποίηση και αφαίρεση μη ακεραίων λύσεων από ένα πρόβλημα γραμμικού προγραμματισμού οδηγούν σε προβλήματα και λανθασμένα συμπεράσματα. Οι κυριότερες τεχνικές Ακεραίου Προγραμματισμού είναι οι εξής: • Μέθοδος κλάδου και φραγής (Branch and Bound) • Τεχνικές περιορισμού του εφικτού χώρου (Cutting Planes) • Μέθοδοι απαρίθμησης • Διαμεριστικοί αλγόριθμοι • Αλγόριθμοι βασισμένοι στη θεωρία ομάδων (Gomory) Η προπτυχιακή αυτή διπλωματική εργασία έχει στόχο να παρουσιάσει δύο από αυτές τις τεχνικές λεπτομερώς, την μέθοδο κλάδου και φραγής και τεχνικές περιορισμού του εφικτού χώρου, και να κάνει κατανοητή τη χρησιμότητα των αλγορίθμων αυτών μέσα από παραδείγματα που αφορούν προβλήματα ακέραιου προγραμματισμού. / Integer Programming is a branch of Linear Mathematical Programming, and is part of the combinatorial optimization. The purpose of using the system optimization of production or administration. The Integer Programming is used to solve practical problems, such as: • Timelines (Scheduling) • Production Design • Parallel execution of works • Telecommunications It may seem that the integer programming problems are easy to solve. However, this is not true, because the astronomically large integers, as well as rounding and removing non-integer solutions of a linear programming problem lead to problems and false conclusions. The main technical Integer Programming are: • branch and bound method (Branch and Bound) • Technical limitations of feasible region (Cutting Planes) • Methods of enumeration • Diameristikoi algorithms • Algorithms based on the theory of groups (Gomory) Undergraduate this thesis aims to present two of these techniques in detail, the branch and bound method and techniques to reduce the feasible region, and make understandable the usefulness of these algorithms through examples involving integer programming problems.

Η διάρθρωση της παρούσας διπλωματικής εργασίας είναι η παρακάτω. Στο πρώτο κεφάλαιο γίνεται μια γενική παρουσίαση της Επιχειρησιακής Έρευνας και του Γραμμικού Προγραμματισμού. Ο Γραμμικός Προγραμματισμός έχει ως στόχο τη βελτιστοποίηση της απόδοσης ενός συστήματος. Η λήψη απόφασης για ένα πρόβλημα Γραμμικού Προγραμματισμού βασίζεται στην επιλογή της βέλτιστης λύσης. Το μαθηματικό μοντέλο ενός τέτοιου προβλήματος αποτελείται από μεταβλητές απόφασης, την αντικειμενική συνάρτηση και περιορισμούς. Στο δεύτερο κεφάλαιο παρουσιάζεται η μέθοδος Simplex, που αναπτύχθηκε από τον G. B. Dantzig το 1947. Η μέθοδος Simplex αποτελεί ίσως την πιο αποδοτική και χρησιμοποιημένη μέθοδο για επίλυση προβλημάτων Γραμμικού Προγραμματισμού. Η μέθοδος Simplex είναι μια μέθοδος δυο φάσεων, όπου κάθε φάση χρησιμοποιεί τον αλγόριθμο Simplex. Στην πρώτη φάση στόχος είναι ο προσδιορισμός μιας εφικτής λύσης. Στη δεύτερη φάση στόχος είναι ο εντοπισμός της βέλτιστης λύσης, ξεκινώντας από την εφικτή λύση που έχει βρεθεί στην πρώτη φάση. Παράλληλα περιγράφεται η πινακοειδής μορφή της μεθόδου Simplex (tableau format). Στο τρίτο κεφάλαιο γίνεται παρουσίαση της μεθόδου δικτυωτής Simplex. Πρόκειται για μια μέθοδο που αποτελεί εξειδίκευση του αλγορίθμου Simplex για δίκτυα. Παρουσιάζονται διάφορες βασικές δομές δικτύων. Επιπλέον, αναλύεται το πρόβλημα ελάχιστου κόστους ροής σε ένα δίκτυο. Ακόμα γίνεται αναφορά σε προβλήματα γραμμικού προγραμματισμού που έχουν δομή δικτύου και μπορούν με τη μέθοδο δικτυωτής Simplex να επιλυθούν με πολύ πιο αποδοτικό τρόπο, παρόλο που μπορούν να λυθούν και με το βασικό αλγόριθμο Simplex. Στο τέταρτο κεφάλαιο παρουσιάζονται οι σημαντικότερες εφαρμογές του προβλήματος ελάχιστου κόστους ροής δικτύου. Οι ειδικές περιπτώσεις του προβλήματος ελάχιστου κόστους της ροής δικτύου είναι το πρόβλημα μεταφοράς, το πρόβλημα εκχώρησης, το πρόβλημα μέγιστης ροής και το πρόβλημα της συντομότερης διαδρομής. / The structure of this thesis is the following. In the first chapter Operational Research and Linear Programming are generally presented. Linear Programming aims to optimize the efficiency of a system. Decision making for a problem of Linear Programming is relevant to the choice of the optimal solution. The mathematical model of such a problem consists of decision variables, an objective function and constraints. In the second chapter Simplex method is presented, which was developed by G. B. Dantzig in 1947. The Simplex method is possibly the most efficient and used method for solving Linear Programming problems. The Simplex method is a two phase method, each phase of which uses the Simplex Algorithm. In the first phase, the goal is to determine a feasible solution. In the second phase, the goal is to determine an optimal solution, starting from a feasible solution that has been found in the first phase. Moreover the Simplex method is described in a tabular format (Simplex tableaux). In the third chapter Network Simplex Method is presented. This method is a specialization of the Simplex algorithm for networks. Various network structures are presented. Moreover, the minimum cost network flow problem is analyzed. Furthermore linear programming problems that have network structure can be solved more efficiently using network Simplex method, even though they can be solve using standard Simplex algorithm. In the fourth chapter the most significant applications of the minimum cost network flow problem are presented. These special cases of the minimum cost network flow problem are the transportation problem, the assignment problem, the maximal flow problem and the shortest path problem.

Η διδασκαλία των γενικών αρχών του προγραμματισμού, ειδικά όταν αφορά ηλικίες της πρώτης βαθμίδας εκπαίδευσης, συγκεντρώνει όλο και περισσότερο το ενδιαφέρον της ερευνητικής κοινότητας. Η εργασία αυτή έχει σαν σκοπό να παρουσιάσει μια πρόταση διδασκαλίας της έννοιας της διαδικασίας σε μαθητές πέμπτης και έκτης δημοτικού. Η προτεινόμενη διδακτική παρέμβαση αξιοποιεί το προγραμματιζόμενο ρομπότ δαπέδου Pro-Bot και προσπαθεί να διερευνήσει το βαθμό εξοικείωσης των μαθητών με την έννοια της διαδικασίας στον προγραμματισμό και να ανιχνεύσει τυχόν διδακτικά προβλήματα που προκύπτουν κατά τη διδασκαλία της. Αφού γίνει μια εισαγωγή στην έννοια της ρομποτικής και στα οφέλη που προκύπτουν από την ένταξή της στη μαθησιακή διαδικασία, περιγράφονται διάφορα διαθέσιμα πακέτα και γίνεται εκτενής αναφορά στο προγραμματιζόμενο ρομπότ Pro-Bot. Στη συνέχεια, παρουσιάζεται η έννοια και το περιβάλλον χρήσης της διαδικασίας, ενώ ερευνάται η βιβλιογραφία που σχετίζεται με την εφαρμογή της ρομποτικής στη διδασκαλία των διαδικασιών στην εκπαίδευση. Ακολουθεί η περιγραφή των στόχων και της μεθοδολογίας της έρευνας και παρουσιάζονται αναλυτικά οι δραστηριότητες, συνοδευόμενες από παρατηρήσεις και φωτογραφικό υλικό από την πορεία της διδασκαλίας. Τέλος, μέσα από την αξιολόγηση των φύλλων εργασίας και του υπόλοιπου υλικού, εξάγονται χρήσιμα συμπεράσματα. / Teaching the general principles of programming, especially to primary education students, becomes more and more interesting to the research community. This thesis aims to present a teaching proposal of the concept of procedure to fifth and sixth graders. The proposed approach utilizes the programmable floor robot Pro-Bot and tries to explore the extent to which students get familiar with the concept of procedure in programming and to detect any problems that may arise when teaching. Once introducing the concept of robotics and the arising benefits of its integration into the learning process, various robotic packages available are described followed by a detailed reference to the programmable robot, Pro-Bot. Furthermore, procedure concept and usage environment is introduced, succeeded by literature research related to the application of robotics in teaching procedures, description of the research objectives and methodology and presentation of teaching activities, together with observations and photos of the course of instruction. Finally, through the evaluation of worksheets and the rest of the material, useful conclusions are made.

Το διάνυσμα προτύπων αποτελεί σύνθεση ενός συνόλου χαρακτηριστικών γνωρισμάτων και ταξινομείται σε δύο κατηγορίες: τα αρχικά χαρακτηριστικά γνωρίσματα και ένα σύνολο μη γραμμικών προβολών των αρχικών χαρακτηριστικών γνωρισμάτων. Στην ταξινόμηση, η κατασκευή χαρακτηριστικών γνωρισμάτων είναι ένα βήμα προ-επεξεργασίας στο οποίο ένα ή περισσότερα γνωρίσματα κατασκευάζονται από ένα αρχικό σύνολο. Ο αριθμός και ο τύπος των χαρακτηριστικών γνωρισμάτων είναι κρίσιμα για την ακρίβεια ταξινόμησης και την υπολογιστική πολυπλοκότητα. Καθώς ο αριθμός των χαρακτηριστικών γνωρισμάτων αυξάνει, απαιτούνται πρόσθετα παραδείγματα για να ολοκληρώσουν μια αξιόπιστη διαδικασία κατάρτισης, επιτρέποντας περισσότερες δυνατότητες αξιόπιστης γενίκευσης χωρίς υπέρ-εκπαίδευση αποτελεσμάτων. Σε αυτή τη διπλωματική εργασία εξετάζουμε και αναλύουμε τη χρήση του Γενετικού προγραμματισμού για την προ-επεξεργασία δεδομένων έτσι ώστε να κατασκευάσουμε μη γραμμικά, ιδιαίτερα προφητικά, χαρακτηριστικά γνωρίσματα από τα αρχικά. Για το σκοπό αυτό χρησιμοποιούμε γενετικούς αλγορίθμους και συγκεκριμένα τον C4.5 αλγόριθμο εκμάθησης δέντρων απόφασης, τον G-Net, ένα διανεμημένο εξελικτικό αλγόριθμο ικανό να συμπεράνει τους ταξινομητές από τα προ-συγκεντρωμένα στοιχεία καθώς και τη μέθοδο που βασίζεται στο συνδυασμό της καθιερωμένης τεχνικής της γραμματικής εξέλιξης και των τεχνητών νευρικών δικτύων. Εφαρμόζοντας τον γενετικό προγραμματισμό σε διάφορα σύνολα δεδομένων ταξινόμησης επιτυγχάνουμε μεγαλύτερη ακρίβεια ταξινόμησης. Όλοι οι αλγόριθμοι που χρησιμοποιήθηκαν έδωσαν πολύ καλύτερη απόδοση στα σύνολα δεδομένων όταν συμπεριλήφθηκε μια ενιαία εξελιγμένη μεταβλητή, επιλύοντας προβλήματα που βρίσκονται πολύ συχνά στις εφαρμογές υπολογιστών όπως Ιατρική και ελαττωματική διάγνωση, πρόγνωση, αναγνώριση εικόνας, κατηγοριοποίηση κειμένων, προσαρμοστική σκιαγράφηση χρηστών. / -

- / -