Title: Detection of change in some special regression models Author: Bc. Petra Exnarová Department: Department of Probability and Mathematical Statistics Supervisor: Prof. RNDr. Marie Hušková, DrSc. Abstract: Presented thesis deals with testing of change in three special cases of change-point analysis. First of them is case of continuous change in linear regression (so-called broken-line model), the other two are related to change in parameters of discrete value distributions - simple case of Bernoulli distributed variables is studied first and then the approach is generalized for case of Multi- nomial distribution. Both situations of known and unknown change point are described for all three cases. Beside approximation by using limit theorems, the bootstrap method and permutation test are described for all studied cases as well. The comparison of critical values gained by different approaches for the particular tests and small power analysis is done using simulations. Keywords: change-point analysis, broken-line model, discrete distribution, boot- strap, permutation test 1

[pt] Este trabalho possui o intuito de desmistificar a dificuldade encontrada por professores e alunos no ensino e aprendizagem do tópico análise combinatória. A razão que motivou este trabalho foi o fato de que boa parte dos professores de matemática do ensino médio e últimas séries do ensino fundamental consideram a Análise Combinatória como algo complicado de ser ensinado; além da questão das dificuldades de entendimento por parte dos alunos que são induzidos à memorização de fórmulas e a aplicação das mesmas à resolução dos exercícios para compreenderem tal conteúdo. Inicialmente apresentaremos alguns conceitos que servirão como auxílio para que o professor possa trabalhar nas atividades propostas a serem desenvolvidas juntamente com os alunos. E ao longo do trabalho iremos falar de alguns tópicos abordados pela análise combinatória sem, inicialmente, mencionarmos fórmulas que servem apenas para serem memorizadas. O mais importante é fazer o aluno trabalhar um problema sugerido através do roteiro e dos conceitos que serão propostos e ao final de alguns exercícios, quando tal aluno tiver entendido tal conceito, ser anunciado a ele que acabou de aprender e entender o conceito em questão, ao invés de memorizar um determinado exercício ou outro, pois sabemos que desta forma, quando o aluno deparar-se com um novo problema, não será capaz de solucioná-lo. Dessa maneira, elaborou-se um roteiro na solução dos exercícios, ou seja, uma forma do professor trabalhar qualquer atividade proposta que envolva problemas de contagem em sala de aula. Enfim, buscou-se com esse trabalho, apresentar aos docentes, estratégias eficientes que podem ser utilizadas para o ensino de combinatória e ajudar os alunos a compreenderem melhor os problemas de contagem utilizando o raciocínio lógico e de contagem. / [en] This work has the intent to explain the difficulties found by teachers and student on teaching and learning combinatorics. The motivation of this work was the fact that most of the Mathematics Teachers of High School consider combinatorics as something complicated to be taught; contributing as well the fact that students are led to memorize the formulas and apply it on exercises so they can understand the subject. Initially we will show some concepts that will help the Teachers to work together with the students on the proposed activities. During the work, we will talk about Combinatorics topics without mentioning formulas that needs memorization only. The most important thing is to make the student work on a suggested problem following a guide and concepts shown and after finishing a few exercises, when the student will show the understanding of the concepts, the Teacher will tell him that he learned that concept, instead of memorizing a specific exercise. Because we know that not doing this, when this student faces a new problem, he will not be able to solve it. Thus it was elaborated a guide to solve exercises and that means a way that the Teacher can work with any proposed activity that has counting in it. Finally, it was sought with this work to show the scholars some efficient strategies that can be used on teaching Combinatorics and help the students to understand better the problems about counting, using logical reasoning and logical counting.

Balancing trade-offs between production cost and holding cost is critical for production and operations management. Utilization of an operating room affects production cost, which relates to makespan, and patient flowtime affects holding cost. There are trade-offs between two objectives, to minimize makespan and to minimize flowtime. However, most existing constructive heuristics focus only on single-objective optimization. In the current literature, NEH is the best constructive heuristic to minimize makespan, and LR heuristic is the best to minimize flowtime. In this thesis, we propose a current and future deviation (CFD) heuristic to balance trade-offs between makespan and flowtime minimizations. Based on 5400 randomly generated instances and 120 instances in Taillard’s benchmarks, our CFD heuristic outperforms NEH and LR heuristics on trade-off balancing, and achieves the most stable performances from the perspective of statistical process control.

