Adaptive filters play an important role in the fields related to digital signal processing and communication, such as system identification, noise cancellation, channel equalization, and beamforming. In practical applications, the computational complexity of an adaptive filter is an important consideration. The Least Mean Square (LMS) algorithm is widely used because of its low computational complexity (O(N)) and simplicity in implementation. The least squares algorithms, such as Recursive Least Squares (RLS), Conjugate Gradient (CG), and Euclidean Direction Search (EDS), can converge faster and have lower steady-state mean square error (MSE) than LMS. However, their high computational complexity ($O(N^2)$) makes them unsuitable for many real-time applications. A well-known approach to controlling computational complexity is applying partial update (PU) method to adaptive filters. A partial update method can reduce the adaptive algorithm complexity by updating part of the weight vector instead of the entire vector or by updating part of the time. An analysis for different PU adaptive filter algorithms is necessary and meaningful. The deficient-length adaptive filter addresses a situation in system identification where the length of the estimated filter is shorter than the length of the actual unknown system. It is related to the partial update adaptive filter, but has different performance. It can be viewed as a PU adaptive filter, in that the deficient-length adaptive filter also updates part of the weight vector. However, it updates the same part of the weight vector for each iteration, while the partial update adaptive filter updates a different part of the weight vector for each iteration. In this work, basic PU methods are applied to the adaptive filter algorithms which have not been fully addressed in the literature, including CG, EDS, and Constant Modulus Algorithm (CMA) based algorithms. A new PU method, the selective-sequential method, is developed for LSCMA. Mathematical analysis is shown including convergence condition, steady-state performance, and tracking performance. Computer simulation with proper examples is also shown to further help study the performance. The performance is compared among different PU methods or among different adaptive filtering algorithms. Computational complexity is calculated for each PU method and each adaptive filter algorithm. The deficient-length RLS and EDS are also analyzed and compared to the performance of the PU adaptive filter. In this dissertation, basic partial-update methods are applied to adaptive filter algorithms including CMA1-2, NCMA, Least Squares CMA (LSCMA), EDS, and CG. A new PU method, the selective-sequential method, is developed for LSCMA. Mathematical derivation and performance analysis are provided including convergence condition, steady-state mean and mean-square performance for a time-invariant system. The steady-state mean and mean-square performance are also presented for a time-varying system. Computational complexity is calculated for each adaptive filter algorithm. Numerical examples are shown to compare the computational complexity of the PU adaptive filters with the full-update filters. Computer simulation examples, including system identification and channel equalization, are used to demonstrate the mathematical analysis and show the performance of PU adaptive filter algorithms. They also show the convergence performance of PU adaptive filters. The performance is compared between the original adaptive filter algorithms and different partial-update methods. The performance is also compared among similar PU least-squares adaptive filter algorithms, such as PU RLS, PU CG, and PU EDS. Deficient-length RLS and EDS are studied. The performance of the deficient-length filter is also compared with the partial update filter. In addition to the generic applications of system identification and channel equalization, two special applications of using partial update adaptive filters are also presented. One application is using PU adaptive filters to detect Global System for Mobile Communication (GSM) signals in a local GSM system using the Open Base Transceiver Station (OpenBTS) and Asterisk Private Branch Exchange (PBX). The other application is using PU adaptive filters to do image compression in a system combining hyperspectral image compression and classification. Overall, the PU adaptive filters can usually achieve comparable performance to the full-update filters while reducing the computational complexity significantly. The PU adaptive filters can achieve similar steady-state MSE to the full-update filters. Among different PU methods, the MMax method has a convergence rate very close to the full-update method. The sequential and stochastic methods converge slower than the MMax method. However, the MMax method does not always perform well with the LSCMA algorithm. The sequential LSCMA has the best performance among the PU LSCMA algorithms. The PU CMA may perform better than the full-update CMA in tracking a time-varying system. The MMax EDS can converge faster than the MMax RLS and CG. It can converge to the same steady-state MSE as the MMax RLS and CG, while having a lower computational complexity. The PU LMS and PU EDS can also perform a little better in a system combining hyperspectral image compression and classification. / Ph. D.

