FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:   || 2 | 3 | 4 | 5 |   ...   | 10 |

«GraphBench: Exploring the Limits of Complexity with Educational Software A dissertation submitted to the SWISS FEDERAL INSTITUTE OF TECHNOLOGY ZURICH ...»

-- [ Page 1 ] --

DISS. ETH NO. 16392

GraphBench: Exploring the Limits of

Complexity with Educational Software

A dissertation submitted to the



for the degree of

Doctor of Sciences ETH Z¨rich


presented by

Markus Andreas Br¨ndle


Dipl. Informatik-Ing. ETH

born 22.05.


citizen of Mosnang SG

accepted on the recommendation of

Prof. Dr. Bertrand Meyer, examiner Prof. Dr. J¨rg Nievergelt, co-examiner u Prof. Dr. Angelika Steger, co-examiner Acknowledgements This dissertation and the software GraphBench resulted from the support and contributions of many people to whom I am very thankful and wish to express my gratitude.

I first would like to thank J¨rg Nievergelt and Werner Hartmann for inu spiring me to work on this thesis. J¨rg Nievergelt has been an extraordinary u supervisor, advisor and personal mentor throughout my whole dissertation.

His interest, commitment, ideas and visions are the cornerstones of my work and for that I am very grateful. Werner Hartmann was the didactic voice and his comments and suggestions account for the usability of GraphBench. I would especially like to thank him for being a friend I could always talk to.

I am also indebted to Bertrand Meyer for allowing me to finish my thesis under his supervision. I greatly appreciate his contributions and his interest in a topic originally not within his research area.

I was very glad that Angelika Steger agreed to be co-advisor. Peter Widmayer and Juraj Hromkovic deserve my gratitude for the time I spent in their groups and for their support.

Matthias Dreier was involved in the beginning of the project and was very much responsible for the good start and the solid software foundation of GraphBench. Raimond Reichert, Ruedi Arnold and Judith Zimmermann greatly supported my work with their time, comments and suggestions.

Many others have directly or indirectly contributed to my work and deserve to be mentioned: Nina Huggenberger, Floris Tschurr, Hon Wai Leong and the whole reasearch group of Betrand Meyer, in particular Michela Pedroni and Till Bay.

Finally, I thank Ursina, my parents and my brother for putting up with me and taking my mind of computers every once in a while.

iii iv Abstract In today’s information society it has become ordinary for students to use computers to study. Educational software is increasingly being developed for all kinds of subjects and school levels. Although a broad range of computer science areas is covered, topics that admit intuitively meaningful graphic representations are almost exclusively considered. Mathematically


topics that are more difficult to present, as well as to understand, still challenge our ability to create effective computer support. The theory of NP-completeness in particular has been almost neglected by educational software, despite its importance in the theory of computation and in computer science education. Yet it is precisely in such a highly specialized, abstract topic that computer-based learning environments might do their best job.

In this thesis we have developed GraphBench, a highly interactive learning environment for the theory of NP-completeness. GraphBench, as well as the techniques and principles on which it is built, is the main contribution of this dissertation. Our software provides students with an intuitive approach to an otherwise abstract and complex topic. GraphBench features eight different NP-complete problems and nine different polynomial time reductions. Our software offers separate environments for all featured NP-complete problems and polynomial time reductions.

GraphBench combines traditional didactic with new computer-based approaches to foster an intuitive understanding of the basic underlying concepts.

In this thesis we identify difficulties that arise when developing educational software for abstract topics and present several didactic concepts and implementation approaches to overcome them.

We have successfully used GraphBench in various courses on the theory of computation at the Swiss Federal Institute of Technology ETH, at the National University of Singapore and at the Free University of Bolzano. The highly positive feedback from professors and students justifies our approach and shows the need for learning environments for highly specialized, abstract topics.

–  –  –

Overview In this chapter we give a short overview of this thesis. We summarize our motivation and the work that has been done. We further give a short introduction to our learning environment GraphBench and shortly look at its use.

1.1 Motivation The theory of computation teaches students the limits of computers, e.g. what a computer can and cannot compute. It is fundamental to computer science and thus an important part of any computer science education. Despite of its importance students often have difficulties with the theory of computation and lack motivation to study it. Among the topics that students typically struggle with is the theory of NP-completeness and polynomial time reductions. This theory defines a class of problems that are difficult, i.e. very time consuming, for a computer to solve.

