As conexões entre as células de um autômato celular tradicional são realizadas conforme um reticulado. Esse padrão de conexão faz com que o comprimento médio do menor caminho entre as células seja grande, exigindo que o autômato celular efetue várias evoluções para que o comportamento dinâmico de uma regra alcance todo o reticulado. O presente trabalho propõe a modificação na estrutura de conexão dos autômatos celulares empregando conceitos de redes complexas. É apresentado um processo de construção capaz de produzir redes que evoluem tanto para frente quanto para trás. O processo de construção de redes emprega uma variante de grafos dirigidos rotulados, permitindo que as redes geradas evoluam a partir do mesmo conjunto de regras utilizado pelo autômato celular tradicional. Experimentos empregando o cálculo de entropia, além de testes sobre aleatoriedade, foram realizados com o objetivo de investigar o comportamento dinâmico obtido por quatro redes distintas, geradas a partir do processo de construção de redes aqui proposto. Os experimentos indicam que, dependendo da estrutura de conexão, é possível reduzir de forma significativa a quantidade de evoluções necessárias para que uma perturbação inicial se propague por todas as células do reticulado. Uma aplicação direta dos resultados encontrados nesse trabalho consiste na elaboração de métodos criptográficos significativamente mais rápidos do que aqueles que empregam os autômatos celulares tradicionais.

VIANA, Luiz Alberto do Carmo. Árvore geradora com dependências mínima. 2016. 69 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2016. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-09-09T12:32:49Z No. of bitstreams: 1 2016_dis_lacviana.pdf: 590271 bytes, checksum: 9bf849e4e918431886cbd4c9beca22b3 (MD5) / Approved for entry into archive by Jairo Viana (jairo@ufc.br) on 2016-09-27T17:45:27Z (GMT) No. of bitstreams: 1 2016_dis_lacviana.pdf: 590271 bytes, checksum: 9bf849e4e918431886cbd4c9beca22b3 (MD5) / Made available in DSpace on 2016-09-27T17:45:27Z (GMT). No. of bitstreams: 1 2016_dis_lacviana.pdf: 590271 bytes, checksum: 9bf849e4e918431886cbd4c9beca22b3 (MD5) Previous issue date: 2016 / We introduce the Dependency Constrained Minimum Spanning Tree Problem, DCMST(G,D,w), defined over a graph G(V,E) and a digraph D(E,A), whose vertices are the edges of G and whose arcs describe dependency relations between these edges. Such problem consists of finding, among the spanning trees of G(V,E) satisfying the dependency constraints imposed by D(E,A), that one whose cost is minimum, according to a edgeweight function w. The dependency constraints impose that an edge e of G can be part of a solution either if it is a source in D or if some other edge e′, such that the arc (e′, e) is in D, is part of it as well. We prove that deciding whether there is a feasible solution to DCMST(G,D,w) is an NP-complete problem, even if G is a chordal cactus and D is a union of arborescences of height at most 2. NP-completeness also applies if G is bipartite, the dependency constraints occur only between adjacent edges of G and their related arcs describe arborescences whose height is at most 2. The same results are obtained for the problem variants which demand that, instead of “some”, “exactly one”or “all”dependencies be part of a solution. To solve the problem, we introduce some integer programming formulations and some valid inequalities. We propose a strategy to reduce the problem dimension by excluding some edges of G according to the structure of D. We evaluate the introduced models and algorithms using randomly generated instances. Computational results are reported. / Introduzimos o problema de Árvore Geradora com Dependências Mínima, AGDM(G,D,w), definido sobre um grafo G(V,E) e um digrafo D(E,A), cujos vértices são as arestas de G e cujos arcos definem dependências entre tais arestas. O problema consiste em encontrar, dentre as árvores geradoras do grafo G(V,E) que satisfaçam as restrições de dependência impostas pelo digrafo de entrada D(E,A), uma que tenha custo mínimo, segundo a ponderação w das arestas de G. As restrições de dependência exigem que uma aresta e de G só pode fazer parte de uma solução se for uma fonte em D ou se fizer parte da solução alguma outra aresta é tal que o arco (e′, e) esteja em D. Provamos que decidir se há solução viável para AGDM(G,D,w) é um problema NP-completo, mesmo quando G é um cacto cordal e D é a união de arborescências de altura no máximo 2. Sua NP-completude também é mostrada ainda que G seja bipartido, as restrições de dependência ocorram apenas entre arestas adjacentes de G e formem arborescências de altura no máximo 2. Resultados idênticos são obtidos para as variantes do problema onde, nas restrições de dependência, substitui-se o requisito “alguma” por “exatamente uma” ou “toda”. Para resolver o problema, apresentamos algumas formulações de programação inteira e desigualdades válidas. Propomos uma estratégia para reduzir a dimensão do problema, excluindo arestas de G com base na estrutura de D. Avaliamos os modelos e algoritmos propostos usando instâncias geradas aleatoriamente. Resultados computacionais são reportados.

