Masteroppgaver i programutvikling

Masteroppgaver i programutvikling og programmeringsteori

• Logikk og algebraiske metoder Oppgaver innen teori, eller i nær tilknytning til teori (Michal Walicki)
• Programmeringsspråk og -teknologi Både praktisk og teoretisk rettede oppgaver innen programmeringsspråk og verktøystøtte for programmering og testing; integrerte editorer (Eclipse), refaktorering, programoptimisering, ... (Anya Helene Bagge / Eva Burrows / Magne Haveraaen)
• Constraint-programmering Programmeringsmetoder for å løse optimeringsproblemer (Marc Bezem)

Logic and Algebraic Methods

Logical and algebraic methods

Various master projects based on logical and algebraic methods.

For more information contact supervisor Michal Walicki.

Implementing a SAT-solver

SAT (deciding if a given CNF formula is satisfiable) is one of the central problems for both theoretical reflection and practical applications. There is a biannual SAT Competition, choosing the current best solutions in the world. Implementing a competitive solution goes beyond a master thesis, but the problem amounts to, given a detailed sketch of a novel algorithm for SAT-solving:

• defining it precisely
• implementing and testing it on the existing benchmarks, and
• comparing the results with the best existing solvers.

For more information contact supervisor Michal Walicki.

Ny programmeringsteknologi

Ved Institutt for informatikk ved UiB kan du være med på å utvikle morgendagens programmeringsteknologi, med vekt på utviklingsmetoder, språkabstraksjoner, og verktøystøtte.

Om Masteroppgavene

Masteroppgavene er forslag som utarbeides videre i samråd med veileder. Det går an å dra oppgavene i flere retninger, eller se på relaterte problemstillinger. Oppgavene egner seg for studenter som liker programmering, og er interessert i å jobbe i krysningen mellom teori og praksis.

Alle oppgavene åpner for samarbeid med andre forskere internasjonalt.

About the thesis topics

The topics below are suggestions that will be tuned further in cooperation with the supervisors.  It is possible to focus on different parts of the topics, or look at related challenges instead. The topics are well suited for students who enjoy programming, and would like to work at the threshold between theory and practice.

There are possibilities for international cooperation with other researchers.

Veiledere / Supervisors

Anya Helene Bagge, Eva Burrows and Magne Haveraaen, Institutt for informatikk.

Forbedret enhetstesting

Testing er svært sentralt for å redusere antall feil i programvare, og enhetstesting inngår som daglig aktivitet hos profesjonelle utviklere. Men mye testing er ad hoc, og det blir veldig tilfeldig hva som testes. Det er svært vanskelig å lage gode og nødvendige tester.

I Java, f.eks., må strenge krav oppfylles for å ha full glede av "collection classes" og andre rammeverk. Men hvordan kan vi systematisk og grundig teste at koden vår oppfyller slike krav? Vi jobber med verktøy og teknikker for å utvikle tester basert på spesifikasjoner, og å tilrettelegge dette for vanlige programmører.

Vi har flere mulig prosjekter innen enhetstesting:

• Case study der man tar utgangspunkt i eksisterende kode som allerede er grundig testet (open source, eller fra en bedriftspartner), skriver forbedrede aksiombaserte tester, og så sammenlikner effekten og kompleksiteten til testene.
• Utvikling og eksperimenter med generering av testdata 
• Utvikling og forbedring av testeverktøy for Java, C++ eller Magnolia

Compiler Development with Program Transformation

Magnolia is a new programming language developed at II. This thesis topic is appropriate for students who like programming, are interested in compiler technology and aren’t afraid to explore new programming paradigms. Possibilities include working on code generation (including code generation for exotic architectures like GPUs, FPGAs, supercomputers), program analysis, program optimisation or compiler infrastructure.

Programming with Concepts and Axioms

Concepts and axioms provide a way of declaring interfaces and behaviour of classes and functions. We’re exploring the use of concepts to structure programs, and the use of axioms for program testing and optimisation. This topic is about exploring the use of concepts and axioms in practical programming, taking part in the design of the Magnolia programming language, and developing tools supporting the use of concepts and axioms. A possible project is to develop an application using this approach, and then compare the experience to traditional development techniques.

User-Defined Program Transformations

Program transformation uses rewrite rules to change one program into another, and is useful in program optimisation, generative programming, compilation, program analysis, etc. Embedding support for program transformation directly in a programming language opens possibilities for libraries that optimise themselves and wide use of generative techniques to save developer time. This thesis topic will look at existing languages with powerful macro or transformation abilities and develop transformation features for the experimental Magnolia programming language.

Integrated Development Environments

Integrated Development Environments (IDEs) like Eclipse offer programmers convenient features like code refactoring, online API help, outlines, instant feedback on code errors and much more.  Developing a full-featured IDE for a language is a huge undertaking.  In this project we want to look at tools that make it easier to generate language plugins for Eclipse and/or develop specific plugin features.

Constraint Programming

Job Scheduling

PDDL (http://en.wikipedia.org/wiki/Planning_Domain_Definition_Language) is a language to specify planning and scheduling problems. A number of systems accept PDDL input and try to solve the specified problem. Examples of such systems are:

- blackbox (http://www.cs.rochester.edu/~kautz/satplan/blackbox/)

- FF (http://www.loria.fr/~hoffmanj/ff.html).

A typical problem is called "Jobshop", where a number of jobs have to be done in the shortest possible time. Jobs use specified resources (f.e., a machine) of limited capacity. There may be dependencies between the jobs (f.e., job A can only start if jobs B and C are finished). There may be additional constraints, for example, concerning safety (no welding and painting at the same time on the same location!).

The aim is to translate an existing set of stylized but realistic scheduling problems found in the oil industry to PDDL and to try to solve them. The solutions should be compared to existing solutions found with Ilog.

The project will be carried out in collaboration with Epsis AS.

For more information contact supervisor Marc Bezem.

Solving max-constraints

A max-constraint is a constraint of the form max(x,y) + k >= z, where x,y and z are variables and k is a constant. Sets of max-constraints are applied in so-called discrete event systems. The aim of the project is to implement and test different algorithms for solving sets of max-constraints.

As an example, solve: u-10 >= x, z >= y, max(x,y)-1 >= z, max(x,u)+25 >= z

For more information contact supervisor Marc Bezem.