Computer-based learning environments can help students overcome their difficulties and help them gain a better understanding. While some topics of the theory of computation are well covered by educational software, the theory of NP-completeness has been almost neglected. It is a highly abstract and rigorously formal topic. This not only makes the theory difficult for students to understand, but also the development of a learning environment for this topic challenging. Topics that are either only highly abstract or only rigorously formal are easier to understand. Students have for instance little problems to use the learning environment “Tarkis world” (Barwise and Etchemendy, 1997) that covers the very formal but not very complex topic of first-order logic.

Computer games on the other hand are often highly complex, but because they are also quite intuitive they are well feasible to master. It is the combination of abstraction and formality that challenges the human mind and makes the design of a learning environment difficult (figure 1.1).

–  –  –

Fig. 1.1: Software for either a only highly complex or a only rigorously formal topic is easier to master than software for a topic that is both.

The importance of the theory of NP-completeness, students’ problems with the topic and the lack of learning environments motivated us to approach the theory of complexity and design a learning environment for NP-completeness.

1.2 Contributions In this thesis we focus on complexity theory. We have developed GraphBench, a highly interactive learning environment for the theory of NP-completeness, i.e. for NP-complete problems and polynomial time reductions. GraphBench provides students with an intuitive approach and combines traditional didactic concepts with new computer-based methods. It fosters an intuitive understanding of the basic underlying concepts and allows students to experiment and thus to discover the theory of NP-completeness.

GraphBench features eight different NP-complete problems, e.g. Satisfiability or Graph Colorability, and nine different polynomial time reductions, e.g. reducing 3CNF Satisfiability to Clique or Vertex Cover to Hamilton Circuit. GraphBench offers a separate environment for every problem and for every reduction. The environments all share a common user interface and similar functionality. The problems and reductions were selected according to several criteria, e.g. their frequent use in computer science education.

GraphBench actively involves students and provides them with a “handson” approach. Students can for instance manipulate and create new problem instances, or actively investigate polynomial time reductions. The learning environment allows students to solve arbitrary examples by hand or to use built-in solution algorithms. GraphBench fosters an intuitive understanding by providing various, intuitive graphical representations of the NP-complete problems, polynomial time reductions, and solution algorithms.

In this thesis we have identified difficulties that arise when developing educational software for abstract topics and present several didactic concepts and implementation approaches to overcome them, e.g. “Selective Level of Detail”.

We illustrate the concepts with examples and state their learning benefits.

This thesis consists of work in the field of computer science education and didactics as well as work in the field of software engineering. With GraphBench we have developed a Java software framework for computer-based learning environments. It consists of several independent libraries that can be reused to create learning environments for topics other than complexity theory. The framework is designed to facilitate maintaining and extending existing content, e.g. adding new NP-complete problems or solution algorithms.

We have successfully used our learning environment GraphBench in various courses on the theory of computation at the Swiss Federal Institute of Technology ETH, at the National University of Singapore and at the Free University of Bolzano. It was used as a demonstrational tool in class as well as for student assignments and semester projects.

1.3 Conclusions With GraphBench we have developed a learning environment for a topic that has otherwise been almost neglected by educational software. The fundamental importance of complexity theory in computer science and student’s struggle with the topic show the need for such a learning environment.

GraphBench conforms to today’s criteria for educational software, e.g. a high level of interactivity or active user involvement. We have developed a software framework and new didactic approaches that can be adapted for other topics.

The widespread use of GraphBench at universities worldwide, and the highly positive feedback from professors and students, convince us that our approach is successful and worth pursuing.

Chapter 2

Computer-based learningenvironments: State of the art

Computer-based learning environments are omnipresent in today’s education society and can be found for a wide variety of topics. In this chapter we first analyze the different uses of computers in education and show our idea of utmost computer benefit on learning success. We point out requirements and criteria for successful computer-based learning environments.

We then focus on computer science education and show the wide range of topics currently addressed by learning environments. We briefly introduce several learning environments and point out where we see room for improvement.

2.1 Computer uses in education: Medium of presentation and subject matter tutor In today’s information society it is not uncommon for students to use computers to study. Educational software is increasingly being developed for all kinds of subjects and school levels. Traditional learning environments like classrooms include infrastructure, information, exercises, tests, teachers or tutors. How do we apply these traditional concepts to computer aided learning? What is needed to create a computer-based learning environment?

