Στατική και δυναμική οπτικοποίηση αλγόριθμων δικτύων

Abstract

The scientific discipline of Algorithm Visualization, which is a subcategory of Software Visualization, aims to facilitate the understanding of computer algorithms. In this doctoral thesis a new software tool is proposed, that has been implemented to fulfil the same aim. The software tool has been implemented in Java and can be executed either remotely as Java applet or locally as standalone Java application. It encompasses visualizations for graph and network optimization algorithms. The didactic tool can be used by students who want to understand some of the implemented algorithms, according to their own pace of learning. Moreover it can be used by instructors during tutoring, while they are trying to explain algorithms to students or while they grade exams or students’ assignments. The software’s features are: inclusion of an interactive graph editor, its customization to user’s personal preferences, allowance user’s input to algorithms, its highly degree of interactivity and illustration of execution history for an algorithm’s visualization. The above characteristics combined with static and dynamic visualization of the Network Simplex algorithm constitute the contribution of this thesis. Several studies have been carried out to evaluate the educational effectiveness of algorithm visualization tools and to investigate the educational requirements of these tools. Despite the mixed results of these studies, one is the common denominator: algorithm visualization helps students to understand algorithms in a better way. The empirical evaluation that we performed using our software tool showed, that students who used it comprehended difficult notions of a specific algorithm much better than those students who did not use it.

Η επιστημονική περιοχή της Οπτικοποίησης Αλγορίθμων, η οποία αποτελεί μια υπο- περιοχή της Οπτικοποίησης Λογισμικού, αποσκοπεί στο να καταστήσει την κατανόη- ση των αλγορίθμων πιο εύκολη. Στην παρούσα διατριβή περιγράφεται ένα λογισμικό που υλοποιήθηκε για τον ίδιο σκοπό. Το λογισμικό είναι γραμμένο στη γλώσσα προ- γραμματισμού Java και μπορεί να εκτελεστεί είτε μέσω του Διαδικτύου ως Java Applet είτε τοπικά ως Java εφαρμογή. Το προτεινόμενο διδακτικό εργαλείο οπτικοποιεί αλγορίθμους γραφημάτων και δικτυακής βελτιστοποίησης. Το λογισμικό μπορεί να χρησιμοποιηθεί από φοιτητές οι οποίοι θέλουν να κατανοήσουν κάποιον από τους αλγορίθμους που οπτικοποιήθηκαν, σύμφωνα με το δικό τους ρυθμό μάθησης. Μπο- ρεί επίσης να χρησιμοποιηθεί από διδάσκοντες είτε κατά τη διάρκεια της διδασκαλί- ας, στην προσπάθειά τους να εξηγήσουν κάποιον αλγόριθμο στους φοιτητές ή για την αξιολόγηση (βαθμολόγηση) γραπτών εξετάσεων ή εργασιών των φοιτητών. Τα χαρακτηριστικά του λογισμικού όπως είναι: η ύπαρξη ενός συντάκτη γραφημά- των, η προσαρμογή του λογισμικού στις προσωπικές προτιμήσεις του χρήστη, η εισα- γωγή δεδομένων στους αλγορίθμους, ο υψηλός βαθμός διαλογικότητας, η απεικόνιση της ιστορίας της εκτέλεσης μιας οπτικοποίησης καθώς και η στατική και δυναμική οπτικοποίηση (κίνηση) του αλγορίθμου Network Simplex παρουσιάζονται για πρώτη φορά στο λογισμικό που αναπτύχθηκε. Αρκετές έρευνες έχουν διεξαχθεί με σκοπό να αξιολογήσουν την εκπαιδευτική απο- τελεσματικότητα λογισμικών οπτικοποίησης αλγορίθμων αλλά και να διερευνήσουν τα επιθυμητά, από παιδαγωγική άποψη, χαρακτηριστικά τους. Αν και τα αποτελέσμα- τα των ερευνών είναι ανάμικτα, ένα είναι το κοινό συμπέρασμα: η οπτικοποίηση αλ- γορίθμων βοηθάει στην καλύτερη κατανόησή τους. Η εμπειρική αξιολόγηση που πραγματοποιήσαμε με το λογισμικό έδειξε ότι οι φοιτη- τές που το χρησιμοποίησαν κατανόησαν σαφώς καλύτερα βαθύτερες έννοιες ενός συ- γκεκριμένου αλγορίθμου, από τους φοιτητές που δεν έκαναν χρήση του λογισμικού.