Studentarbeten // Student Theses
Använd denna länk för att länka till samlingen:
Browse
Browsar Studentarbeten // Student Theses efter Program "Computer science – algorithms, languages and logic (MPALG), MSc"
Visar 1 - 20 av 325
Sökresultat per sida
Sortera efter
- 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.
- Post3D object detection for autonomous driving using deep learning(2019) Berg Marklund, Olof; Hulthén, Oskar; Chalmers tekniska högskola / Institutionen för elektroteknik; Granström, Karl
- PostA column generation approach to the flexible job-shop problem with ordering requirements on operations(2018) Jonsson, Niclas; Chalmers tekniska högskola / Institutionen för matematiska vetenskaper; Chalmers University of Technology / Department of Mathematical Sciences
- 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 Compiler from CakeML to JavaScript(2018) Nyberg, Oskar; 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 new compiler from CakeML to JavaScript with support for almost the entire CakeML language. In addition to the new compiler, a JavaScript syntax formalization has been defined together with formal semantics for a subset of JavaScript. The semantics include coverage for language features introduced as part of the ECMAScript 2015 standard. The new compiler, syntax formalization and semantics are implemented in the HOL4 theorem prover to allow for future verification of the new compiler. The new compiler enables CakeML programs to be run in web browsers on both desktop computers and smart phones and other contexts previously not available to CakeML.
- 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 Decentralized Application for Verifying a Matching Algorithm - Programming and Testing a Smart Contract on the Ethereum Blockchain(2018) Fritz, Linnea; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)This thesis uses blockchain technology to construct a decentralized application (often called a ‘Ðapp’) for the sake of verifying results of a matching algorithm used on data in the automotive industry. Its main intent is to explore whether the framework Ethereum can be utilized to aid in ensuring the correctness of client responses to a query sent by a peer in the network. The application was programmed in Solidity and JavaScript, and run on a local test network consisting of five clients. Testing the finished application showed that the throughput of data was slow, approximately 35 bytes/s, and that taking over the network to send corrupted information was relatively simple. These findings, along with a general study of the areas where blockchain technology is most advantageous, led to the conclusion that though it has potential as a constituent in the car industry, it is not suitable for verification of matchings at the time of writing.
- PostA deep learning based tracking framework for passenger monitoring(2018) Granqvist, Filip; Holmberg, Oskar; Chalmers tekniska högskola / Institutionen för elektroteknik; Chalmers University of Technology / Department of Electrical Engineering
- 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 [11], 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 machine learning algorithm to detect fog from space(2024) Svensson, Kevin; Johansson, Nils; Chalmers tekniska högskola / Institutionen för rymd-, geo- och miljövetenskap; Chalmers University of Technology / Department of Space, Earth and Environment; Eriksson, Patrick; Ceccobello, ChiaraFog detection is important for traffic safety. Detecting fog using machine learning on satellite data has been researched before, but not on a global scale using syn thetic data. The aim of the thesis is to use a synthetic dataset of simulated MODIS satellite data to determine the viability of machine learning algorithms for detecting fog in satellite images. The synthetic dataset we use is simulated using a fast ra diative transfer model called RTTOV by inputting various atmospheric information for different conditions. The dataset is tabular and no spatial or temporal relation ship exists between the data points meaning each pixel is treated independently. We use the synthetic data to train and evaluate numerous machine learning models including various implementations of XGBoost and feed forward deep neural net works. We also apply a model trained on synthetic data to a real MODIS image. We demonstrate that classification models can achieve good recall values on synthetic data when oversampling fog in the training data, the best being 0.87 recall with a deep neural network. However, we find that this comes at the cost of a large amount of false positives evident by the low precision value of 0.27. It is concluded that no model performed satisfactory results for replacing existing methods of fog detection. We identify the acquisition of supplemental labeled real satellite images as a possi bility for future improvement, allowing for spatial analysis which is impossible with the independent pixels of the synthetic dataset alone. However, this is a non-trivial task due to the challenges in obtaining and labeling a sufficiently large and diverse dataset of real satellite images.
- 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 multimodal deep learning approach for real-time fire detection in aerial imagery(2019) Posch, Daniel; Rask, Jesper; Chalmers tekniska högskola / Institutionen för elektroteknik; Chalmers University of Technology / Department of Electrical Engineering
- 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 natural language processing approach for identifying driving styles in curves(2016) McNabb, Eric; Kalander, Marcus; Chalmers tekniska högskola / Institutionen för tillämpad mekanik; Chalmers University of Technology / Department of Applied MechanicsA machine able to autonomously recognise driving styles has numerous applications, of which the most straightforward is to recognise risky behaviour. Such knowledge can be used to teach new drivers with the goal of reducing accidents in the future and increasing traffic safety for all road users. Furthermore, insurance companies can incentivise safe driving with lower premiums, which in turn can motivate a more careful driving style. Another application is within the field of autonomous vehicles where learning about driving styles is imperative for autonomous vehicles to be able to interact with other drivers in traffic. The first step towards identifying different driving styles is being able to recognise and distinguish between them. The aim of this thesis is to identify the indicators of aggressive driving in curves from a large amount of naturalistic driving data. The first step was finding curve sections to analyse within trips and the second step was reducing the data to become more manageable. Symbolic representations were used for the second preprocessing step, which in turn allowed the use of Natural Language Processing techniques for the analysis. We categorise drivers into different groups depending on their perceived tendency towards aggressive driving styles. This categorisation is used to compare the drivers and their driving style with each other. The tendencies used were Speeding, Braking, Jerky curve handling and Rough curve handling. Some general trends among the analysed drivers are also identified. It is possible to reuse the categorisation to include more drivers in the future or to use what we have learned about the features and drivers for further research.
- 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.