Today the computer is mostly used as versatile presentation medium that combines the capabilities of a number of traditional media such as books, movies or audio. The cognitive theory of multimedia learning supports the use of such multimedia presentations. [MM02] state for instance, that animations can improve learning when used in ways that are consistent to the theory of cognitive multimedia learning. This theory is based on three assumptions: 1) dual-channel assumption – the idea that humans possess separate information processing channels for visual and auditory material, 2) limited capacity assumption – the idea that humans are limited in the amount of information they can process at one time in each channel, 3) active processing – the idea that meaningful learning occurs when learners engage in cognitive processes, e.g. selecting relevant material (see e.g. [May01]).

Using computers and multimedia does not exhaust the strength of computers in learning by far. Computer-based technologies present a number of possibilities to further improve learning. Educational software can for instance provide access to a large collection of documents and facts. An additional advantage, compared to traditional media, is obtained if the data is kept upto-date. In business and finance, for example, the software might access daily currency exchange rates and stock quotations that are freely available on the Internet.

Today’s educational software often does not allow students to change the texts, narrations, sounds or animations, e.g. to change the initial configuration of an animated experiment. However, allowing students to manipulate underlying objects, such as examples or solutions, can improve learning. For instance, instead of seeing a pre-computed animation, the student can now configure the initial parameters and then watch a simulation based on his settings.

An even greater benefit arises when the software is able to produce new content depending on actions by the student, e.g. generate an unlimited number of exercises with various difficulty levels, solve arbitrary examples or provide meaningful feedback to actions or questions by the student. This implies that it must embody a model of its domain of discourse that enables it to derive facts not explicitly foreseen and stored. We refer to such systems as subject matter tutors. In this thesis we have developed a learning environment containing several subject matter tutors, we introduce the system and the subject matter tutors in detail in chapters 6, 7.

Pages:   || 2 | 3 | 4 | 5 |   ...   | 10 |

Similar works:

«Smear Campaigns Steven Connor A talk given at the Unclean Beings symposium, Wellcome Collection, London, 16 July 2011. It is customary, almost, on occasions such as this, one might say, compulsory, to say that dirt is matter out of place, or, sometimes, „merely‟ matter out of place. As the advertising posters for this exhibition also reassure us, we are indebted for this insight to the sociologist, Mary Douglas. In fact, however, though she provides some neat and striking demonstrations of...»

«Pázmány Péter Katolikus Egyetem Kánonjogi Posztgraduális Intézet VALLÁSKÜLÖNBSÉG KÉRDÉSE A HÁROM MONOTEISTA VILÁGVALLÁSBAN KÜLÖNÖS TEKINTETTEL KATOLIKUSOK ÉS MUSZLIMOK KÖZÖTT A 21. SZÁZADI EURÓPÁBAN Doktori disszertáció Készítette: Csordás Eörs Moderátor: DDr. PhD Habil. Szuromi Szabolcs Anzelm OPraem egyetemi tanár Budapest 2009 Tartalom Tartalom Rövidítések Bevezetés 1 A HÁROM MONOTEISTA VILÁGVALLÁS 1.1 A vallások meghatározása és felosztása 1.2 A...»

«Spiritual and Social Trends and Patterns in the Christian Reformed Church in North America A report on the CRCNA 150th Anniversary Survey, 2007-2008 Rodger Rice, Neil Carlson and Christina Vanden Bosch Foreword by Gerard L. Dykstra September 2009 Prepared for the Christian Reformed Church in North America CENTER FOR SOCIAL RESEARCH A C E N T E R O F C A LV I N C O L L E G E This report is based on research conducted by the Calvin College Center for Social Research with funding and direction...»

«SCHLUSSFOLGERUNGEN DES VORSITZES 1. Der Tagung des Europäischen Rates ging ein Exposé des Präsidenten des Europäischen Parlaments, Josep Borrell, voraus, an das sich ein Gedankenaustausch anschloss.2. Der Europäische Rat weist erneut darauf hin, wie wichtig die gemeinsamen europäischen Werte der Solidarität, der sozialen Gerechtigkeit und der Nachhaltigkeit als Grundlage für die Gestaltung der Unionspolitik sind. Sie bilden den Rahmen, in dem die in diesen Schlussfolgerungen enthaltenen...»

