Augmented reality (AR) is an innovative use of computer graphics in combination with real world data to create a new kind of video image. AR seamlessly integrates technology with the real world, allowing for a naturally enhanced computing. Nonograms, also known as Paint by Numbers or Griddlers are logic puzzles in which cells in a grid have to be colored or left blank according to numbers given at the side of the grid to reveal a hidden picture. In this puzzle type, the numbers measure how many unbroken lines of filled-in squares there are in any given row or column. Aim of this project is to implement and compare nonogram solution algorithms and find out which algorithm is suitable for mobile device running Android operating system. / Papildyta realybė yra inovatyvus kompiuterinės grafikos ir realaus pasaulio vaizdų panaudojimas, sukuriantis naują vaizdą. Papildyta realybė sklandžiai integruoja technologijas realiame pasaulyje, leisdama natūraliai naudotis naujausiomis technologijomis. Nonogramos, dar žinomos kaip Japoniški gryžiažodžiai, yra loginis galvosūkis. Norint išspręsti šį galvosūkį lentelės langeliai turi būti nuspalvinti arba palikti tušti priklausomai nuo skaičių, esančių lentelės šone ir viršuje, taip atskleidžiant paslėptą paveikslėlį. Šio tipo galvosūkiuose skaičiai parodo kiek vientisų užspalvintų langelių yra duotoje eilutėje arba stulpelyje. Šio darbo tikslas yra suprogramuoti ir palyginti nonogramų sprendimo algoritmus ir nustatyti, kuris iš jų yra tinkamesnis naudoti išmaniuosiuose telefonuose su Android operacine sistema.

Course timetabling is a well known constraint satisfaction optimization (CSOP) problem, which needs to be solved in educational institutions regularly. Unfortunately, this course timetabling problem is known to be NP-complete [7, 39]. This M.Sc. thesis presents a multi-phase approach to solve the university level course timetabling problem. We decompose the problem into several sub-problems with reduced complexity, which are solved in separate phases. In phase-1a we assign lectures to professors, phase-1b assigns labs and tutorials to academic assistances and graduate assistants. Phase-2 assigns each lecture to one of the two day-sequences (Monday-Wednesday-Friday or Tuesday-Thursday). In Phase-3, lectures of each single day-sequence are then assigned to time-slots. Finally, in phase-4, labs and tutorials are assigned to days and time-slots. This decomposition allows the use of different techniques as appropriate to solve different phases. Currently different phases are solved using constraint programming and integer linear programming. The multi-phase architecture with the graphical user interface allows users to customize constraints as well as to generate new solutions that may incorporate partial solutions from previously generated feasible solutions. / ix, 117 leaves ; 29 cm

This document presents a synthesis of the research results conducted in the eld of software veri cation for model-driven engineering (MDE). MDE is becoming one of the dominant software engineering paradigms in the industry. The main characteristic of MDE is the use of software models and model manipulation operations as main artifacts in all software engineering activities. This change of perspective implies that correctness of models (and model manipulation operations) becomes a key factor in the quality of the nal software product. The problem of ensuring software correctness is still considered to be a Grand Challenge for the software engineering community. At the modellevel, we are still missing a set of tools and methods that helps in the detection of defects and smoothly integrates in existing MDE-based tool-chains without an excessive overhead. Characteristics of existing tools, which require designer interaction, deep knowledge of formal methods or extensive manual model annotations seriously impair its usability in practice. In this document, we present our pragmatic set of techniques for formal model veri cation to overcome these limitations. We call our techniques pragmatic because they try to nd the best trade-o between completeness of the veri cation and the usability of the process.

This thesis focuses on constraints for membership in formal languages under both the systematic search and stochastic local search approaches to constraint programming (CP). Such constraints are very useful in CP for the following three reasons: They provide a powerful tool for user-level extensibility of CP languages. They are very useful for modelling complex work shift regulation constraints, which exist in many shift scheduling problems. In the analysis, testing, and verification of string-manipulating programs, string constraints often arise. We show in this thesis that CP solvers with constraints for membership in formal languages are much more suitable than existing solvers used in tools that have to solve string constraints. In the stochastic local search approach to CP, we make the following two contributions: We introduce a stochastic method of maintaining violations for the regular constraint and extend our method to the automaton constraint with counters. To improve the usage of constraints for which there exists no known constant-time algorithm for neighbour evaluation, we introduce a framework of using solution neighbourhoods, and give an efficient algorithm of constructing a solution neighbourhood for the regular constraint. In the systematic search approach to CP, we make the following two contributions: We show that there may be unwanted consequences when using a propagator that may underestimate a cost of a soft constraint, as the propagator may guide the search to incorrect (non-optimum) solutions to an over-constrained problem. We introduce and compare several propagators that compute correctly the cost of the edit-distance based soft-regular constraint. We show that the context-free grammar constraint is useful and introduce an improved propagator for it.

Natural language generation (NLG), the problem of creating human-readable documents by computer, is one of the major fields of research in computational linguistics The task of creating a document is extremely common in many fields of activity. Accordingly, there are many potential applications for NLG - almost any document creation task could potentially be automated by an NLG system. Advanced forms of NLG could also be used to generate a document in multiple languages, or as an output interface for other programs, which might ordinarily produce a less-manageable collection of data. They may also be able to create documents tailored to the needs of individual users. This thesis deals with document structure, a recent theory which describes those aspects of a document’s layout which affect its meaning. As well as its theoretical interest, it is a useful intermediate representation in the process of NLG. There is a well-defined process for generating a document structure using constraint programming. We show how this process can be made considerably more efficient. This in turn allows us to extend the document structuring task to allow for summarisation and finer control of the document layout. This thesis is organised as follows. Firstly, we review the necessary background material in both natural language processing and constraint programming.

Thesis (M.S.)--University of Texas at El Paso, 2007. / Title from title screen. Vita. CD-ROM. Includes bibliographical references. Also available online.

Thesis (Ph. D.)--University of Canterbury, 2007. / Typescript (photocopy). Includes bibliographical references. Also available via the World Wide Web.

Thesis (Ph. D.)--George Mason University, 2007. / Title from PDF t.p. (viewed Jan. 18, 2008). Thesis directors: Paul Amman, Duminda Wijesekera. Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Information Technology. Vita: p. 198. Includes bibliographical references (p. 189-197). Also available in print.

Thesis (M.Sc.)--Victoria University of Wellington, 2008. / Includes bibliographical references.

Thesis (Ph. D.)--University of Washington, 1997. / Vita. Includes bibliographical references (p. [177]-184).