A new approach to image-space hardware-based rendering of Constructive Solid Geometry (CSG) models is presented. The work is motivated by the evolving functionality and performance of computer graphics hardware. This work is also motivated by a specific industrial application --- interactive verification of five axis grinding machine tool programs. The goal is to minimise the amount of time required to render each frame in an animation or interactive application involving boolean combinations of three dimensional shapes. The Sequenced Convex Subtraction (SCS) algorithm utilises sequenced subtraction of convex objects for the purpose of interactive CSG rendering. Concave shapes must be decomposed into convex shapes for the purpose of rendering. The length of Permutation Embedding Sequences (PESs) used as subtraction sequences are shown to have a quadratic lower bound. In many situations shorter sequences can be used, in the best case linear. Approaches to s ubtraction sequence encoding are presented including the use of object-space overlap information. The implementation of the algorithm is experimentally shown to perform better on modern commodity graphics hardware than previously reported methods. This work also examines performance aspects of the SCS algorithm itself. Overall performance depends on hardware characteristics, the number and spatial arrangement of primitives, and the structure and boolean operators of the CSG tree.

Dans cette thèse, la Séparation Aveugle de Mélanges Convolutifs de Sources est étudiée. Pour la séparation des mélanges audio, nous avons développé des méthodes nouvelles pour les cas avec bruit et sans bruit dans l'environnement de propagation. La méthode sans bruit est basée sur la diagonalisation conjointe des matrices spectrales et exploite la non stationnarité des signaux. Nous avons proposé deux techniques différentes pour résoudre le problème de permutation. La deuxième méthode, où un bruit additif est présent, est basée sur le maximum de vraisemblance. La simulation des méthodes est réalisée sur des données réelles de salles acoustiques.

Cette thèse concerne les valeurs du caractère irréductible (renormalisé) comme fonction de la partition indexant la représentation (et non de la permutation sur laquelle on calcule le caractère). Avec une bonne renormalisation, les caractères s'écrivent comme des polynômes en fonction des coordonnées des diagrammes multirectangulaires d'une part et en fonction des cumulants libres d'autre part ( ce sont des observables du diagramme apparaissant naturellement dans des problèmes d'asymptotique). Nous avons donné des interprétations combinatoires des coefficients de ces différentes expressions. Celles-ci peuvent s'exprimer en termes de cartes, dont le genre est lié au comportement asymptotique du terme correspondant. Ce type d'expression permet d'une part de bien comprendre le comportement asymptotique : nous avons ainsi amélioré les bornes connues sur les caractères ainsi que le domaine de validité d'équivalents classique. D'autre part, la combinatoire apparaissant dans ces questions est riche et a pu être utilisée dans l'étude d'identité sur des fractions rationnelles

<p>The aim of source coding is to represent information as accurately as possible using as few bits as possible and in order to do so redundancy from the source needs to be removed. The aim of channel coding is in some sense the contrary, namely to introduce redundancy that can be exploited to protect the information when being transmitted over a nonideal channel. Combining these two techniques leads to the area of joint source–channel coding which in general makes it possible to achieve a better performance when designing a communication system than in the case when source and channel codes are designed separately. In this thesis two particular areas in joint source–channel coding are studied: multiple description coding (MDC) and soft decoding. Two new MDC schemes are proposed and investigated. The first is based on sorting a frame of samples and transmitting, as side-information/redundancy, an index that describes the resulting permutation. In case that some of the transmitted descriptors are lost during transmission this side information (if received) can be used to estimate the lost descriptors based on the received ones. The second scheme uses permutation codes to produce different descriptions of a block of source data. These descriptions can be used jointly to estimate the original source data. Finally, also the MDC method multiple description coding using pairwise correlating transforms as introduced by Wang et al is studied. A modification of the quantization in this method is proposed which yields a performance gain. A well known result in joint source–channel coding is that the performance of a communication system can be improved by using soft decoding of the channel output at the cost of a higher decoding complexity. An alternative to this is to quantize the soft information and store the pre-calculated soft decision values in a lookup table. In this thesis we propose new methods for quantizing soft channel information, to be used in conjunction with soft-decision source decoding. The issue on how to best construct finite-bandwidth representations of soft information is also studied.</p>