«Von Polysulfanen, hochreaktiven S8-Nanopartikeln und organochalkogenhaltigen Redoxkatalysatoren: Identifizierung und Charakterisierung neuer, potentieller Wirkmechanismen und intrazellulärer Targets Dissertation zur Erlangung des Grades des Doktors der Naturwissenschaften der Naturwissenschaftlich-Technischen Fakultät III -Chemie, Pharmazie, Biound Werkstoffwissenschaftender Universität des Saarlandes Vorgelegt von Dipl.-Chem. Thomas Schneider Saarbrücken Diese Doktorarbeit entstand unter...»

«Formal Specication and Verication of Knowledge and its Application Ralph Miarka miarka@aix520.informatik.uni-leipzig.de Leipzig University Faculty for Mathematics and Computer Science Institute for Computer Science Master's Thesis supervised by Prof. Dr. Heinrich Herre, Leipzig University and Dr. Peter Hrandek, Siemens AG Austria Leipzig, July 1998 Formale Wissensspezikation und -verikation und deren Anwendung Ralph Miarka miarka@aix520.informatik.uni-leipzig.de Universitt Leipzig a Fakultt...»

«Zirkuläre und temporäre Migration Empirische Erkenntnisse, politische Praxis und zukünftige Optionen in Deutschland Studie der deutschen nationalen Kontaktstelle für das Europäische Migrationsnetzwerk (EMN) WorkingPaper WorkingPaper WorkingPaper WorkingPaper WorkingPaper Working Paper 35 WorkingPaper WEMNdesr der Forschungs­ P a p e r des ound k i n g der Nationalen Kontaktstelle gruppe Bundesamtes WorkingPaper erschienen 2011 WorkingPaper WorkingPaper WorkingPaper Kofinanziert durch die...»

«V I K T O R B A B E S ÉLETE ÉS MUNKÁSSÁGA KAPRONCZAY KÁROLY A magyar és az egyetemes orvostörténetírás egyik lényeges feladata az egyetemi v á r o s o k ­ hoz kötődő orvosi iskolák szellemi kisugárzásának feltárása, a k ö l c s ö n h a t á s o k elemzése, az ezekből fakadó szakmai m ű h e l y e k részletes leírása. Alapos ismeretekkel rendelkezünk az első és második bécsi orvosi iskoláról, továbbá a n é m e t egyetemek orvosi karainak...»

«ENVIRONMENTAL AND SOCIAL IMPACT ASSESSMENT Baku – Tbilisi – Ceyhan Oil Pipeline Azerbaijan Prepared for BP By AETC Ltd / ERM December 2002 BTC PIPELINE ESIA AZERBAIJAN FINAL ESIA GENERAL NOTES Project No: P8107 Title: Environmental and Social Impact Assessment Baku – Tbilisi – Ceyhan Oil Pipeline Azerbaijan Client: BP Issue Date: December 2002 Issuing Office: Helsby Authorised by: Project Manager Date: Authorised by: Project QA Rep Date: AETC has prepared this report for the sole use of...»

«Научный журнал КубГАУ, №104(10), 2014 года 1 УДК 575:75 UDC575:75 ПРОИЗВЕДЕНИЯ ЖИВОПИСИ В PAINTINGS IN TEACHING THE DISCIPLINE ПРЕПОДАВАНИИ ДИСЦИПЛИНЫ OF GENETIC MONITORING «ГЕНЕТИЧЕСКИЙ МОНИТОРИНГ» Цаценко Людмила Владимировна Tsatsenko Luidmila Vladimirovna д.б.н., профессор, кафедра генетики, селекции и Dr.Sci.Biol., professor,...»

«54 ica Resumenes AbstRActs International Congress of Americanists Congresso Internacional de Americanistas Congreso Internacional de Americanistas       Estimados participantes del 54 ICA!  Esta memoria USB contiene el programa completo del ICA 54, incluyendo los resumenes de todos los  simposios y ponencias correspondientes, asi como las fechas, horas y número de sala de cada  simposio. También encontrará un calendario de los simposios.  ...»

«Konkretisierungsstrategien für Art. 2 der UN-Klimarahmenkonvention Konrad Ott Gernot Klepper Stephan Lingner (Studienleitung) Achim Schäfer Jürgen Scheffran Detlef Sprinz mit einem Beitrag von Meinhard Schröder Endbericht März 2004 on behalf of the Federal Environmental Protection Agency of Germany (UBA) FZK 202 41 252 Europäische Akademie GmbH Wilhelmstr. 56, D-53474 Bad Neuenahr-Ahrweiler, Tel. (0)2641/973-300 Berichts-Kennblatt Berichtsnummer UBA-FB 202 41 252 Titel des Berichts...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.