ARAÚJO, Júlio César Silva. Coloração e convexidade em grafos. 2012. 207 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2012. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-09-09T13:56:50Z No. of bitstreams: 1 2012_tese_jcsaraujo.pdf: 2148108 bytes, checksum: 966c00be231160cb1e161402770627d6 (MD5) / Approved for entry into archive by Jairo Viana (jairo@ufc.br) on 2016-09-27T23:24:47Z (GMT) No. of bitstreams: 1 2012_tese_jcsaraujo.pdf: 2148108 bytes, checksum: 966c00be231160cb1e161402770627d6 (MD5) / Made available in DSpace on 2016-09-27T23:24:47Z (GMT). No. of bitstreams: 1 2012_tese_jcsaraujo.pdf: 2148108 bytes, checksum: 966c00be231160cb1e161402770627d6 (MD5) Previous issue date: 2012 / In this thesis, we study several problems of Graph Theory concerning Graph Coloring and Graph Convexity. Most of the results contained here are related to the computational complexity of these problems for particular graph classes. In the first and main part of this thesis, we deal with Graph Coloring which is one of the most studied areas of Graph Theory. We first consider three graph coloring problems called Greedy Coloring, Weighted Coloring and Weighted Improper Coloring. Then, we deal with a decision problem, called Good Edge-Labeling, whose de finition was motivated by the Wavelength Assignment problem in optical networks. The second part of this thesis is devoted to a graph optimization parameter called (geodetic) hull number. The de finition of this parameter is motivated by an extension to graphs of the notions of convex sets and convex hulls in the Euclidean space. Finally, we present in the appendix other works developed during this thesis, one about Eulerian and Hamiltonian directed hypergraphs and the other concerning distributed storage systems. / Nesta tese, estudamos vários problemas de teoria dos grafos relativos à coloração e convexidade em grafos. A maioria dos resultados contidos aqui são ligados à complexidade computacional destes problemas para classes de grafos particulares. Na primeira, e principal, parte desta tese, discutimos coloração de grafos que é uma das áreas mais importantes de teoria dos grafos. Primeiro, consideramos três problemas de coloração chamados coloração gulosa, coloração ponderada e coloração ponderada imprópria. Em seguida, discutimos um problema de decisão, chamado boa rotulagem de arestas, cuja de finição foi motivada pelo problema de atribuição de frequências em redes óticas. A segunda parte desta tese é dedicada a um parâmetro de otimização em grafos chamado de número de fecho (geodético). A de finição deste parâmetro é motivada pela extensão das noções de conjuntos e fecho convexos no espaço Euclidiano. Por m, apresentamos em anexo outros trabalhos desenvolvidos durante esta tese, um em hipergrafos dirigidos Eulerianos e Hamiltonianos e outro sobre sistemas de armazenamento distribuído.

