Browsar Examensarbeten för masterexamen // Master Theses efter Program "Computer science – algorithms, languages and logic (MPALG), MSc"
Visar 1 - 20 av 270
Sökresultat per sida
- Post3D head scanner(2013) Jedvert, Magnus; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)The advent of cheap depth cameras such as Microsoft Kinect together with modern reconstruction algorithms implemented for the Graphics Processing Unit (GPU) o ers the potential of many new exciting applications. In this thesis, a scanning booth equipped with three Kinect cameras is built, where a user can scan their head and upper body into a high-quality textured 3D model. This is done using a variant of the KinectFusion algorithm, adapted to work with multiple cameras. The system operates in real-time and the reconstructed model is presented within seconds.
- PostA Comparative Study of Segmentation and Classification Methods for 3D Point Clouds(2016) NYGREN, PATRIK; Jasinski, Michael; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)Active Safety has become an important part of the current automotive industry due to its proven potential in making driving more joyful and reducing number of accidents and causalities. Different sensors are used in the active safety systems to perceive the environment and implement driver assistance and collision avoidance systems. Light detection and ranging (LIDAR) sensors are among the commonly utilized sensors in these systems; a LIDAR produces a point cloud from the surrounding and can be used to detect and classify objects such as cars, pedestrians, etc. In this thesis, we perform a comparative study where several methods to both segment Region Growing and Euclidian Clustering) and classify (Support Vector Machines, Feed Forward Neural Networks, Random Forests and K-Nearest Neighbors) point clouds from an urban environment are evaluated. Data from the KITTI database is used to validate the methods which are implemented using the PCL and Shark library. We evaluate the performance of the classification methods on two different sets of developed features. Our experiments show that the best accuracy can be obtained using SVMs, which is around 96.3% on the considered data set with 7 different classes of objects.
- PostA Computational Grammar and Lexicon for Maltese(2013) Camilleri, John J.; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)Maltese is the national language of Malta and an official language of the European Union. While classified as Semitic, Maltese has been heavily influenced by the Romance languages and English, and features both root-and-pattern and concatenative morphologies. Despite its active use, the language is highly under-resourced in digital terms. This thesis contributes two computational resources for Maltese: a grammar and an online full-form lexicon. The first part of this thesis deals with a computational grammar for Maltese, which is implemented using the Grammatical Framework (GF). GF is a multilingual grammar formalism based on using abstract syntax trees as language-independent semantic representations. Its Resource Grammar Library (RGL) already covers the morphology and basic syntax of some 27 languages from around the world. Maltese is the 28th addition to the RGL, and the first Semitic language in the library to be completed. The smart paradigms implemented in the morphological part of grammar allow full inflection tables to be produced for any lexical unit, often requiring only a lemmatised form. This report looks at some of the more interesting implementational details of the grammar, discussing the compromises that had to be made along the way. The second part covers the collection of various Maltese lexical resources into a single searchable collection, using a schema-less database to accommodate partial data from heterogeneous sources. We then use the smart paradigms from the morphological part of the grammar to automatically produce some 4 million inflection forms and extend the collection into a full-form computational lexicon, which can be used in for morphological lookup and spell checking. All the software and resources described in this thesis are open-source and free to use for any purpose.
- PostA Constraint Programming Approach to Finding Stable Matchings within Airline Manpower Planning(2017) Jarmar, Jakob; Sörensson, Fabian; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)The objective of airline manpower planning is to have the right number of pilots with the right qualifications at the right time. To accomplish this, one has to solve the subproblem of assigning pilots to promotion courses such that pilots’ seniority ranks and preferences are taken into account: no senior pilot should be able to find a junior pilot with a promotion that the senior pilot would have preferred. We call this subproblem the airline promotion assignment problem (APA). The objective of this thesis is to develop an efficient model for APA. We show how APA can be modelled as a stable matching problem, and more specifically how it can be formulated as an instance of the hospitals/residents problem with ties and forbidden pairs. A constraint satisfaction problem model for APA is presented, which we have implemented in a constraint programming system. We also present a model for an extension to APA, which we call the airline promotion assignment problem with detailed preferences (APA-D), and which involves additional rules used within a specific airline. We show results from running our constraint programming implementation on different types of test data derived from real airline data. The thesis is concluded with a discussion of our work and some remarks on how the problem could be modelled and solved differently.
- PostA Deflate-like compressor in HOL, Creating executable binaries using CakeML(2022) Carlsson, Eric; Rönning, Li; Chalmers tekniska högskola / Institutionen för data och informationsteknik; Seger, Carl-Johan; Myreen, MagnusDeflate is a well-known file format specification of lossless compression, with implementations in software like gzip and zip. Proving that a compressor following the Deflate algorithm has the property of being entirely reversible is of interest, as Deflate is widely used. The aim of this project is to produce verified binaries for the Deflate algorithm using the interactive theorem prover HOL4 and the CakeML compiler. The implementation consists of three main parts: the LZSS compression algorithm, the Huffman encoding algorithm, and the Deflate algorithm. Since the focus was to properly implement Deflate, the majority of our effort was put into developing the algorithm itself. Due to time constraints however, our implementation reached an executable implementation of a Deflate-like algorithm. While the Deflate algorithm has been implemented and verified before, the work described here is the first to produce an executable binary of a compression specification.
- PostA Formal Semantics for Javalette in the K framework(2022) Burak Bilge, Yalcinkaya; Chalmers tekniska högskola / Institutionen för data och informationsteknik; Abel, Andreas; Myreen, MagnusThis thesis is about developing an executable formal semantics for Javalette in the K framework. Javalette is an imperative programming language. Its syntax is formally specified using BNF (Backus-Naur form) notation, but it does not have a formal semantics. The semantics of the language is informally documented in English. Javalette has several extensions that enrich the language’s syntax and semantics with new types, statements, and expressions. K is a toolset for programming language design and implementation. It provides a specification language for formally defining syntax and semantics. From these definitions, K automatically generates various tools such as parsers, interpreters, model checkers, and deductive verifiers. The purpose of this project is to develop a complete formal semantics for the Javalette language, design an architecture for extending the language modularly and implement language extensions, find and resolve undefined behaviors in the language, and use the formal semantics to develop an input fuzzer for testing Javalette programs and implementations.
- PostA Generator of Incremental Divide-and-Conquer Lexers A Tool to Generate an Incremental Lexer from a Lexical Specification(2015) Hansson, Kristofer; Hugo, Jonas; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)This report aims to present a way to do lexical analysis incrementally instead of the present norm: sequential analysis. In a text editor, where updates are common, an incremental lexer together with an incremental parser could be used to give users real time parsing feedback. Previous work has proven that regular expressions can be implemented incrementally , we make use of these findings in order to show that it can be expanded to a lexical analyzer. The results in this report shows that an incremental lexer is efficient, it can do an update in log n time which makes it suitable when updates are common. In order for an incremental lexer to be applicable it has to be precise, only correctly lexed tokens are relevant. It is required that an incremental lexer is robust, a lexical error for a partial result must be handled gracefully since it may not propagate to the final result. To achieve incrementality a divide and conquer tree structure, fingertrees, is used that stores the intermediate lexical results of all the partial trees. When an update to the tree is made only the effected node and its parents are updated. The state machine in the implementation is generated by Alex since it is efficient and enables support for lexical analysis of different languages. The report finishes with giving suggestions for improvements to the drawbacks found during the work, The suggestions given are mainly for improving space complexity. This report shows that an implementation of an incremental lexer can be precise, efficient and robust.
- PostA hybrid recommender system for usage within e-commerce Content-boosted, context-aware, and collaborative filtering-based tensor factorization recommender system for targeted advertising within e-commerce(2017) Lagerstedt, Marcus; Olsson, Marcus; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)Recommender systems are information filtering systems that try to predict what rating a user would give an item, usually with the goal of recommending, would be high rated items to users. Today there exists recommender systems in most online stores, in one form or another. The complexity of these systems varies greatly, where the less complex ones might base their recommendations on similar products, while others are much more complex, utilizing user modeling etc. This thesis describes changes made to a context-aware and collaborative filtering-based tensor factorization recommender system, in order to adapt it to perform better with the implicit-only data found in e-commerce, specifically garment-based e-commerce. Multiple contexts are evaluated in regard to a specific data set, and the performance impact of the changes proposed are also measured. The evaluation is carried out through use of self-implemented algorithms written in Python. The project resulted in a content-boosted, context-aware, and collaborative filtering-based tensor factorization recommender system made for implicit-only e-commerce data. The results show that the changes proposed in this thesis give a substantial performance increase, while time-based contexts do not seem to increase performance, in regard to the specific data set used for evaluation in this project.
- PostA method for multi-agent exploration planning(2012) Chekanov, Alexander; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)This project is concerned with the problem of exploration planning, which arises in systems of one or several mobile robots set with a task of exploring the map of their environment. Today the most popular algorithm that deals with this problem is the naive (greedy) approach, which is very simple and usually shows reasonably good results. This algorithm performs poorly in the worst case with several robots however. To cope with this problem, a new approach is developed and analyzed. This approach, called coordinated breadth-first search, is shown to guarantee linear scaling and to be asymptotically more efficient than the naive method in the worst case. To test these findings a computer simulation was developed which admits both algorithms and arbitrary maps. Finally, a comparison between the algorithms is made and further improvements are suggested.
- PostA multi-CDN request routing strategy(2015) Söderlund, Oscar; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)In this thesis, we design and implement a multi-CDN request routing strategy for Spotify’s audio files. Through A/B testing, we show that our strategy improves median download latency compared to Spotify’s existing routing strategy. Our strategy groups Spotify’s users by autonomous system number and country, and uses a linear programming model on download latency log messages to generate routing weights on a group-by-group basis. Our linear programming model generates routing weights with the goal of minimising request latencies, while also preserving a number of traffic volume constraints.
- PostA natural language interface for a music database(2011) Diz Pico, Jorge; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)We present an interface for a music database in which the user asks questions and the system replies with the exact information desired. Natural language parsing with the Grammatical Framework was used for input and output processing as to offer multilingual capabilities. The code architecture, from interface to database connection and results treatment, was built with Haskell. Arrows and an increased degree of function modularity were employed, looking for flexibility for future expansions.
- PostA Parallel Intermediate Representation for Embedded Languages(2013) Lång, Ivar; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)This thesis presents a parallel intermediate representation for embedded languages called PIRE, and its incorporation into the Feldspar language. The original Feldspar backend translates the parallel loops of Feldspar to ordinary for loops, meaning that they are not actually parallel in the generated code. We create an alternate backend for the Feldspar project, where the parallel loops of Feldspar are translated as OpenCL kernels that run on the GPU. We show that we gain performance using our new backend for big input sizes compared to the original backend.
- PostA Parametric Fitch-Style Modal Lambda Calculus(2023) Forsman, Axel; Chalmers tekniska högskola / Institutionen för data och informationsteknik; Chalmers University of Technology / Department of Computer Science and Engineering; Abel, Andreas; Valliappan, NachiappanThe necessity modality, denoted by , where the focus lies, has been applied to model staged computations, compartmental purity in functional languages, and more. So called Fitch-style modal deduction, where modalities are eliminated by opening a subproof, and introduced by shutting one, has been adapted for lambda calculi. Different modal logics may be encoded via different open and shut rules. Prior work  has given normalization proofs for four Fitch-style formulations of lambda calculi with different modalities, which required repeating the proofs for each individual calculus. A parametric Fitch-style modal lambda calculus generalizing the variants is presented, in order to avoid the repetition and ease further extensions.
- PostA practical shading model for ray tracing(2016) Käkelä, Aki; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)Photorealistic rendering relies on informative descriptions of its scenes. In particular, the material properties of 3D objects is important to achieve convincing results. The material of an object details how it interacts with light, for instance the color, transparency, and the sharpness of its reflections. What arises in practice is finding a brief description that allows for a wide range of materials to be represented, while preserving photorealism - in other words, a practical material system. These constraints mean that the material parameters should be few and easy to understand, and creating the material definitions themselves must be simple. This report outlines a shading model that attempts to deal with these issues, and presents a collection of base material types that exposes only a few, but powerful, parameters for artists to work with.
- PostA Real-Time Testbed for Distributed Algorithms:Evaluation of Average Consensus inSimulated Vehicular Ad Hoc Networks(2017) Casparsson, Albin; Gardtman, David; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)Intelligent transportation systems consist of applications which use communication capabilities of vehicles to solve tasks that require cooperation with other vehicles. One of the possible applications is cooperative positioning, in which vehicles increase the accuracy of their positions by sharing positioning information with each other. Previous research has suggested using average consensus to share this information. Average consensus is a type of distributed algorithm that, in a system where each node performs a measurement of some value, can make all nodes reach agreement on the average of the set of measurements. This thesis evaluates the performance of average consensus algorithms in vehicular ad hoc networks. Full-scale experiments on vehicular systems are costly, but it is also not necessarily desired to fully simulate a vehicular system. This thesis presents a testbed where we opt to fully simulate the vehicular communication network. The vehicles that are part of the network can be simulated using either virtual nodes or a scaled down physical robot system. An 802.11p wireless network, which has been suggested for vehicular ad hoc networks, is simulated using the ns-3 network simulator. Additionally, some properties that cause the wireless network to be unreliable are simulated. Furthermore, in this thesis, three average consensus algorithms are implemented with some modifications to account for the properties of vehicular ad hoc networks. These algorithms are evaluated in the created testbed, in order to study their performance in such a network. We observe that consensus converges asymptotically in a simulation of randomly moving nodes, and that the consensus states of the nodes oscillate around the true average when new nodes are allowed to enter the system during consensus. The consensus converges to a state that does not necessarily coincide exactly with the true average, which is to be expected since some packets are lost due the simulated wireless network not being fully reliable. We also demonstrate that performing average consensus on the position of an object can improve the precision of driving in a physical system of moving robots.
- PostA RealTime Adaptation of Inverse Kinematics for Motion Capture(2015) Bornold, Jonas; Svantesson, Joanna; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)In this thesis, the process of animating characters from motion capture in real-time is presented. A model of a human skeleton is defined, and the joints of this skeleton are located using positions of markers placed on the body during motion capture. These methods for locating joints are presented and evaluated. During motion capture, markers might be occluded from cameras, resulting in joint positions that can not be determined. This problem is, in this project, solved by estimating the missing joint positions with the technique Inverse Kinematics, in a way that, to our knowledge, has not been used before. Four different inverse kinematics solvers were implemented in order to determine if one algorithm performs better than other. The implemented algorithms are the Jacobian Transpose, Damped Least Squares (DLS), Cyclic Coordinate Descent (CCD), and Forward and Backward Reaching Inverse Kinematics (FABRIK). The implemented system receives marker positions from the motion capture system in real-time and rst performs joint localization followed by estimation of missing positions with IK. The result is a skeleton with a similar pose as the actor frame by frame. The application works well, but need improvements for smooth animation. The fastest and most accurate algorithm was CCD, but the other three are promising for possible future implementations.
- PostA simulation based forecast algorithm for public transportation(2014) Daugaard, Jonathan; Larkö, Erik; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)This thesis describes a simulation based system for forecasting arrival and departure times in complex public transit systems. The variables included in the calculations are: time of day, vehicle schedule adherence, estimated passenger count on stop, interactions with other vehicles and vehicle position from both historical and contemporary data. The use of a simulation based algorithm simpli es the implementation of a complex model with a great number of di erent dependencies. Additionally, creating a forecast using historical data while looking at di erent data features to nd similarities gives a more accurate forecast than just looking at a moving average using data from the current day.
- PostA Survey of Transport Simulation Tools - Comparing free tools for simulating autonomous vehicles in traffic and logistics networks(2019) Hultén, Jonas. A.; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)With the emergence of autonomous transport vehicles it becomes desirable to simulate and evaluate their behavior before they begin operating on the open road. In this work we study three simulator platforms for traffic and logistics simulation and evaluate them over eleven criteria and three scenarios. We find that none of the simulators is strictly better than any of the others, instead excelling in handling different classes of problems, such as simulation of goods transport or fuel consumption estimation.