The capability of changing beliefs upon new information in a rational and efficient way is crucial for an intelligent agent. Belief change therefore is one of the central research fields in Artificial Intelligence (AI) for over two decades. In the AI literature, two different kinds of belief change operations have been intensively investigated: belief update, which deal with situations where the new information describes changes of the world; and belief revision, which assumes the world is static. As another important research area in AI, reasoning about actions mainly studies the problem of representing and reasoning about effects of actions. These two research fields are closely related and apply a common underlying principle, that is, an agent should change its beliefs (knowledge) as little as possible whenever an adjustment is necessary. This lays down the possibility of reusing the ideas and results of one field in the other, and vice verse. This thesis aims to develop a general framework and devise computational models that are applicable in reasoning about actions. Firstly, I shall propose a new framework for iterated belief revision by introducing a new postulate to the existing AGM/DP postulates, which provides general criteria for the design of iterated revision operators. Secondly, based on the new framework, a concrete iterated revision operator is devised. The semantic model of the operator gives nice intuitions and helps to show its satisfiability of desirable postulates. I also show that the computational model of the operator is almost optimal in time and space-complexity. In order to deal with the belief change problem in multi-agent systems, I introduce a concept of mutual belief revision which is concerned with information exchange among agents. A concrete mutual revision operator is devised by generalizing the iterated revision operator. Likewise, a semantic model is used to show the intuition and many nice properties of the mutual revision operator, and the complexity of its computational model is formally analyzed. Finally, I present a belief update operator, which takes into account two important problems of reasoning about action, i.e., disjunctive updates and domain constraints. Again, the updated operator is presented with both a semantic model and a computational model.

Die 'Mitteilungen des URZ' enthalten Informationen für die Nutzer des Universitätsrechenzentrums der TU Chemnitz und erscheinen vierteljährlich.

The capability of changing beliefs upon new information in a rational and efficient way is crucial for an intelligent agent. Belief change therefore is one of the central research fields in Artificial Intelligence (AI) for over two decades. In the AI literature, two different kinds of belief change operations have been intensively investigated: belief update, which deal with situations where the new information describes changes of the world; and belief revision, which assumes the world is static. As another important research area in AI, reasoning about actions mainly studies the problem of representing and reasoning about effects of actions. These two research fields are closely related and apply a common underlying principle, that is, an agent should change its beliefs (knowledge) as little as possible whenever an adjustment is necessary. This lays down the possibility of reusing the ideas and results of one field in the other, and vice verse. This thesis aims to develop a general framework and devise computational models that are applicable in reasoning about actions. Firstly, I shall propose a new framework for iterated belief revision by introducing a new postulate to the existing AGM/DP postulates, which provides general criteria for the design of iterated revision operators. Secondly, based on the new framework, a concrete iterated revision operator is devised. The semantic model of the operator gives nice intuitions and helps to show its satisfiability of desirable postulates. I also show that the computational model of the operator is almost optimal in time and space-complexity. In order to deal with the belief change problem in multi-agent systems, I introduce a concept of mutual belief revision which is concerned with information exchange among agents. A concrete mutual revision operator is devised by generalizing the iterated revision operator. Likewise, a semantic model is used to show the intuition and many nice properties of the mutual revision operator, and the complexity of its computational model is formally analyzed. Finally, I present a belief update operator, which takes into account two important problems of reasoning about action, i.e., disjunctive updates and domain constraints. Again, the updated operator is presented with both a semantic model and a computational model.

L'objectif de cette thèse consiste à présenter un nouvel algorithme pour la programmation non linéaire en nombres entiers, inspirée par la méthode Multiplicative Weights Update et qui compte sur une nouvelle classe de reformulations, appelées les reformulations ponctuelles.La programmation non linéaire en nombres entiers est un sujet très difficile et fascinant dans le domaine de l'optimisation mathématique à la fois d'un point de vue théorique et computationnel. Il est possible de formuler de nombreux problèmes dans ce schéma général et, habituellement, ils posent de réels défis en termes d'efficacité et de précision de la solution obtenue quant aux procédures de résolution.La thèse est divisée en trois parties principales : une introduction composée par le Chapitre 1, une définition théorique du nouvel algorithme dans le Chapitre 2 et l'application de cette nouvelle méthodologie à deux problèmes concrets d'optimisation, tels que la sélection optimale du portefeuille avec le critère moyenne-variance dans le Chapitre 3 et le problème du sac à dos non linéaire dans le Chapitre 4. Conclusions et questions ouvertes sont présentées dans le Chapitre 5. / This thesis presents a new algorithm for Mixed Integer NonLinear Programming, inspired by the Multiplicative Weights Update framework and relying on a new class of reformulations, called the pointwise reformulations.Mixed Integer NonLinear Programming is a hard and fascinating topic in Mathematical Optimization both from a theoretical and a computational viewpoint. Many real-word problems can be cast this general scheme and, usually, are quite challenging in terms of efficiency and solution accuracy with respect to the solving procedures.The thesis is divided in three main parts: a foreword consisting in Chapter 1, a theoretical foundation of the new algorithm in Chapter 2, and the application of this new methodology to two real-world optimization problems, namely the Mean-Variance Portfolio Selection in Chapter 3, and the Multiple NonLinear Separable Knapsack Problem in Chapter 4. Conclusions and open questions are drawn in Chapter 5.