FIGUEIREDO, Tatiane Fernandes. Problema de Formação de Equipes Sociotécnicas: Complexidade, Formulações Matemáticas e Resultados Computacionais. 2016. 86 f. Dissertação (mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2016. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-03-22T19:14:08Z No. of bitstreams: 1 2016_dis_tffigueiredo.pdf: 1148121 bytes, checksum: a25818a809d3426e9eb1ee56535c6361 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-04-25T12:32:53Z (GMT) No. of bitstreams: 1 2016_dis_tffigueiredo.pdf: 1148121 bytes, checksum: a25818a809d3426e9eb1ee56535c6361 (MD5) / Made available in DSpace on 2016-04-25T12:32:53Z (GMT). No. of bitstreams: 1 2016_dis_tffigueiredo.pdf: 1148121 bytes, checksum: a25818a809d3426e9eb1ee56535c6361 (MD5) Previous issue date: 2016 / Using concepts of the socio-technical systems theory, this dissertation defines mathematically the problems of cooperative teams formation considering social and technical constraints separately, and then presents their computational complexity. Mainly, it is defined and studied the central problem in this work, which jointly considers social and technical requirements for creating teams of cooperative work, to be called FEST (Socio-Technical Teams Formation Problem). Two mathematical formulations and a meta-heuristic are proposed for FEST. One formulation uses a cubic number of variables and constraints, whereas the second one has a quadratic number of variables but an exponential number of constraints. The proposed heuristic is based on the Non-monotonic Simulated Annealing meta-heuristic with local search using swap-like operators. The correctness of both formulations is proved. A polynomial algorithm to separate the constraints of the second formulation is presented. It is proved that the two formulations provide the same linear programming bound, and valid inequalities to strengthen it are proposed. For the compact formulation, some classes of valid inequalities are shown to be facet-inducing under suitable hypotheses. Finally, it is statistically analyzed the performance of the presented formulations and meta-heuristic. Real and random generated instances are used in the computational experiments. / Utilizando conceitos da Teoria dos Sistemas Sociotécnicos, este trabalho define matematicamente os problemas de formação de equipes cooperativas considerando separadamente restrições sociais e técnicas e apresenta a complexidade computacional dos mesmos. Sobretudo, é definido e estudado o problema central deste trabalho, que considera conjuntamente requisitos sociais e técnicos para criação de equipes de trabalho cooperativo, denominado FEST (Problema de Formação de Equipes Sociotécnicas). Duas formulações matemáticas e uma meta-heurística para o FEST são propostas. Uma formulação utiliza um número cúbico de variáveis e restrições, enquanto a segunda formulação possui um número quadrático de variáveis, mas um número exponencial de restrições. A meta-heurística proposta é baseada no Simulated Annealing Não-Monotônico com busca local que usa operadores tipo swap. A corretude de ambas as formulações é provada. Um algoritmo polinomial para separar as restrições da segunda formulação é apresentado. Mostra-se que as duas formulações fornecem o mesmo limite de programação linear, e desigualdades válidas para fortalecê-lo são propostas. Para a formulação compacta, algumas classes de desigualdades válidas são demonstradas indutoras de facetas sob hipóteses apropriadas. Por fim, foi analisado estatisticamente o desempenho das formulações e da meta-heurística apresentadas. Instâncias reais e geradas aleatoriamente são usadas nos experimentos computacionais.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2010. / Submitted by Luiza Moreira Camargo (luizaamc@gmail.com) on 2011-06-20T17:36:29Z No. of bitstreams: 1 2010_FelipePontesGuimarães.pdf: 3025286 bytes, checksum: 90ebea4efc3733e40b3ce19f7925beda (MD5) / Approved for entry into archive by Guilherme Lourenço Machado(gui.admin@gmail.com) on 2011-06-21T13:43:47Z (GMT) No. of bitstreams: 1 2010_FelipePontesGuimarães.pdf: 3025286 bytes, checksum: 90ebea4efc3733e40b3ce19f7925beda (MD5) / Made available in DSpace on 2011-06-21T13:43:47Z (GMT). No. of bitstreams: 1 2010_FelipePontesGuimarães.pdf: 3025286 bytes, checksum: 90ebea4efc3733e40b3ce19f7925beda (MD5) / A computação em Grid proporciona a seus usuários o compartilhamento de recursos autônomos e heterogêneos para solucionar problemas computacionais de grande complexidade. Em um Grid, os recursos possuem autonomia, logo podem entrar e sair do mesmo conforme suas necessidades. A computação em Grid é frequentemente usada para executar worflows científicos, que são uma rede de passos necessários à análise de grande volume de dados. Geralmente, a execução de workflows científicos é demorada, podendo levar vários minutos, várias horas ou mesmo dias. Ao se associar essas duas características - um ambiente dinâmico e workflows de longa duração - surge um problema: não há como se impedir que os recursos saiam do Grid durante a execução de tarefas de um workflow, causando assim um erro na execução. Não se pode, no entanto, permitir que tais erros inviabilizem a execução do workflow. Para contornar esse problema existem técnicas de tolerância a falhas, que procuram garantir que, mesmo em face de falhas na execução de algumas tarefas, o workflow como um todo será executado corretamente. Vários trabalhos lidam com técnicas de tolerância a falhas para workflows em Grid e várias técnicas diferentes já existem. No entanto, nenhuma das abordagens estudadas considera, em conjunto, as preferências do usuário e a situação atual do Grid. A presente dissertação de mestrado propõe e avalia um framework de execução adaptativa tolerante a falhas que permite ao usuário definir as regras pelas quais a seleção das técnicas de tolerância a falhas será realizada em tempo de execução e também permite a adição de novas técnicas de tolerância a falhas. Os resultados experimentais obtidos em um Grid com 5 máquinas mostram que o framework proposto de fato permite a definição de regras pelo usuário e a inclusão de novas técnicas de tolerância a falhas. Além disso, a sobrecarga no tempo de execução dos workflows foi baixo: cerca de 2%, na plataforma avaliada. ___________________________________________________________________________________ ABSTRACT / Grid computing allows its users to share autonomous and heterogeneous resources to solve highly complex computational problems. It creates an extremely dynamic environment, in which the resources may enter or leave at any given moment according to their needs. One of the major uses of Grid computing is the execution of scientific workflows, a set of necessary steps for analyzing great amounts of data. The execution time of these workflows may vary from several minutes to days. Once we combine these two characteristics - a dynamic environment and long execution times - a problem arises, since there is no mechanism to prevent resources from leaving the Grid during the execution of a task belonging to a workflow, thus introducing an error in the execution. However, the ocurrence of these errors must not make unfeasible the workflow execution. To deal with this issue fault tolerance techniques have been proposed. They allow for correct workflow execution even when facing errors during a number of faults in intermediary tasks. Many published papers deal with fault tolerance techniques for workflow execution in the Grid, but none of the studied approaches consider both the user preferences and the current status of the Grid. The current Master's Thesis proposes and evaluates a framework that provides adaptive fault tolerant execution for workflows in Grids allowing the user to define the rules by which the fault tolerance techniques will be chosen at runtime. Moreover, it allows the addition of new fault tolerance techniques. The experimental results obtained from a 5-machine Grid show that the framework is able to allow the user to set the rules and add new fault tolerance techniques at the cost of a very low overhead in the execution time: around 2% in the evalution platform.

MinistÃre de l'Enseignement SupÃrieur et de la Recherche / Nesta tese, estudamos vÃrios problemas de teoria dos grafos relativos à coloraÃÃo e convexidade em grafos. A maioria dos resultados contidos aqui sÃo ligados à complexidade computacional destes problemas para classes de grafos particulares. Na primeira, e principal, parte desta tese, discutimos coloraÃÃo de grafos que à uma das Ãreas mais importantes de teoria dos grafos. Primeiro, consideramos trÃs problemas de coloraÃÃo chamados coloraÃÃo gulosa, coloraÃÃo ponderada e coloraÃÃo ponderada imprÃpria. Em seguida, discutimos um problema de decisÃo, chamado boa rotulagem de arestas, cuja definiÃÃo foi motivada pelo problema de atribuiÃÃo de frequÃncias em redes Ãticas. A segunda parte desta tese à dedicada a um parÃmetro de otimizaÃÃo em grafos chamado de nÃmero de fecho (geodÃtico). A definiÃÃo deste parÃmetro à motivada pela extensÃo das noÃÃes de conjuntos e fecho convexos no espaÃo Euclidiano. Por m, apresentamos em anexo outros trabalhos desenvolvidos durante esta tese, um em hipergrafos dirigidos Eulerianos e Hamiltonianos e outro sobre sistemas de armazenamento distribuÃdo. / In this thesis, we study several problems of Graph Theory concerning Graph Coloring and Graph Convexity. Most of the results contained here are related to the computational complexity of these problems for particular graph classes. In the first and main part of this thesis, we deal with Graph Coloring which is one of the most studied areas of Graph Theory. We first consider three graph coloring problems called Greedy Coloring, Weighted Coloring and Weighted Improper Coloring. Then, we deal with a decision problem, called Good Edge-Labeling, whose definition was motivated by the Wavelength Assignment problem in optical networks. The second part of this thesis is devoted to a graph optimization parameter called (geodetic) hull number. The definition of this parameter is motivated by an extension to graphs of the notions of convex sets and convex hulls in the Euclidean space. Finally, we present in the appendix other works developed during this thesis, one about Eulerian and Hamiltonian directed hypergraphs and the other concerning distributed storage systems.

Submitted by Isaac Francisco de Souza Dias (isaac.souzadias@ufpe.br) on 2015-10-20T18:25:48Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) tese bruno oliveira digital.pdf: 7541467 bytes, checksum: 33036bbf6267da571ee033123d8aa37a (MD5) / Made available in DSpace on 2015-10-20T18:25:48Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) tese bruno oliveira digital.pdf: 7541467 bytes, checksum: 33036bbf6267da571ee033123d8aa37a (MD5) Previous issue date: 2015-02-27 / CNPq / A presente tese trabalha a hipótese de que a Engenharia Reversa pode suprir a carência de ferramenta que ajude os designers a especificar os games - principalmente as variáveis que formam a mecânica de jogo. A pesquisa entende e considera jogos digitais um produto industrial e, quando abstraído em alto nível, segue os mesmos passos de projeto de outros produtos do design. Tendo isso em conta, a pesquisa desenvolvida usa como base o método Design Thinking Canvas (DTC) desenvolvido no GRDLab da UFPE como alicerce para trabalhar a hipótese. Constata-se que há uma carência de ferramentas que suportem a especificação dos jogos. A pesquisa propõe o uso da Engenharia Reversa através de um modelo de uso proposto, como meio de solucionar essa carência. Em seguida o modelo proposto é colocado em uso em um experimento empírico com duas avaliações: uma pelos alunos do curso de design que utilizaram o modelo - avaliando a utilidade do modelo; e, na segunda, professores e profissionais da área de games avaliam o impacto do uso do modelo na especificação das variáveis nos trabalhos dos alunos. Em ambas, os resultados demonstram um impacto positivo no uso da ferramenta, indicando que o uso da ER no processo de game design contribui para a melhoria qualitativa das especificações dos jogos.

