In our bachelor thesis, we described an implicit data structure that, given a way to maintain an implicit representation of polylogarithmic buckets, could implement all the dynamic ordered dictionary operations in logarithmic time. We now fulfill our obligation and provide a corresponding construction of implicit buckets. 1

Dans cette Thèse, nous avons introduit plusieurs procédures pour résoudre le problème d’ordonnancement du projet multi-compétences (MSPSP). L’objectif est de trouver un ordonnancement qui minimise le temps de terminaison (makespan) d’un projet, composé d’un ensemble d’activités. Les relations de précédences et les contraintes de ressource seront considérées. Dans ce problème, les ressources sont des membres du personnel qui maîtrisent plusieurs compétences. Ainsi, un certain nombre de travailleurs doit être affecté pour utiliser chaque compétence requise par une activité. Par ailleurs, nous accorderons une importance particulière aux méthodes exactes pour résoudre le MSPSP, puisqu’il y a encore un certain nombre d’instances pour lesquelles l’optimalité doit encore être prouvée. Néanmoins,pour traiter des instances plus importantes, nous implémentons une approche heuristique. / In this Phd Thesis we introduce several procedures to solve the Multi-Skill Project Scheduling Problem (MSPSP). The aim is to find a schedule that minimizes the completion time (makespan) of a project, composed of a set of activities. Precedence relations and resource constraints are considered. In this problem, resources are staff members that master several skills. Thus, a given number of workers must be assigned to perform each skill required by an activity. Furthermore, we give a particula rimportance to exact methods for solving the Multi-Skill Project Scheduling Problem (MSPSP), since there are still several instances for which optimality is still to be proven. Nevertheless, with the purpose of solving big sized instances we also developed and implemented a heuristic approach.

NP search problems and reductions among them Renáta Ševčíková In the thesis we study the class of Total NP search problems. More attention is devoted to study the subclasses of Total NP search problems and reductions among them. We combine some known methods: the search trees and their relation to re- ductions, the Nullstellensatz refutation and the degree lower bound based on design to show that two classes of relativized NP search problems based on Mod-p counting principle and Mod-q counting principle, where p and q are different primes, are not reducible to each other. This thesis is finished by a new separation result for p = 2 and q = 3.

Estimativa e simulação baseados na estatística de dois pontos têm sido usadas desde a década de 1960 na análise geoestatístico. Esses métodos dependem do modelo de correlação espacial derivado da bem conhecida função semivariograma. Entretanto, a função semivariograma não pode descrever a heterogeneidade geológica encontrada em depósitos minerais e reservatórios de petróleo. Assim, ao invés de usar a estatística de dois pontos, a geoestatística multi-pontos, baseada em distribuições de probabilidade de múltiplo pontos, tem sido considerada uma alternativa confiável para descrição da heterogeneidade geológica. Nessa tese, o algoritmo multi-ponto é revisado e uma nova solução é proposta. Essa solução é muito melhor que a original, pois evita usar as probabilidades marginais quando um evento que nunca ocorre é encontrado no template. Além disso, para cada realização a zona de incerteza é ressaltada. Uma base de dados sintética foi gerada e usada como imagem de treinamento. A partir dessa base de dados completa, uma amostra com 25 pontos foi extraída. Os resultados mostram que a aproximação proposta proporciona realizações mais confiáveis com zonas de incerteza menores. / Estimation and simulation based on two-point statistics have been used since 1960\'s in geostatistical analysis. These methods depend on the spatial correlation model derived from the well known semivariogram function. However, the semivariogram function cannot describe the geological heterogeneity found in mineral deposits and oil reservoirs. Thus, instead of using two-point statistics, multiple-point geostatistics based on probability distributions of multiple-points has been considered as a reliable alternative for describing the geological heterogeneity. In this thesis, the multiple-point algorithm is revisited and a new solution is proposed. This solution is much better than the former one because it avoids using marginal probabilities when a never occurring event is found in a template. Moreover, for each realization the uncertainty zone is highlighted. A synthetic data base was generated and used as training image. From this exhaustive data set, a sample with 25 points was drawn. Results show that the proposed approach provides more reliable realizations with smaller uncertainty zones.

Estimativa e simulação baseados na estatística de dois pontos têm sido usadas desde a década de 1960 na análise geoestatístico. Esses métodos dependem do modelo de correlação espacial derivado da bem conhecida função semivariograma. Entretanto, a função semivariograma não pode descrever a heterogeneidade geológica encontrada em depósitos minerais e reservatórios de petróleo. Assim, ao invés de usar a estatística de dois pontos, a geoestatística multi-pontos, baseada em distribuições de probabilidade de múltiplo pontos, tem sido considerada uma alternativa confiável para descrição da heterogeneidade geológica. Nessa tese, o algoritmo multi-ponto é revisado e uma nova solução é proposta. Essa solução é muito melhor que a original, pois evita usar as probabilidades marginais quando um evento que nunca ocorre é encontrado no template. Além disso, para cada realização a zona de incerteza é ressaltada. Uma base de dados sintética foi gerada e usada como imagem de treinamento. A partir dessa base de dados completa, uma amostra com 25 pontos foi extraída. Os resultados mostram que a aproximação proposta proporciona realizações mais confiáveis com zonas de incerteza menores. / Estimation and simulation based on two-point statistics have been used since 1960\'s in geostatistical analysis. These methods depend on the spatial correlation model derived from the well known semivariogram function. However, the semivariogram function cannot describe the geological heterogeneity found in mineral deposits and oil reservoirs. Thus, instead of using two-point statistics, multiple-point geostatistics based on probability distributions of multiple-points has been considered as a reliable alternative for describing the geological heterogeneity. In this thesis, the multiple-point algorithm is revisited and a new solution is proposed. This solution is much better than the former one because it avoids using marginal probabilities when a never occurring event is found in a template. Moreover, for each realization the uncertainty zone is highlighted. A synthetic data base was generated and used as training image. From this exhaustive data set, a sample with 25 points was drawn. Results show that the proposed approach provides more reliable realizations with smaller uncertainty zones.

The main objective of this work is to design and implement an application that can be used as an aid for the education of programming essentials. Particularly, the attention focuses on the domain of dynamic data structures. The target application will be implemented with the use of web technologies so that it can be run in an ordinary WWW browser. First of all, a brief introduction recapitulates the data structures to be covered. Then the work summarizes the usable technologies available within the web browsers with the focus on the particular technology (which is DHTML) that will become the target platform. The most significant part of this work then discusses the design of the final application. This rather theoretical part is then followed by the description of the practical implementation. A short user manual is also included.

This work is intended on identification with basic problems from the graphs theory area. There are the basic conceptions as well more complicated problems described. The one part of this work is specialized in working of individual types of graphs. It starts with single linked list through double linked list after as much as trees which represented the simplest graphs textures. The other part of this work devotes to the whole graph and describes more complicated problems and their resolution from the theory graphs area. Among these problems belongs to searching in graphs help by Depth First Search and Breadth First Search methods. Then searching the shortest way help by the specific algorithms as are: Dijkstra´s algorithm, Floyd-Warshall´s algorithm and Bellman-Ford´s algorithm. The last part is devoted to problems with searching minimal frames of graphs with usage Kruskal´s algorithm, Jarnik´s algorithm and Boruvka´s algorithm methods.