This work provides overview of creating of a simple driver for the BIOS flash memory by accessing the physical computer memory. Although, the BIOS is one of a system's core components, there is no standardized update mechanism approach. Purpose of thesis is to create module driver by taking advantage of existing interface subsystem MTD, to suggest and implement driver for one specific device to Linux kernel operating system. Also explains technique allowing write access to registers of the flash memory with utilization of configuration file.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Utilization of ALS data for update of a road network Abstract My thesis concerned problematics of automatic detection of communication data from aerial laser scanning. Goal of this method is to identify area of roads - tarmacs as accurate as possible. On its basis are counted attributes of specific parts. In first part of the thesis are summarized known procedures, which are used to deal with the issue and experiences and evaluation of the output of theirs authors. In practical part of the thesis is described procedure methodology, which is based on findings from the literature review. Subsequently, input data and model areas are introduced. In the final parts are described results and compared with the results of authors, who used such evaluation in their work. Key words: airborne laser scanning, digital topographic database, road network, database update

Data warehousing is becoming an increasingly important technology for information integration and data analysis. Given the dynamic nature of modern distributed environments, both source data updates and schema changes are likely to occur autonomously and even concurrently in different data sources. Current approaches to maintain a data warehouse in such dynamic environments sequentially schedule maintenance processes to occur in isolation. Furthermore, each maintenance process is handling the maintenance of one single source update. This limits the performance of current data warehouse maintenance systems in a distributed environment where the maintenance of source updates endures the overhead of network delay as well as IO costs for each maintenance query. In this thesis work, we propose two different optimization strategies which can greatly improve data warehouse maintenance performance for a set of source updates in such dynamic environments. Both strategies are able to support source data updates and schema changes. The first strategy, the parallel data warehouse maintainer, schedules multiple maintenance processes concurrently. Based on the DWMS_Transaction model, we formalize the constraints that exist in maintaining data and schema changes concurrently and propose several parallel maintenance process schedulers. The second strategy, the batch data warehouse maintainer, groups multiple source updates and then maintains them within one maintenance process. We propose a technique for compacting the initial sequence of updates, and then for generating delta changes for each source. We also propose an algorithm to adapt/maintain the data warehouse extent using these delta changes. A further optimization of the algorithm also is applied using shared queries in the maintenance process. We have designed and implemented both optimization strategies and incorporated them into the existing DyDa/TxnWrap system. We have conducted extensive experiments on both the parallel as well as the batch processing of a set of source updates to study the performance achievable under various system settings. Our findings include that our parallel maintenance gains around 40 ~ 50% performance improvement compared to sequential processing in environments that use single-CPU machines and little network delay, i.e, without requiring any additional hardware resources. While for batch processing, an improvement of 400 ~ 500% improvement compared with sequential maintenance is achieved, however at the cost of less frequent refreshes of the data warehouse content.

<p>Many embedded systems are complex, and it is often required that the firmware in these systems are updatable by the end-user. For economical and confidentiality reasons, it is important that these systems only accept firmware approved by the firmware producer.</p><p>This thesis work focuses on creating a security enhanced firmware update procedure that is suitable for use in embedded systems. The common elements of embedded systems are described and various candidate algorithms are compared as candidates for firmware verification. Patents are used as a base for the proposal of a security enhanced update procedure. We also use attack trees to perform a threat analysis on an update procedure.</p><p>The results are a threat analysis of a home office router and the proposal of an update procedure. The update procedure will only accept approved firmware and prevents reversion to old, vulnerable, firmware versions. The firmware verification is performed using the hash function SHA-224 and the digital signature algorithm RSA with a key length of 2048. The selection of algorithms and key lengths mitigates the threat of brute-force and cryptanalysis attacks on the verification algorithms and is believed to be secure through 2030.</p>