<p>The concept of Parallel Vector (scratch pad) Memories (PVM) was introduced as one solution for Parallel Computing in DSP, which can provides parallel memory addressing efficiently with minimum latency. The parallel programming more efficient by using the parallel addressing generator for parallel vector memory (PVM) proposed in this thesis. However, without hiding complexities by cache, the cost of programming is high. To minimize the programming cost, automatic parallel memory address generation is needed to hide the complexities of memory access.</p><p>This thesis investigates methods for implementing conflict-free vector addressing algorithms on a parallel hardware structure. In particular, match vector addressing requirements extracted from the behaviour model to a prepared parallel memory addressing template, in order to supply data in parallel from the main memory to the on-chip vector memory.</p><p>According to the template and usage of the main and on-chip parallel vector memory, models for data pre-allocation and permutation in scratch pad memories of ASIP can be decided and configured. By exposing the parallel memory access of source code, the memory access flow graph (MFG) will be generated. Then MFG will be used combined with hardware information to match templates in the template library. When it is matched with one template, suited permutation equation will be gained, and the permutation table that include target addresses for data pre-allocation and permutation is created. Thus it is possible to automatically generate memory address for parallel memory accesses.</p><p>A tool for achieving the goal mentioned above is created, Permutator, which is implemented in C++ combined with XML. Memory access coding template is selected, as a result that permutation formulas are specified. And then PVM address table could be generated to make the data pre-allocation, so that efficient parallel memory access is possible.</p><p>The result shows that the memory access complexities is hiden by using Permutator, so that the programming cost is reduced.It works well in the context that each algorithm with its related hardware information is corresponding to a template case, so that extra memory cost is eliminated.</p>

Dans ce mémoire, nous nous intéressons à l'étude et la résolution de problèmes d'ordonnancement de type flowshop de permutation, en présence de contraintes d'écarts temporels (ou time lags), définies entre les couples d'opérations consécutives au sein des travaux. De telles contraintes généralisent les contraintes de précédence classiques et peuvent modéliser de nombreuses situations réelles. De nouveaux résultats de complexité sont démontrés et viennent compléter des résultats classiques tirés de la littérature. Nous présentons aussi un état de l'art assez détaillé sur les travaux concernant les problèmes d'ordonnancement avec time lags, qui met en évidence le manque d'attention reçu par ces problèmes. Nous développons ensuite un schéma générique de résolution exacte reposant sur une Procédure par Séparation et Evaluation et nous l'utilisons pour résoudre plusieurs problèmes de flowshop de permutation en présence de time lags. L'efficacité de cette approche de résolution est évaluée grâce à des séries d'expériences numériques. Enfin, des extensions permettant de prendre en compte des contraintes supplémentaires sont proposées.

This thesis presents several statistical analysis on a cooperative project with Dr. Pallas and Yuting Mao from Biology Department of Georgia State University. This research concludes the impact of cauterize size of animals’ midbrain on auditory and visual response in brains. Besides some already commonly used statistical analysis method, such as MANOVA and Frequency Test, a unique combination of Permutation Test, Kolmogorov-Smirnov Test and Wilcoxon Rank Sum Test is applied to our non-parametric data. Some simulation results show the Permutation Test we used has very good powers, and fits the need for this study. The result confirms part of the Biology Department’s hypothesis statistically and enhances more complete understanding of the experiments and the potential impact of helping patients with Acquired Brain Injury.