Orientadores : Marconi Kolm Madrid, Alvaro Geraldo Badan Palhares / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-28T21:26:01Z (GMT). No. of bitstreams: 1 Nogueira_ReinaldoGoncalves_D.pdf: 31517235 bytes, checksum: 525880e222b125f146a7cf29f52162f1 (MD5) Previous issue date: 2001 / Doutorado

Orientador: Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T06:09:05Z (GMT). No. of bitstreams: 1 Grilo_AlexBredariol_M.pdf: 1279418 bytes, checksum: 80f0b105ffcfb57f6e43c530b32cb7a9 (MD5) Previous issue date: 2014 / Resumo: A Computação Quântica é um tópico relativamente recente e pouco conhecido, principalmente no meio da Computação. Seu estudo surgiu na tentativa de físicos simularem sistemas regidos pela Mecânica Quântica por computadores clássicos, o que se conjecturou inviável. Portanto, um novo modelo computacional que utiliza a estrutura quântica da matéria para computar foi teorizado para suprir estas deficiências. Este trabalho tem como objetivo principal estudar as influências da Computação Quântica na Teoria da Computação. Para atingir tal objetivo, primeiramente são expostos os conhecimentos básicos da Mecânica Quântica através de uma linguagem voltada para Teóricos de Computação sem conhecimento prévio na área, de forma a remover a barreira inicial sobre o tema. Em seguida, serão apresentadas inovações na área da Teoria de Computação oriundas da Computação Quântica. Começaremos com os principais Algoritmos Quânticos desenvolvidos até hoje, que foram os primeiros passos para demonstrar a possível superioridade computacional do novo modelo. Dentre estes algoritmos, apresentaremos o famoso Algoritmo de Shor, que fatora números em tempo polinomial. Adicionalmente, neste trabalho foram estudados tópicos mais avançados e atuais em Computabilidade e Complexidade Quânticas. Sobre Autômatos Quânticos, foram estudados aspectos de um modelo que mistura estados clássicos e quânticos, focando na comparação do poder computacional em relação aos Autômatos Finitos Clássicos. Do ponto de vista de Classes de Complexidade, será abordada a questão se em linguagens da classe QMA, o análogo quântico da classe NP, consegue-se atingir probabilidade de erro nulo na aceitação de instâncias positivas / Abstract: Quantum Computing is a relatively new area and it is not well known, mainly among Computer Scientists. It has emerged while physicists tried to simulate Quantum Systems with classical computers efficiently, which has been conjectured impossible. Then, a new computational model that uses the quantum structure of matter to perform computations has been theorized in order to perform these operations. We intend in this work to study the influences of Quantum Computing in Theoretical Computer Science. In order to achieve this goal, we start by presenting the basics of Quantum Computing to Theoretical Computer Science readers with no previous knowledge in this area, removing any initial barriers for a clean understanding of the topic. We will then follow by showing innovations in Theoretical Computer Science introduced by Quantum Computation. We start by showing the main Quantum Algorithms, that exemplify advantages of the new computational model. Among these algorithms, we will present the Shor Algorithm that factors numbers in polynomial time. We follow with more advanced topics in Quantum Computability and Complexity. We study Quantum Finite Automata Models that work with quantum and classical states, focusing on comparing their computational power with Deterministic Finite Automata. In Complexity Theory, we study the question if for languages in QMA, the quantum analogue of NP, zero probability error can be achieved in yes-instances / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

[pt] Os códigos de prefixo têm importância fundamental na comprenssão e transmissão de dados. Estes códigos também apresentam relações com problemas de busca. Neste tese, apresentamos novos resultados estruturais e algorítimos sobre a classe dos códigos de prefixo. Explicamos teoricamente as boas taxas de compressão observadas para alguns métodos utilizados na prática. Propomos também algoritmos eficientes para construção de códigos de prefixo ótimos e variantes. Os principais resultados aqui descritos são os seguintes: - um novo algoritmo paralelo para construção de códigos de prefixos ótimos: - uma cota superior para a perda de compressão introduzida pela restrição de comprimento nos códigos de prefixo: - uma cota superior para a perda de compressão introduzida pela restrição de comprimento nos códigos de prefixo alfabéticos: - um algoritmo aproximativo e linear para construção de códigos de prefixo com restrição de comprimento: - um algoritmo aproximativo com complexidade 0(n log n) para construção de códigos de prefixo alfabéticos com restrição de comprimento: - uma nova versão de algoritmo WARM-UP com complexidade fortemente polinomial: - um algoritmo linear para reconhecer códigos de prefixo ótimos com restrição de comprimento: - uma prova afirmativa da conjectura de Vitter sobre o desempenho dos códigos de Huffmann dinâmicos construídos pelo algoritmo FGK (Faller, Gallanger e Knuth) / [en] The prefix codes play an important role in data compression and data communication. These codes also present relation with search problems. In this thesis, we present new structural and algorithmic results concerning the prefix code class. We theoretically explain results related to the high compression rates of some methods that have been used for pratical purposes. We also propose efficient algorthims for constructing optimal prefix codes and some variants. The major results are listed below: -a new parallel algorithm for constructing optimal prefix codes: -a sharp upper bound for the compression loss introduced due usage of length restricted prefix codes: -an upper bound for the compression loss introduced due the usage of length restricted alphabetic prefix codes: -an 0(n log n) time approximative algorithm for constructing lenght restricted prefix code: -a 0(n log n) time approximative algorithm for constructing lenght restricted alphabetic prefix code: -a strongly polinomial version for the WARM-UP algorithm: -a linear time algorithm for recognizing optimal length restricted prefix codes: -a proof for Vitter´s conjecture about the perfomance of the Dynamic Huffman Codes constructed by FGK (Faller, Gallager and Knuth) algorithm.