Prévia do material em texto

Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Unidade 1
Teoria da Computabilidade: Programas e Máquinas
Aula 1
Programas e máquinas
Introdução
Olá, estudante! 
Nesta unidade, os alunos terão a oportunidade de explorar um dos mundos mais fascinantes: o
mundo dos programas e máquinas. Esse é um tema fundamental para a análise de
computabilidade e complexidade de algoritmos. Serão aprensentados os conceitos basilares
acerca de computabilidade, programas e máquinas, os quais são essenciais para o entendimento
da primeira etapa do curso. 
Compreender de forma aprofundada os programas e máquinas é de extrema importância para a
melhor concepção da base de princípios fundamentais da computabilidade. O objetivo desta
unidade é fornecer parâmetros em prol da clara visão de como funcionam os programas e
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
máquinas, para isso, serão utilizados insights práticos relacionados à aplicação dos
conhecimentos, contudo, já na esfera pro�ssional. Ademais, será oportunizada a prática a partir
de exempli�cações concretas, bem como, por meio de exercícios interativos, o que dará subsídio
para a consolidação do seu aprendizado. 
Por essa razão, você é nosso convidado para aprofundar os seus conhecimentos de forma
didática acerca deste vasto campo que é a teoria da computabilidade, abarcando ainda os
programas e máquinas. Lembre-se, as habilidades fomentadas por você neste momento de
aprendizado serão a sua vantagem de conhecimento. Iniciaremos a jornada de aprendizado
agora! 
Conceitos fundamentais sobre programas e máquinas
Computabilidade pode ser apontada enquanto o estudo acerca dos limites do que pode ser
computado, ou seja, corresponde ao estudo responsável pela indicação de parâmetros limitantes
daquilo que de fato pode ser computado. Nesse sentido, ela tem por escopo a busca pelo
entendimento de quais problemáticas podem ser resolvidos por um computador, bem como
aqueles que não podem. Consiste na área da ciência da computação responsável pela
investigação dos limites antes mencionados, assim, obtendo a capacidade de fornecer
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
ferramentas em prol da análise de complexidade de problemas, do mesmo modo, para realizar a
comparação de algoritmos diversi�cados (Diverio e Menezes, 2009). 
Programas são instruções dadas em conjunto e que possuem a capacidade de realizar o
direcionamento de um computador à execução de tarefas especí�cas. Tais instruções são
comandos dados para a condução do computador no que fazer. Os programas possuem uma
divisão principal, qual seja: programas monolíticos, programas iterativos e programas recursivos
(Diverio e Menezes, 2009). Vamos ver a seguir a diferença entre cada um desses programas 
Programas monolíticos são aqueles considerados os mais simpli�cados, sendo estes os
responsáveis pela execução de instruções utilizando-se de uma ordem única sem a utilização de
loops ou condições (Diverio e Menezes, 2009). Tal característica agrega a esse tipo de programa
a facilidade para escrever e entender, contudo, há a possibilidade de apresentar uma menor taxa
de e�ciência correlata a problemáticas complexas. 
Os programas iterativos fazem o uso de loops em prol da repetição de um conjunto de instrução
até o momento em que uma condição seja atendida com sucesso, ou seja, o conjunto de
instruções é executado quantas vezes for necessário, visando exclusivamente a execução e�caz
de uma determinada questão. Isto é válido quando se trata de problemas que podem sofrer
divisões em pequenas partes, podendo ser solucionados mais repetidamente. 
No que tange aos programas recursivos, estes são considerados imprescindíveis quando há
aqueles problemas relativos à capacidade de divisão em subproblemas semelhantes. 
Máquinas são ferramentas responsáveis pela transformação de dados. Um dos melhores
exemplos de máquinas é o tão usado computador, utilizado de forma corriqueira no dia a dia.
Todavia, há diversos outros tipos de máquinas, como, por exemplo, os robôs, as máquinas em
geral no ramo industrial e os dispositivos médicos. 
Segundo Diverio e Menezes (2009), a máquina consiste em um sistema receptor de informações
de entrada, que tem a capacidade de realizar a transformação destas de modo a seguir um
conjunto de instruções e, por conseguinte, realizar a produção de informações de saída. 
Tal de�nição guarda semelhança com à de�nição primária, também chamada de de�nição
tradicional, de máquina, a qual refere-se à máquina enquanto um dispositivo com a capacidade
de realizar a conversão de energia de uma forma para outra, em busca da realização de uma
tarefa especí�ca. Na ciência da computação, máquinas realizam a conversão de informações de
uma forma para outra com o escopo de realizar tarefas especí�cas.
A base da computabilidade
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
A teoria da computabilidade pode ser apontada enquanto um dos pilares da ciência da
computação, fomentando, de forma sólida, o desenvolvimento e�caz de algoritmos e a
possibilidade de compreensão em relação às restrições inerentes às máquinas computacionais. 
Além dos mais, essa teoria perpassa pelo estudo da complexidade de problemas, no qual
corresponde ao parâmetro responsável por mensurar o tempo ou recursos de processamento
considerados imprescindíveis em busca da resolução do problema. A análise da complexidade
passa a ser de vasta importância no âmbito do desenvolvimento de algoritmos e�cientes, o que
possibilita que cientistas da área da computação realizem testes de comparação e avaliação da
e�cácia de diversi�cados algoritmos, os quais postos em ação para �ns de solucionar uma
mesma problemática. 
A área dos programas apresenta uma vasta gama de complexidade, apresentando ainda
variações de simples algoritmos matemáticos até variações em sistemas operacionais
apontados como completos, sendo componentes basilares em prol do bom funcionamento de
computadores, o que lhes permite a concretização de um leque variado de tarefas. 
Nesse sentido, programas são objetos de estudos tendo como pauta a compreensão de quais
são passíveis de resolução por intermédio de um computador, bem como, qual a viabilidade
computacional de determinada problemática e a probabilidade da existência de programas com
capacidade de solução especí�ca. 
Outro ponto importante de se ressaltar, é a investigação correlata à complexidade dos
programas, por meio de métrica, responsável pela avaliação do tempo ou dos recursos de
processamento que são utilizados para a execução de um programa. A avaliação da
complexidade dos programas faz-se necessária para o devido desenvolvimento de programas, a
�m de que eles consigam atingir cada vez mais um número maior de e�cácia. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
No que tange às máquinas físicas, estas compreendem os dispositivos concretos, ou seja,
aqueles com existência no mundo real, possuindo componentes tangíveis, como circuitos,
memória e armazenamento. Máquinas físicas esbanjam a capacidade intrínseca de executar
programas de computador, que são conjuntos de instruções que funcionam como um caminho a
ser seguido por um computador, tendo o objetivo de executar tarefas especí�cas. 
Há, em contraste com as máquinas físicas, as máquinas lógicas, que por sua vez, estão no
domínio matemático, de modo a representar os moldes abstratos das máquinas físicas. A sua
existência se dá apenas no âmbito conceitual. Por outro lado, as máquinas lógicas também
possuem a capacidade de execução de programas de computador.  
Por �m, a teoria da computabilidade dedica-se, ainda, ao estudo na ceara da complexidade das
máquinas, no qual utiliza-se uma métrica elaborada para avaliar o tempo ou ainda os recursos de
processamento utilizados para a execução de programas em uma máquina especí�ca (Diverio e
Menezes, 2009). 
Aplicação da Teoria da Computabilidade: programas e máquinas
Iniciaremos explorando os programas,que consistem em conjuntos de instruções com o objetivo
de orientar o computador para a execução de tarefas especí�cas. Considerando isso, vamos
usar a imaginação! Você está desenvolvendo um programa simples, com o objetivo de realizar o
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
cálculo da média das notas de estudantes. A partir de um código escrito por você, é feita a
instrução ao computador para que ele faça a somatória das notas e realize a divisão pelo
número de estudantes, buscando assim uma média. Isso é um programa em ação. 
Imagine um ambiente corporativo! Nesses, os programas são utilizados em prol da
automatização de tarefas repetitivas, vamos exempli�car com um escritório de
recrutamento, nesse caso, a tarefa é processar os currículos e organizá-los com apenas
alguns cliques.  
Agora vamos falar das máquinas. Estas são dispositivos físicos com a �nalidade de executar os
programas. Pensando nisso, considere o computador do seu local de trabalho ou até mesmo o
de estudos utilizado nas bibliotecas das faculdades. Eles são máquinas que operam a partir do
seguimento de instruções dos programas que são executados neles por você. Então, pode-se
concluir que sem programas a máquina que você utiliza não passaria de uma peça de hardware
inerte. 
Em ambientes empresariais, há diversos tipos de servidores de alta potência, que são máquinas
com dedicação exclusiva para a execução de programas complexos, podendo suportar
operações de negócios, como é o caso de empresas de investimento. Em se tratando de Internet
das Coisas (IoT), máquinas com sensor de movimento executam o acender e o apagar de luzes
nos ambientes. 
Tais conceitos se relacionam com a Teoria da Computabilidade, de modo que auxilia na
compreensão de quais problemáticas podem ser solucionados por um computador. Vamos
pensar em um exemplo prático: a busca de músicas no Youtube. Quando é feita a pesquisa na
barra de buscar, o programa do mecanismo utiliza-se de busca executada em máquinas remotas,
como resultado, retorna para você de acordo com o solicitado. Nesse sentido, a Teoria da
Computabilidade é responsável por auxiliar na garantia do retorno e�ciente das buscas e que
problemas, considerados como complexos, sejam computacionalmente executáveis. 
Em síntese, buscou-se proporcionar a você a identi�cação da relação dos conceitos teóricos da
Teoria da Computabilidade com as aplicações na prática. Pode-se observar melhor como os
programas e as máquinas interagem e estão presentes no cotidiano da sociedade de forma
geral, tanto na vida pessoal quanto na pro�ssional. Compreender a base de conceitos é o
primeiro passo para aqueles que desejam trabalhar com tecnologia da informação e ciência da
computação de forma e�ciente, propiciando conhecimento e experiência práticas com a
capacidade de aplicação em uma vasta gama de cenários. Ao passo em que se avança no
aprendizado é importante lembrar a importância dos conceitos primários.
Videoaula: Programas e máquinas
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante! 
Tenho a honra em lhe dar as boas-vindas ao vídeo resumo. Nele, será sintetizado de forma clara
e objetiva os postos-chaves sobre a Teoria da Computabilidade: programas e máquinas. Nos
próximos minutos, lhe daremos uma visão panorâmica, como uma cápsula de conhecimento
sobre a temática. 
No decorrer do vídeo, serão abordados os pontos principais e destacados os conceitos-chaves,
sendo fornecido ainda insights para te ajudar a compreender de forma mais didática o item.  
Desejo que você esteja apto ao �nal deste vídeo para explanar com tranquilidade o assunto e
sinta-se seguro para avançar nos estudos. 
Vamos começar! 
Saiba mais
A Teoria da Computabilidade é um campo fascinante e crucial da ciência da computação que vai
muito além do que podemos cobrir em vídeo ou texto. Vamos aprofundar o nosso
conhecimento! 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Comece com livros que oferecem uma introdução detalhada a essa teoria e que são excelentes
opções para iniciantes. 
Teoria da computação: máquinas universais e computabilidade. V.5 (Livros didáticos informática
UFRGS). Porto Alegre: Bookman, 2009.  
Referências
DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computabilidade.
V.5 (Livros didáticos informática UFRGS). Porto Alegre: Bookman, 2009. Disponível em:
https://integrada.minhabiblioteca.com.br/books/9788577808311 
Aula 2
Equivalência de programas e máquinas
Introdução
https://integrada.minhabiblioteca.com.br/books/9788577808311
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Olá, estudante! 
Nesta aula, será abordada a equivalência de Programas e Máquinas, de modo que, nesta jornada
de aprendizado, será explorado um dos conceitos fundamentais no mundo da ciência da
computação, o qual impacta diretamente no desenvolvimento de software e sistemas
computacionais. 
A equivalência de programas e máquinas consiste na pedra angular da con�abilidade e
portabilidade de software. A compressão de tal conceito se assemelha ao desvendar de
segredos correlatos à capacidade de um programa e à sua funcionalidade de forma consistente
em diversi�cados ambientes e plataformas. Você pode construir um futuro pro�ssional brilhante
ao passar a considerar a importância de possuir a habilidade de criar um software que possua
características robustas e adaptáveis em prol da variedade de con�gurações, o que é altamente
valorizado no mercado e o torna, consequentemente um pro�ssional mais quali�cado. 
No decorrer do estudo, vamos mergulhar na teoria existente sobre a equivalência de programas e
máquinas, de modo a explorar casos práticos e construir um aprendizado de como aplicar o
conhecimento no desenvolvimento de um software na prática. 
Vamos começar? 
Conceitos e fundamentos sobre equivalência de programas e máquinas
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
A computação consiste no processo que realiza cálculos, processa informações e executa
tarefas utilizando um sistema de processamento de dados, como, por exemplo, um computador.
A computação consiste, também, na manipulação de dados por meio de algoritmos, os quais
são conjuntos de instruções precisas (Diverio e Menezes, 2009). 
Apesar de ser apontada apenas enquanto uma função, na realidade a função computada
corresponde a um bloco de código ou um procedimento com capacidade de aceitação de
entradas (parâmetros) e produção de saídas (resultados) baseando-se em algoritmos ou na
lógica já de�nida. Funções podem ser entendidas enquanto fundamentais para a programação,
bem como para a resolução de problemas computacionais (Diverio e Menezes, 2009). 
Exemplos de computação e função computada:  
A função f(x) = x + 1 é computada pelo programa x + 1. 
A função g(x) = x * 2 é computada pelo programa x * 2. 
Já a equivalência de programas consiste na ideia basilar de que dois programas de computador
divergentes podem produzir resultados idênticos quando houver o fornecimento das mesmas
entradas. Nesse sentido, ainda que os programas possam vir a possuir implementações
diferentes, as suas saídas serão idênticas para um conjunto determinado de entradas (Diverio e
Menezes, 2009).. Por �m, a busca pela equivalência de programas é fundamental para o fomento
da garantia de que o software possua con�abilidade, bem como que diferentes implementações
podem alcançar o mesmo objetivo. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Exemplos de equivalência de programa:  
Os programas x + 1 e 2 * x são equivalentes, pois produzem a mesma saída para qualquer
entrada. 
Os programas x + 1 e x - 1 não são equivalentes, pois produzem saídas diferentes para as
entradas 0 e 1. 
A equivalência demáquinas diz respeito à capacidade de diferentes sistemas ou máquinas de
computação executarem os mesmos programas e produzirem os mesmos resultados. Isso
implica que um programa escrito para uma máquina ou sistema deve ser executado com
sucesso em outra máquina ou sistema, desde que essas máquinas sejam consideradas
equivalentes em termos de poder computacional e capacidades. A equivalência de máquinas é
essencial para a portabilidade de software, permitindo que programas sejam utilizados em uma
variedade de ambientes de hardware sem a necessidade de reescrevê-los (Diverio e Menezes,
2009). 
Considerando o que foi mencionado anteriormente, vale ressaltar que uma Máquina de Turing e
uma Máquina de Von Neumann possuem equivalência entre si, isso em razão de ambas
possuírem o poder de executar o mesmo conjunto de programas. Por outro lado, elas não
possuem equivalência, devido ao fato da Máquina de Johnson não poder realizar a execução de
todos os programas que a Máquina de Turing consegue vir a executar. 
Os conceitos de computação, função computada, equivalência de programas e equivalência de
máquinas são as bases necessárias para a compreensão da teoria da computação, haja vista
que estes são utilizados em prol da comparação de dois programas ou duas máquinas com o
objetivo de determinar se estes são equivalentes no que tange a sua capacidade de
computacional. 
Fundamentos da computação e equivalência de programas e máquinas
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
A computação consiste no processo de realizar cálculos, efetuar o processamento de
informações e executar tarefas utilizando-se de um dispositivo computacional. Já a função
computada consiste na capacidade de um programa ou algoritmo em realizar a execução de
tarefas especí�cas, de modo a transformar dados de entrada em saída de forma sistemática
(Diverio e Menezes, 2009).  
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Ademais, o desenvolvimento de programas possui algumas etapas, como: análise, projeto,
implementação, teste e manutenção. Nesse sentido, as ferramentas incluem linguagens de
programação, ambientes de desenvolvimento e depuradores. 
A equivalência de programas é a capacidade de dois programas diferentes produzirem os
mesmos resultados para um determinado conjunto de entradas, sendo isso crucial para analisar
se uma versão de um programa é correta ou se uma otimização não introduziu erros (Diverio e
Menezes, 2009). . 
Características: 
Corretude: dois programas são considerados equivalentes se produzirem as mesmas
saídas para todas as entradas válidas. 
Abstração: a equivalência de programas não depende de detalhes de implementação e sim
do comportamento ora observado. 
Para veri�car a equivalência de programas, as técnicas que podem ser utilizadas são: prova
formal, testes extensivos e análise estática. 
A equivalência de máquinas consiste na capacidade de diferentes máquinas, como, por exemplo,
computadores, processadores e arquiteturas, executarem os mesmos programas de maneira
equivalente, ou seja, igual, sendo uma ação necessária para a garantia da portabilidade de
software (Diverio e Menezes, 2009). . 
Características: 
Portabilidade: se um programa é equivalente em diferentes máquinas, ele pode ser
executado sem modi�cação. 
E�ciência: a equivalência de máquinas também pode ser usada para otimizar o
desempenho, escolhendo a máquina mais adequada para uma tarefa especí�ca. 
Em prol da garantia da equivalência de máquinas, é necessário compreender a arquitetura de
cada máquina, compilar programas para diferentes alvos e, também, realizar testes de
desempenho. 
Os três conceitos estão interligados no contexto da computação, sendo a função computada
implementada por meio de programas, sendo a sua equivalência crucial em prol da garantia de
que as diferentes implementações, ainda que de uma mesma função, se comportem de forma
igual em diferentes máquinas. Por �m, a equivalência de máquinas está ligada à capacidade de
execução de programas equivalentes em diferentes sistemas, assim, mantendo o mesmo
resultado. 
Por �m, ter a compreensão e aplicar tais conceitos basilares é essencial para o desenvolvimento
teste e a manutenção do software, a �m de que seja alcançado um alto padrão de qualidade,
garantindo a sua funcionalidade de modo que ela seja consistente em diferentes contextos
computacionais. Essas ações são de suma importância para solucionar problemas de alta
complexidade e, também, para aproveitar ao máximo a capacidade da computação moderna. 
Aplicando fundamentos da computação e equivalência
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
A computação trata do uso de dispositivos computacionais com a �nalidade de processar
informações e executar tarefas. Já a função computada, refere-se à capacidade de realização de
tarefas especi�cas dos programas. 
Observe o seguinte exemplo 
Imagine que você trabalha em uma loja de roupas e precisa calcular o valor total de uma
compra. A função computada nesse caso seria a de um programa que consegue receber a
lista de itens e calcula o total destes, aplicando descontos, se for o caso. Nesse cenário,
você desenvolve a habilidade de projetar e implementar algoritmos com a capacidade de
resolver problemas na prática, ou seja, no mundo real, de modo que venha a melhorar a sua
habilidade de resolução de problemas e lógica. 
A equivalência de programas consiste na capacidade de dois programas diferentes possuírem a
e�ciência de produzirem os mesmos resultados para um conjunto de entradas. 
Vamos a um exemplo prático! 
Suponha que você está desenvolvendo um projeto de software e sente a necessidade de
otimizar uma função de busca. Nesse sentido, você reescreve a função de uma forma mais
e�ciente, entendendo ser crucial garantir que a nova versão seja equivalente à anterior, ou
seja, produza os mesmos resultados, mas agora de uma forma melhorada. Nesse cenário,
você aprende a realizar testes de equivalência, buscando garantir que as alterações no
código não venham a afetar o comportamento já esperado do programa, assim,
desenvolvendo habilidades de teste de software e a análise crítica. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
 A equivalência de máquinas está relacionada à capacidade de diferentes máquinas
possuírem a e�ciência de executarem os mesmos programas de maneira igual. 
Veja a seguir! 
Você está trabalhando em uma empresa de desenvolvimento de software e precisa garantir
que o aplicativo que você construiu para o Windows também funcione corretamente em
sistemas macOS. Aqui, a equivalência de máquinas é fundamental para a portabilidade do
software, a �m de que o aplicativo funcione em ambos os casos. Nesse contexto, você
aprende a adaptar o seu software para diferentes arquiteturas, de modo a melhorar as suas
habilidades de desenvolvimento multiplataforma e aumentando, também, a sua
compreensão das nuances das máquinas. 
Em síntese, os conceitos abordados são fundamentais para a computação moderna e têm
aplicações em diversos campos pro�ssionais. Ao realizar a aplicação destes em exemplos
práticos, você desenvolve diversas competências, como: resolução de problemas, análise
crítica, pensamento lógico e adaptabilidade, habilidades essas que são cruciais em
qualquer carreira relacionada à tecnologia da informação.  
Por �m, isso permite e dá a liberdade para que você se torne um pro�ssional mais
capacitado e preparado para enfrentar desa�os complexos no mundo da computação,
considerando todas as questões que foram levantadas nesta aula, permitindo ainda que
você tenha acesso a informações basilares de conhecimento, que são de suma
importância para o melhor aprendizado, de modo que a prática seja tranquila e sem
grandes desa�os.
Videoaula: Equivalência de programas e máquinas
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistirmesmo sem conexão à internet.
Olá, estudante! 
É com grande satisfação que lhe damos as boas-vindas a este vídeo resumo. Nele, será
apresentado a você, de forma clara e concisa, os pontos essenciais relacionado à compreensão
dos tipos de programas, bem como, aqueles necessários para entender a equivalência entre
programas. 
Ao longo deste vídeo, abordaremos os principais aspectos e enfatizaremos os conceitos-chaves,
oferecendo insigths adicionais para facilitar a compreensão do assunto de maneira mais
didática. 
Vamos começar! 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Saiba mais
Para o aprofundamento do aprendizado dos conteúdos, apresentaremos alguns recursos que
podem ser úteis. São eles: 
Existem diversas plataformas de exercícios online que podem ser úteis para a prática dos
conceitos de computação. 
O LeetCode é uma plataforma online que oferece uma ampla variedade de problemas de
programação e desa�os relacionados à computação, algoritmos e estruturas de dados. É uma
ferramenta valiosa para aprimorar as habilidades de programação e compreender os conceitos
de computação, equações de programas e equivalência de máquinas. 
Referências
https://leetcode.com/
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computabilidade.
V.5 (Livros didáticos informática UFRGS). Porto Alegre: Bookman, 2009. Disponível em:
https://integrada.minhabiblioteca.com.br/books/9788577808311. Acesso em: 31 out 2023. 
SIPSER, M. Teoria da Computação. 3ed. São Paulo: Pearason Education do Brasil, 2018. 
GRIES, D. Equivalência de Programas. In: Revista Teoria da Computação, v;3, n.1, p.1-22, 1976. 
Aula 3
Máquinas de registradores - Norma
Introdução
https://integrada.minhabiblioteca.com.br/books/9788577808311
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Olá, estudante! 
Assim como a con�abilidade e a portabilidade de software, as máquinas de registradores
possuem um papel fundamental no mundo dos negócios e das operações �nanceiras. 
As Máquinas de Registradores - Norma (MRN) correspondem ao modelo de máquina abstrata
que é Turing equivalente, ou seja, qualquer problema que pode ser resolvido por uma Máquina de
Turing também poderá ser solucionado por uma MRN. 
As MRN são consideradas cruciais na ciência da computação, isso em razão delas serem a base
para diversos algoritmos e aplicações, as quais são importantes no mundo dos negócios e das
operações �nanceiras, considerando que a sua utilização basilar se concentra na implementação
de sistemas de controle e automação. 
Ao longo desta aula, vamos aprender mais sobre a MRN, explorar casos práticos e compreender
melhor como aplicar esse conhecimento no mundo real. 
Vamos começar? 
Conceitos e fundamentos sobre Máquinas de Registradores
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
As Máquinas de Registradores são dispositivos que possuem destaque em razão da utilização
de um ou mais registradores. Tal modelo teórico possui um papel fundamental na ciência da
computação, de modo que permite a descrição detalhada, bem como a análise aprofundada da
arquitetura de tipo especí�co de máquina computacional (Diverio e Menezes, 2009).  
Tais máquinas representam uma classe abstrata, que por sua vez, trata de um conjunto de
registradores, em que cada registrador possui a capacidade de armazenar valores inteiros
positivos e ainda executar operações aritméticas simples, como adição, subtração, multiplicação
e divisão. A versatilidade a torna uma ferramenta crucial em prol da compreensão dos princípios
fundamentais da computação, do mesmo modo para a análise minuciosa do comportamento de
algoritmos e problemas computacionais. 
Para além de valor educacional, as Máquinas de Registradores também têm um desempenho
signi�cativo como uma ferramenta teórica na pesquisa em ciência da computação, vindo prestar
auxílio na análise da complexidade computacional, modelagem de sistemas computacionais e
na exploração das fronteiras da computação teórica. 
Por outro lado, a Máquina Norma, que também desempenha um papel fundamental na ciência da
computação, serve como marco de referência em relação à compreensão e à análise de
Máquinas de Registradores. As máquinas teóricas, em razão de sua natureza abstrata e
simpli�cada, dispõem um padrão consistente pelo qual outras arquiteturas de máquinas de
registradores podem ser avaliadas e comparadas (Diverio e Menezes, 2009). 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Estas proporcionam uma base sólida para estudos comparativos, destacando as diferenças e as
semelhanças entre várias Máquinas de Registradores e, sincronicamente, proporcionando a
melhor compreensão relacionada às capacidades e limitações relacionadas a esses sistemas já
mencionados. A partir da criação desse modelo simpli�cado, as Máquinas Norma passaram a
facilitar a análise relacionada a propriedades fundamentais, capacidade de computação, bem
como da e�ciência de diversi�cadas Máquinas de Registradores, de modo a contribuir para o
desenvolvimento e o aprofundamento do conhecimento na Teoria da Computação e na
construção de algoritmos e�cazes. 
Uma das características notáveis que pode ser utilizada para de�nir as "Máquinas Norma" é a
sua capacidade de operar como máquinas universais, ou seja, uma Máquina Norma pode ser
programada de maneira engenhosa para simular o comportamento de forma virtual de qualquer
outra Máquina de Registradores, independentemente das nuances especí�cas de sua arquitetura
( Diverio e Menezes, 2009). 
Em síntese, por meio de uma programação habilidosa e adequada, uma Máquina Norma tem a
possibilidade de desempenhar a função de uma máquina universal, executando qualquer
algoritmo que uma Máquina de Registradores seja capaz de realizar. Esse conceito não apenas
ilustra, mas também consagra o princípio fundamental da computação universal, que é
amplamente explorado e fundamenta a ciência da computação e a Teoria da Computação. Essa
propriedade de universalidade é de suma importância para a compreensão aprofundada dos
limites e das vastas possibilidades do campo da computação, desempenhando um papel de
destaque como uma pedra angular central na teoria mencionada.
Máquinas de Registradores
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Máquinas de Registradores são um modelo de máquina abstrata que é Turing equivalente.
Assim, qualquer problema que pode ser resolvido por uma Máquina de Turing também pode ser
resolvido por uma máquina do tipo registradora. 
Máquina de Registradores é um sistema abstrato de�nido pela quíntupla: 
Q = conjunto de estados 
Σ = alfabeto de entrada 
Γ = alfabeto de saída 
δ: Q × Σ Q × Γ × {A,B,...,X,Y} {A,B,...,X,Y} × {+1,-1}  
q0 Q: estado inicial 
O estado inicial q0 é o estado em que a máquina inicia a execução. A função δ é responsável
pela de�nição da transição de estado da máquina. A função δ toma como entrada o estado atual
q, o símbolo de entrada s, e o registrador A. A função δ retorna o novo estado q', o símbolo de
saída s', e o registrador A'. 
A Máquina Norma possui um conjunto in�nito de registradores naturais como memória e três
instruções: 
A:= A+1 (adiciona um) 
A:= A-1 (subtrai um) 
A = 0 (testa se zero) 
Os registradores podem conter um elemento qualquer de números naturais, isto é,
V   N
Os registradores são denotados por A, B, ..., X, Y. A operação A:= A-1, quando A=0, não altera o
seu valor. Os registradores X e Y são especiais. 
Máquina Norma é caracterizada por seu conjunto de instruções limitado, que é composto de
apenas três operações. Apesar de seu conjunto de instruções limitado, elas são Turing
equivalentes, o que signi�ca que ela pode ser usadas para implementar qualquer algoritmo (
Diverio e Menezes, 2009). 
Vale ressaltar ainda que há uma gama de aplicações em uma Máquina de Registradores.
Observe abaixo:  
Soma: a soma de dois números pode ser calculada usando uma Máquinade Registradores com
dois registradores, A e B. Essa máquina inicializa A com o primeiro número e B com o segundo
número. Em seguida, a máquina registradora executa as instruções A:=A+1 repetidamente até
que B seja igual a zero. O valor �nal em A é a soma dos dois números. 
Multiplicação: a multiplicação de dois números pode ser calculada usando uma Máquina de
Registradores com três registradores, A, B, e C. Esta inicializa A com o primeiro número, B com o
segundo número, e C com zero. Em seguida, a máquina registradora executa as instruções
A:=A+B repetidamente até que B seja igual a zero. O valor �nal em C é a multiplicação dos dois
números. 
Recursividade: a recursividade pode ser implementada em uma Máquina de Registradores
usando um registrador especial X para armazenar o estado da recursão. A máquina registradora
inicializa X com o estado inicial da recursão. Em seguida, ela executa o corpo da recursão. Após
a execução do corpo da recursão, essa máquina armazena o estado �nal da recursão em X. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
As Máquinas de Registradores são um modelo de máquina abstrata simples e e�ciente que é
Turing equivalente. Elas podem ser usadas para implementar qualquer algoritmo, incluindo
algoritmos recursivos. A Máquina Norma é um tipo especí�co de máquina registradora que é
caracterizada por seu conjunto de instruções limitado. Apesar de seu conjunto de instruções
limitado, a Máquina Norma é Turing equivalente. 
Máquinas de Registradores
As Máquinas de Registradores são frequentemente usadas como um modelo de execução para
as linguagens de programação, portanto, isso permite que os compiladores sejam capazes de
traduzir os programas de alto nível em instruções de máquina que podem vir a ser executadas
por meio dessas máquinas. 
Ademais, estas são usadas ainda para implementar o núcleo de muitos sistemas operacionais. O
núcleo é responsável pela gestão de recursos do sistema, como memória, processador e
dispositivos de entrada e saída. A sua utilização abrange ainda a modelação do hardware de
computadores. Isso permite que os engenheiros projetem computadores que sejam e�cientes e
con�áveis. 
Por �m, elas são utilizadas para implementar algoritmos de inteligência arti�cial, como
aprendizado de máquina e processamento de linguagem natural. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Exemplos de aplicações especí�cas 
A soma de dois números pode ser implementada usando uma Máquina de Registradores
com dois registradores, A e B. A máquina inicializa A com o primeiro número e B com o
segundo número. Em seguida, esta executa as instruções A:=A+1 repetidamente até que B
seja igual a zero. O valor �nal em A é a soma dos dois números. 
A multiplicação de dois números pode ser implementada usando uma Máquina de
Registradores com três registradores, A, B, e C. Ela inicializa A com o primeiro número, B
com o segundo número, e C com zero. Em seguida, a máquina registradora executa as
instruções A:=A+B repetidamente até que B seja igual a zero. O valor �nal em C é a
multiplicação dos dois números. 
A recursividade pode ser implementada usando uma Máquina de Registradores usando um
registrador especial, X, para armazenar o estado da recursão. Essa máquina inicializa X
com o estado inicial da recursão. Em seguida, a máquina registradora executa o corpo da
recursão. Após a execução do corpo da recursão, a máquina armazena o estado �nal da
recursão em X. 
Vantagens e desvantagens 
As vantagens de Máquinas de Registradores são: 
As desvantagens das Máquinas de Registradores são:
Essas máquinas são um modelo poderoso e versátil de máquina abstrata elas podem ser usadas
para implementar uma ampla gama de algoritmos e aplicações. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Videoaula: Máquinas de registradores - Norma
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante! 
É com grande prazer que lhe damos as boas-vindas a este vídeo resumo. Nele, vamos apresentar
de maneira clara e sucinta os pontos essenciais relacionados à compreensão das Máquinas de
Registradores e da Máquina Norma. Nos próximos minutos, forneceremos uma visão abrangente
deste tópico crucial. Durante este vídeo, exploraremos os aspectos fundamentais e
destacaremos os conceitos-chave, fornecendo insights adicionais para tornar a compreensão
desse assunto mais didática e acessível. Vamos começar! 
Saiba mais
Para o aprofundamento do aprendizado dos conteúdos apresentaremos alguns recursos que
podem ser úteis. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Livros Didáticos e Acadêmicos: existem muitos livros de referência na área da Teoria da
Computação e ciência da computação que exploram Máquinas de Registradores e tópicos
relacionados. Alguns exemplos incluem "Introdução à Teoria da Computação" de Michael Sipser
e "Estruturas de Dados e Algoritmos em Java" de Robert Lafore
Referências
DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computabilidade.
V.5 (Livros didáticos informática UFRGS). Porto Alegre: Bookman, 2009. Disponível em:
https://integrada.minhabiblioteca.com.br/books/9788577808311. Acesso: 31 out 2023. 
Aula 4
Máquina de Turing
Introdução
https://integrada.minhabiblioteca.com.br/books/9788577808311
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Olá, estudante! 
As Máquinas de Turing são um conceito fundamental na ciência da computação e
desempenham um papel crucial na compreensão da natureza e das limitações da computação.
Proposta por Alan Turing em 1936, essa abstração teórica é um marco na história da
computação e é a base para todo o campo da Teoria da Computação. 
Basicamente, uma Máquina de Turing é um modelo abstrato de um dispositivo de computação.
Consiste em uma �ta in�nita, um cabeçote de leitura/gravação e um conjunto �nito de estados. O
poder dela reside na sua simplicidade e versatilidade. 
Exploraremos a natureza da ciência da computação, compreenderemos os limites teóricos da
computação e os fundamentos do desenvolvimento de algoritmos, linguagens de programação e
sistemas de software. É uma ferramenta importante para avaliar a viabilidade computacional de
um problema e continua a moldar a tecnologia da informação. 
Vamos começar? 
Principais conceitos sobre a Máquina de Turing
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Uma Máquina de Turing é um modelo teórico de computação que pode ser usado para �ns de
calcular qualquer função que seja computável. Assim, ela é composta por uma �ta in�nita
dividida em células, um cabeçote de leitura/gravação que pode se mover para a esquerda ou
para a direita e um conjunto �nito de estados. Essa máquina é capaz ainda de operar de acordo
com um conjunto de regras que especi�cam como ele lê, escreve e se move na �ta, dependendo
do símbolo atual e do estado atual da célula (Diverio e Menezes, 2009). 
Tal hipótese traz consigo a a�rmação de que qualquer função matemática intuitivamente
computável pode ser computada por uma Máquina de Turing. A hipótese de Church-Turing vem
trazendo parâmetros para estabelecer que essa máquina é um modelo de computação universal.
No que tange a �ta in�nita, esta representa a memória do computador. Já a cabeça de
leitura/gravação representa o processador e os estados �nitos representam os programas que o
computador pode executar (Diverio e Menezes, 2009). 
Ainda de acordo com a hipótese de Church-Turing, aponta-se que há implicações importantes
para a Teoria da Computação. Nesse sentido, a hipótese estabelece que a Máquina de Turing
corresponde a um modelo de computação completo. Em outros termos, pode-se dizer que
qualquer função que pode ser calculada por um computador pode ser calculada por essa
máquina 
Levanta-se ainda a hipótese de que existeo estabelecimento de um limite teórico para o que é
computável. Sendo assim, se uma função não pode ser calculada por uma Máquina de Turing,
então ela também não pode ser calculada por qualquer outro dispositivo de computação. A
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Máquina de Turing e a hipótese de Church-Turing são conceitos fundamentais da Teoria da
Computação. Eles fornecem uma base para a compreensão de como os computadores
funcionam e o que eles podem calcular. 
Extensões da Máquina de Turing 
Máquinas de Turing não-determinísticas: permitem várias transições para cada estado e
símbolo, tornando-as mais poderosas em termos de expressividade. 
Máquinas de Turing com oráculo: são estendidas com uma caixa que pode responder
instantaneamente a certas perguntas, permitindo a resolução de problemas intratáveis. 
Máquinas de Turing quânticas: exploram a sobreposição de estados quânticos para
cálculos mais e�cientes em algumas situações. 
Esses conceitos são de grande importância, pois são especí�cos para a base essencial no
campo da Teoria da Computação e são fundamentais para compreender o funcionamento
intrínseco dos computadores. Ademais, são capazes de desempenhar um papel crucial na
identi�cação e delimitação de problemas que podem ser resolvidos efetivamente por meio de
processamento computacional, assim como aqueles que, devido à sua complexidade ou
natureza, permanecem insolúveis por computadores. Tais alicerces conceituais são, portanto, a
sustentação não apenas da ciência da computação, mas também torna a melhor compreensão
sobre a temática.
Aprofundando a compreensão sobre a Máquina de Turing
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
A hipótese de Church-Turing, em um sentido particular, é crucial, haja vista que a�rma que
qualquer função computável pode ser calculada por uma Máquina de Turing, o que signi�ca que
a capacidade de computação de todos os sistemas computacionais é essencialmente
equivalente a essa máquina. 
Uma das principais características que podem ser apontadas da Máquina de Turing é que ela é
um modelo abstrato e simpli�cado de um computador que consiste em: uma �ta in�nita dividida
em células, uma cabeça de leitura/escrita e um conjunto de estados �nitos. Já a hipótese de
Church-Turing postula que qualquer função que possa ser intuitivamente calculada pode ser
computada por uma Máquina de Turing ou um equivalente matemático, como o lambda cálculo
de Church. 
Dito isto, vale ressaltar que não há ferramentas práticas diretas associadas a esses conceitos,
pois eles são mais teóricos. No entanto, para explorá-los, é útil estudar Máquinas de Turing em
um ambiente de aprendizado, como um simulador, para visualizar como elas funcionam. 
Modelos formais são essenciais para a análise e o projeto de algoritmos e sistemas
computacionais. Ele fornece uma maneira precisa de representar e compreender a lógica por
trás do processo computacional. O uso de modelos formais ajuda a evitar erros de design e
facilita a comunicação entre os desenvolvedores. 
Um modelo formal é uma representação abstrata de um sistema de computação, geralmente
expressa em termos matemáticos ou lógicos. Descreve de forma precisa e inequívoca os
componentes do sistema, as suas operações e os relacionamentos entre eles. Modelos formais
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
são utilizados em diversas áreas da ciência da computação, incluindo a análise de algoritmos,
sistemas de software e protocolos de comunicação. 
Para criar modelos formais, você pode usar linguagens de especi�cação formais, como Z ou
TLA+ (Temporal Logic of Actions), que permitem especi�car sistemas e propriedades em termos
matemáticos e lógicos. 
As extensões da Máquina de Turing são de extrema relevância em prol da exploração da
computação para além dos limites dessa máquina padrão. Isso é fundamental para entender
melhor a complexidade de algoritmos, assim como para conseguir resolver problemas
especí�cos e considerar cenários computacionais avançados, como a criptogra�a quântica. 
Como já visto, as principais extensões da Máquina de Turing são: Máquinas de Turing Não-
determinísticas, Máquinas de Turing com Oráculo, Máquinas de Turing Quânticas. As extensões
da Máquina de Turing não têm, geralmente, ferramentas especí�cas, entretanto possuem a
compreensão desses conceitos, o que é fundamental para a resolução e�ciente de problemas
considerados complexos em diversas áreas, como a criptogra�a, Teoria da Complexidade
Computacional e algoritmos avançados. 
Esses conceitos e extensões são essenciais para a ciência da computação e têm aplicações em
tudo, desde o desenvolvimento de software até a resolução de problemas complexos em
matemática e ciência da computação teórica. 
A Máquina de Turing
Vamos entender melhor a Máquina de Turing por meio de um exemplo prático? 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
 Você deseja escrever um programa que calcule a sequência de Fibonacci. A suposição de
Church-Turing garante que, independentemente da linguagem de programação ou método de
implementação, o seu algoritmo pode ser considerado equivalente a uma Máquina de Turing. Isto
signi�ca que, embora as implementações possam variar, todos os programas que calculam a
sequência de Fibonacci têm um limite teórico para a sua e�ciência. 
Vejamos outra situação: imagine um engenheiro de software usando a hipótese de Church-Turing
para projetar um algoritmo e avaliar a viabilidade computacional de sua solução. Isso ajuda a
garantir que a solução seja válida e esteja dentro dos limites computacionais do que é
teoricamente possível. A hipótese de Church-Turing a�rma que qualquer função matemática que
seja intuitivamente computável pode ser computada por uma Máquina de Turing, o que signi�ca
que se você puder imaginar um método de cálculo, sendo assim existe uma Máquina de Turing
que pode fazer isso. 
Ressalta-se que a hipótese de Church-Turing é uma ferramenta importante para a Teoria da
Computação, pois permite que os pesquisadores analisem e classi�quem problemas de
computação. 
Agora, vamos dar uma olhada em outra aplicação, desta vez apenas modelos formais, mas
primeiro é importante lembrar que um modelo formal é uma descrição matemática de um
algoritmo ou sistema. Ele usa símbolos e fórmulas para representar o comportamento de um
algoritmo ou sistema. 
Use modelos formais para garantir que algoritmos e sistemas sejam precisos e e�cientes. 
Vamos ilustrar isso melhor com um exemplo. Suponha que você esteja desenvolvendo um novo
algoritmo de classi�cação de dados. Antes de implementá-lo em código, você pode criar um
modelo formal que descreva o algoritmo em pseudocódigo ou em uma linguagem de
especi�cação. Esse modelo formal ajuda a entender como o algoritmo funciona e a analisar a
sua complexidade. Imagine o seguinte cenário: engenheiros de software e cientistas de dados
usam modelos formais para projetar algoritmos e sistemas complexos antes de começar a
codi�car. 
Tenha em mente que você está desenvolvendo um sistema de criptogra�a para proteger dados
con�denciais. Sendo possível utilizar extensões para Máquinas de Turing, como Máquinas de
Turing com oráculos, para implementar algoritmos de criptogra�a fortes. Pro�ssionais de
segurança da informação e criptógrafos usam extensões de Máquina de Turing em sistemas de
criptogra�a e segurança cibernética para manter os dados protegidos contra ameaças. 
Vale lembrar que as extensões da Máquina de Turing são modelos teóricos que adicionam novas
capacidades nela a. Essas funções podem ser usadas para resolver problemas que não podem
ser resolvidos pelas Máquinas de Turing padrão. Essas extensões são usadas em diversas
aplicações, incluindo criptogra�a, computação quântica e inteligência arti�cial.
Videoaula: Máquina de Turing
Este conteúdo é um vídeo!
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Para assistir este conteúdo é necessário que você acesseo AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante! 
Este vídeo resumo é um convite para aprender sobre os principais conceitos fundamentais da
hipótese de Church-Turing; o Modelo Formal; e as extensões da Máquina de Turing. 
Aqui, você verá os principais conceitos de forma clara e concisa sobre o tema mencionado
acima, com exemplos e insights adicionais para facilitar a compreensão. 
Vamos começar! 
Saiba mais
Uma ferramenta que pode ser útil no dia a dia do mercado de trabalho para explorar e aplicar os
conceitos relacionados a Máquinas de Turing, Modelos Formais e Teoria da Computação é o
ambiente de desenvolvimento e simulação conhecido como como Turing Machines (Simulador
de Máquinas de Turing). 
Trata-se de um simulador online que permite criar, visualizar e testar Máquinas de Turing de
forma interativa. Com ele, você pode entender melhor como essas máquinas funcionam,
experimentar com diferentes con�gurações e até mesmo implementar algoritmos simples
usando esse modelo teórico. 
https://turingmachinesimulator.com/
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Referências
DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computabilidade.
V.5 (Livros didáticos informática UFRGS). Porto Alegre: Bookman, 2009. Disponível em:
https://integrada.minhabiblioteca.com.br/books/9788577808311. Acesso: 31 out 2023 
SIPSER, M.; QUEIROZ, R. J. G. B. D.; VIEIRA, N. J. Introdução à teoria da computação. [s.l.] São
Paulo Thomson Learning, 2007. 
Aula 5
Revisão da unidade
Computabilidade e Máquina e Turing
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Olá, estudante! 
Nesta aula, você terá a oportunidade de revisar os conceitos basilares, que são considerados
como fundamentais na computabilidade. Saiba que essa é a área responsável pelo estudo da
base conceitual de programas e máquinas, ou seja, traz para você informações primordiais da
base da computabilidade, para que seja possível fomentar um conhecimento inicial sólido, a �m
de você tenha subsídio para avançar nos próximos assuntos.  
Programas e máquinas são essenciais no campo da ciência da computação e desempenham
papéis cruciais no desenvolvimento de tecnologia, automação e resolução de problemas
complexos. 
Os programas são caracterizados por conjuntos de instruções codi�cadas, as quais são capazes
de direcionar o funcionamento de um computador ou dispositivo eletrônico, vindo ainda a
representar os algoritmos que descrevem a lógica que há por trás de uma tarefa ou de uma
operação especí�ca (Diverio e Menezes, 2009). 
No que tange as máquinas, que são tão cruciais quantos os programas, Divero e Menezes (2009)
entendem que podemos dizer que estas são representadas pelos dispositivos físicos ou
modelos abstratos com capacidade de executar os programas. Observe aqui, aluno, que
programas e máquinas possuem uma ligação, enquanto um está relacionado à execução em
dispositivos propriamente dita, o outro executa programas. 
Um exemplo clássico e fundamental é a Máquina de Turing, uma máquina teórica que está ligada
ao estabelecimento das bases da Teoria da Computação. Nesse sentido, vale ressaltar que as
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
máquinas traduzem os programas em ações concretas, de modo sejam executados cálculos, o
processamento de dados e, também, realizando tarefas diversi�cadas. 
Seguindo em frente, é essencial que você compreenda que quando fala-se da equivalência de
programa e máquina, estamos falando sobre a con�ança, ou seja, da base da con�abilidade e
portabilidade do software. Essa compressão de conceitos é semelhante à revelação consistente
de segredos relacionados aos recursos de um programa e a sua funcionalidade em diferentes
ambientes e plataformas. 
Você pode construir um futuro pro�ssional brilhante pela frente considerando a sua capacidade
de criar softwares com recursos que sejam considerados poderosos e adaptáveis, que possuam
funcionalidade em diversas con�gurações, que são extremamente valorados no mercado da
computação e que podem fazer com que você se torne um pro�ssional mais quali�cado e com
um diferencial considerável dentre os demais que irão competir com você por bons cargos. 
Por outro prisma, pode-se mencionar que a Máquina Norma também desempenha um papel
fundamental na ciência da computação e enquanto é considerada uma referência para a
compreensão e análise de máquinas de registro. As máquinas teóricas, devido à sua natureza
abstrata e simpli�cada, fornecem um padrão consistente pelo qual outras arquiteturas de
máquinas de registro podem ser avaliadas e comparadas. (Diverio e Menezes, 2009). 
As Máquinas de Turing são um conceito fundamental na ciência da computação e
desempenham um papel importante na compreensão da natureza e dos limites da computação.
Essa abstração teórica, proposta por Alan Turing em 1936, é um marco na história da
computação e é a base para todo o campo da Teoria da Computação.
Videoaula: Revisão da unidade
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante!  
No vídeo resumo da unidade será possível ver os principais conceitos que foram estudados por
você nas últimas aulas. Tais conceitos são de extrema importância para a compreensão da
computabilidade, dos programas e das maquinas. Aqui, será apresentada a revisão dos
seguintes conteúdos: equivalência entre programas e máquina; Máquina Norma; e Máquina de
Turing. A partir deste vídeo, você terá a capacidade de realizar a análise e a avaliação de
assuntos no âmbito das premissas da computabilidade. Bons estudos! 
Estudo de caso
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Para contextualizar a sua aprendizagem, você, aluno, resolverá agora um estudo de caso.
Enquanto um pro�ssional da computação, você poderá deparar-se com alguns problemas
computacionais relacionados a programas; função computada; codi�cação de conjuntos
estruturados; de�nição da Máquina Norma; Máquina Norma como máquina universal; hipótese
de Church-Turing; extensões da Máquina de Turing, entre outros. Toda problemática da sua vida
pro�ssional demandará de você tempo e conhecimento técnico e prático, todavia, concentrar
esforços em um problema só é valido quando estes são solucionáveis   
No âmbito da pesquisa é comum a presença de problemas considerados desconhecidos que são
abordados em prol do fomento de novos produtos ou serviços. Frente a isso, aqui você terá a
oportunidade de aplicar tudo o que você aprendeu durante as aulas desta unidade, de modo a
utilizar o conteúdo conceitual basilar que foi tratado anteriormente.  
Considerando todo o conhecimento adquirido até aqui, passaremos ao caso concreto: na
situação hipotética você é um engenheiro de software, contratado pela empresa de tecnologia
Atualizada LTDA. Essa empresa tem como um de seus objetivos a exploração da capacidade de
máquinas registradoras, como, por exemplo a Máquina Norma e as máquinas universais. 
A equipe que você é integrante foi designada para realizar o desenvolvimento de um compilador,
o qual  será responsável por traduzir programas escritos em uma linguagem de�nida para a
Máquina Norma. Tal funcionalidade dará subsídio para que a empresa na qual você trabalha
realize a exploração da noção de equivalência de programas e máquinas, de modo a validar a
hipótese de Church-Turing. 
Diante desse contexto, e considerando que você já sabe o que deve fazer, responda aos
questionamentos a seguir. Inicialmente, descreva as principais características da Máquina
Norma, apontando ainda, de forma comparativa, a Máquina de Turing em termos de capacidade
computacional. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
A seguir, liste e explique os passos necessáriospara desenvolver um compilador que seja capaz
de traduzir programas de uma linguagem de�nida para a Máquina Norma e como  você,
enquanto pro�ssional, lidaria com a de�nição de variáveis, estruturas condicionais e loops nesse
contexto. 
Vale ressaltar que a fase de teste é de extrema importância em qualquer área de conhecimento,
pois é o momento em que será validado de forma prática todos os dados levantados em
pesquisa. Neste sentido, explique como você testaria a equivalência de programas escritos para
a Máquina Norma com programas de uma Máquina de Turing e quais seriam os critérios de
sucesso estabelecidos por você. 
Por �m, você deve indicar se há ou não implicações práticas e teóricas de demonstrar que a
Máquina Norma é uma máquina universal. Caso a reposta seja positiva, parta para a explicação
de quais seriam essas implicações e como essa descoberta poderia impactar o campo da Teoria
da Computação e o desenvolvimento de algoritmos. 
________
Re�ita
Desenvolver um compilador para traduzir programas de uma linguagem de�nida em código, que
possa ser executado em uma Máquina Norma, é um desa�o empolgante que passa por diversos
aspectos da Teoria da Computabilidade. 
A Máquina Norma representa um dos modelos teóricos considerados mais simples e ao mesmo
tempo e�cazes, possuindo um conjunto limitado de instruções, sendo Turing equivalente, ou seja,
capaz de executar qualquer algoritmo que uma Máquina de Turing pode realizar. Isso levanta
questões sobre a natureza da universalidade em máquinas de registro e, por extensão, sobre a
hipótese de Church-Turing, que postula que qualquer função matemática que possa ser
calculada pode ser realizada por uma Máquina de Turing (Diverio e Menezes, 2009). 
O desenvolvimento do compilador é um empreendimento desa�ador, exigindo compreensão de
linguagens de programação, estruturas de dados, algoritmos, conhecimentos sobre a Máquina
Norma e as suas operações básicas podem ser mapeadas a partir de uma linguagem de alto
nível.  
Ao testar a equivalência entre programas escritos para a Máquina Norma e programas de uma
Máquina de Turing, esbarramos em um problema interessante. A teoria diz que essas máquinas
são equivalentes em termos de capacidade computacional, mas a questão prática é como testar
essa equivalência. 
A resposta está relacionada à criação de teste rigorosos e de�nição de critérios de sucesso. O
fato de a Máquina Norma ser uma máquina universal tem repercussões tanto práticas quanto
teóricas, validando a hipótese de Church-Turing em relação a essa máquina especí�ca, indicando
que modelos mais simples de computação ainda podem ser incrivelmente poderosos. 
Videoaula: Resolução do estudo de caso
Este conteúdo é um vídeo!
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
A Máquina Norma consiste em um modelo teórico de máquina registradora, tendo por
característica principal o seu conjunto limitado de instruções, incluindo A:=A+1, A:=A-1 e A=0.
Apesar desse conjunto de instruções limitado, as Máquinas Norma são Turing equivalentes, ou
seja, têm a mesma capacidade computacional que uma Máquina de Turing, assim, ambas são
capazes de solucionar os mesmos tipos de problemas computacionais e realizar cálculos
equivalentes (Diverio e Menezes, 2009). 
Para desenvolver um compilador que traduza programas para a Máquina Norma, você deve
seguir os seguintes passos: 
1. Realizar a análise da linguagem de�nida para identi�car sua sintaxe e semântica.
2. Criar uma representação intermediária que capture o signi�cado dos programas na
linguagem de�nida.
3. Projetar um conjunto de regras de tradução que mapeiem os elementos da linguagem
de�nida para as instruções da Máquina Norma.
4. Implementar um analisador léxico e um analisador sintático para processar o código-fonte
na linguagem de�nida.
5. Utilizar o conjunto de regras de tradução para gerar código na linguagem da Máquina
Norma. 
Você deveria lidar com a de�nição de variáveis usando registradores da Máquina Norma, de
modo a implementar estruturas condicionais e loops usando as instruções disponíveis na
máquina em questão. 
Na fase de teste da equivalência de programas, você deveria executar os mesmos algoritmos em
ambas as máquinas, a Máquina Norma e a Máquina de Turing, usando entradas idênticas. Já em
relação aos critérios de sucesso, estes deveriam ser: 
1. Consideram que ambos os programas produzam a mesma saída para todas as entradas,
isso indicaria a equivalência em termos de resultados.
2. Se ambos os programas terminarem a execução com sucesso ou entrarem em um estado
de loop in�nito para as mesmas entradas, isso seria um demonstrativo de equivalência em
termos de capacidade computacional.
3. Se um programa for capaz de simular o comportamento do outro programa em todas as
situações, isso con�rmaria a equivalência. 
Em relação as implicações práticas e teóricas, demonstrar que a Máquina Norma é uma máquina
universal validaria a hipótese de Church-Turing, a qual sustenta que todos os problemas
solucionáveis algoritmicamente podem ser resolvidos por uma Máquina de Turing ou
equivalentes. Diante disso, haveria a consolidação da Máquina Norma como um modelo
relevante na Teoria da Computação, o que reforçaria toda a sua base teórica.No âmbito prático, a
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
descoberta poderia abrir portas para o desenvolvimento de compiladores e linguagens de
programação que se baseiam na Máquina Norma, o que poderia simpli�car a criação de
algoritmos e�cazes. Para além, poderia ter aplicações em áreas como a simulação de sistemas
computacionais e a análise da complexidade computacional. Em uma visão geral, essa
descoberta poderia promover avanços signi�cativos no campo da Teoria da Computação e no
desenvolvimento de algoritmos mais e�cientes. 
Resumo visual
Veja o resumo visual da unidade:
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Referências
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computabilidade.
V.5 (Livros didáticos informática UFRGS). Porto Alegre: Bookman, 2009. Disponível em:
https://integrada.minhabiblioteca.com.br/books/9788577808311. Acesso: 21 out 2023. 
,
Unidade 2
Teoria da computabilidade: decidibilidade
Aula 1
Decidibilidade
Introdução
https://integrada.minhabiblioteca.com.br/books/9788577808311
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Olá, estudante! 
Nesta aula, a utilização da Máquina de Turing na compreensão de problemas de decisão e na
classi�cação desses problemas em relação à sua solucionabilidade será abordada. Este estudo
é de grande importância para veri�car se um problema é solúvel ou insolúvel diante de uma
perspectiva computacional. 
Os tópicos que serão abordados irão te ajudar a compreender os conceitos subjacentes às
práticas de decidibilidade, à elaboração de algoritmos e à identi�cação de linguagens.  
A distinção entre problemas solúveis e insolúveis é essencial para garantir que os recursos
destinados a projetos de pesquisa e desenvolvimento sejam bem investidos e, também, para
determinar os limites da tecnologia atual.  
Vamos começar? 
Máquina de Turing e solucionabilidade
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Em 1900, o matemático David Hilbert propôs 23 problemas matemáticos em um Congresso
Internacional de Matemática. Na época, não se conhecia nenhuma solução para esses
problemas e, também, não estava claro se era ou não possível resolvê-los. Muitos desses
problemas só foram solucionados (ou provados insolúveis) décadas depois. Ainda hoje, cinco
deles se encontram em aberto e dois são considerados parcialmente resolvidos. Desse modo,
percebe-se a importância de desenvolver estratégias para determinara solucionabilidade de um
problema, com vistas a evitar o gasto de tempo e energia em problemas insolúveis (Diverio e
Menezes, 2009). 
No dia a dia, encontra-se diversos tipos de problemas com as mais variadas estruturas, muitos
deles com respostas complexas que di�cilmente se pode transpor para uma calculadora ou um
computador. A linguagem desses problemas é conhecida como linguagem natural. Linguagens
naturais são comumente utilizadas para se comunicar, o termo se refere às linguagens que os
seres humanos utilizam em seu cotidiano, tais como português, inglês e espanhol.  
Por outro lado, em muitos casos os problemas podem ser representados por meio de uma
estrutura formal, utilizando uma linguagem que pode ser compreendida por um computador, ou
seja, uma linguagem formal. Nesse contexto, entende-se linguagens formais como aquelas que
se baseiam em um modelo matemático ou computacional, tais como: html, PHP, java, entre
outras. 
Computabilidade é um campo de estudo que se preocupa em solucionar problemas de maneira
computacional/automatizada, por meio de linguagens formais e algoritmos. Um problema pode
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
ser resolvido por meio de um algoritmo se ele for um problema de decisão. Problemas de
decisão são aqueles cujas únicas respostas possíveis são “sim” ou “não”, 1 ou 0 em linguagem
binária (Diverio e Menezes, 2009). 
Assim, observa-se que só é possível resolver um problema computacionalmente se ele puder ser
representado como um problema de decisão. Porém, como identi�car se um problema pode ser
transformado em um algoritmo? 
Essa pergunta pode ser respondida por meio da Máquina de Turing. Segundo Sipser, Queiroz e
Vieira (2007), a Máquina de Turing, conhecida também como Máquina Universal, é a
formalização de um algoritmo. Ou seja, provar que existe uma Máquina de Turing que resolva um
determinado problema é o mesmo que provar a existência de um algoritmo que resolva esse
problema.  
Suponha que um determinado problema é um problema de decisão, logo, ele pode ser
representado a partir de uma linguagem formal. As Máquinas de Turing, por sua vez, podem ser
utilizadas para interpretar uma linguagem formal. Desse modo, a Máquina de Turing é capaz de
ler e executar uma sequência de etapas, escritas em linguagem formal, para resolver o problema.
Observe que o tipo de linguagem do problema é o que determinará sua solucionabilidade e
computabilidade. 
A partir do comportamento da Máquina de Turing, pode-se classi�car um problema em quatro
categorias: solucionável/computável, parcialmente solucionável, não solucionável e totalmente
insolúvel. A classe dos problemas não-computáveis é muito maior do que a classe dos
computáveis. Estas serão abordadas em maiores detalhes no próximo bloco desta aula. 
Classes de solucionabilidade
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Um problema de decisão avalia se um elemento pertence ou não a um determinado conjunto.
Por exemplo, o número 5 é um número par? Para responder a essa pergunta é necessário
veri�car se o elemento “5” pertence ao conjunto dos números “pares”.
Uma Máquina de Turing resolve um problema desse tipo. Ao submeter uma determinada entrada
(palavra) à uma Máquina de Turing (M) ela:
I. Reconhece a entrada e a ACEITA, resultando em uma resposta positiva. Na sequência, a
máquina para. Chamaremos esse conjunto de entradas de ACEITA(M).
II. Não reconhece a palavra e a REJEITA, resultando em uma resposta negativa e, depois, a
máquina para. Esse conjunto será chamado de REJEITA(M).
III. Não reconhece a palavra e entra em LOOP, ou seja, a entrada faz com que a máquina �que
processando inde�nidamente. Essas entradas compõem o conjunto LOOP(M).
Representando as relações entre esses conjuntos em um diagrama de Venn-Euler tem-se:
Figura 1| Representação da relação entre os conjuntos de reações possíveis da Máquina de Turing. Fonte: Elaborada pelo
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
autor.
Observe que os conjuntos são disjuntos, ou seja, eles não compartilham nenhum elemento.
A Máquina de Turing aceita apenas linguagens recursivamente enumeráveis, ou seja, aquelas em
que é possível listar/enumerar todas as suas palavras, e pode de�ni-la em termos de si mesma
(Diverio e Menezes, 2009).
Uma linguagem L é recursiva se:
1. ACEITA(M) = Conjunto de palavras L=L.
2. REJEITA(M) = (conjunto de todas as combinações do símbolos de L) - L.
3. LOOP(M) =  
Ou seja, uma linguagem é recursiva quando todas as entradas são aceitas ou rejeitadas, e
nenhuma de suas entradas gera um loop inde�nido (Diverio e Menezes, 2009).Representando
essas relações em um diagrama tem-se:
Figura 2 |Representação da relação entre os conjuntos de linguagens aceitas por uma Máquina de Turing. Fonte: Elaborada
pelo autor.
Observe que as linguagens recursivas são um subconjunto das linguagens recursivamente
enumeráveis.
Um problema é considerado solucionável/decidível se: (i) existir pelo menos uma Máquina de
Turing (ou seja, um algoritmo) que o solucione, e (ii) o problema pode ser expresso em uma
linguagem recursiva (Diverio e Menezes, 2009).
Um problema é dito parcialmente solucionável ou computável se: (i) existir pelo menos uma
Máquina de Turing que o solucione, (ii) ele puder ser representado como uma linguagem
recursivamente enumerável, (iii) alguma instância negativa (entrada que não representa uma
solução para o problema) gera um loop (Diverio e Menezes, 2009).
Problemas não-solucionáveis são aqueles que: (i) existe pelo menos uma Máquina de Turing que
aceite sua linguagem, e ela necessariamente entra em loop com alguma instância negativa
∅
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
(entrada que não resolve o problema), ou (ii) não existe nenhuma Máquina de Turing que aceite a
linguagem usada para representá-lo, ou seja, sua linguagem é não-recursiva (Diverio e Menezes,
2009). Um problema não-solucionável pode ser parcialmente solucionável ou totalmente
insolúvel.
Um problema é considerado totalmente insolúvel ou não computável se não existir nenhuma
Máquina de Turing que reconheça todas as entradas que representam uma solução do problema
(Diverio e Menezes, 2009).Isto é, algumas soluções podem ser rejeitadas pela máquina e sua
linguagem é não-recursivamente enumerável. A �gura abaixo representa a relação entre as
classes de solucionabilidade.
Figura 3 | Representação da relação entre problemas solucionáveis e não-solucionáveis. Fonte: Elaborado pelo autor.
Podemos utilizar, também, a estratégia do Princípio da Redução para determinar a
solucionabilidade. Basicamente esse princípio consiste em determinar a classe de
solucionabilidade de um problema a partir de outro, cuja classe já é conhecida.
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Figura 4 – Princípio da Redução. Fonte: Elaborado pelo autor.
Na Figura 4, podemos observar que A é um caso de B. Desse modo, se B é solucionável, então
pode-se dizer que A também é solucionável. Caso A seja não-solucionável, conclui-se que B
também é não-solucionável.
Relevância do estudo sobre decidibilidade
Diferentemente de um computador material, em que há limitações físicas, a Máquina de Turing
permite a modelagem de um problema, sem gerar gastos ou demandar a construção de aparatos
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
especí�cos, servindo como base para avaliar algoritmos em outros dispositivos (Sipser, Queiroz
e Vieira, 2007).
Nos problemas solucionáveis sempre é possível determinar, por meio de uma Máquina de Turing,
se uma palavra pertence ou não a uma determinada linguagem. Em problemas insolúveis não se
consegue fazer essa distinção, contudo, pode-se, por meio do Princípio da Redução, utilizar um
problema insolúvel para identi�car se problemas similares são ou não computáveis (Diverio e
Menezes, 2009). . Vale ressaltar que problemas insolúveis são tão importantes quanto
problemas solucionáveis. Um exemplo deproblema insolúvel muito relevante é a criação de um
Detector Universal de Loops, também conhecido como Problema da Parada, que será estudado
em maior detalhe na próxima aula.
Para exempli�car os assuntos discutidos nesta aula, considere o seguinte problema P: “Como
saber se um número natural é par ou ímpar?”. P aceita várias respostas que não se limitam a sim
ou não. Logo, é necessário reescrevê-lo de modo que ele se torne um problema de decisão.
Existem várias formas de fazê-lo, cada uma gera algoritmos diferentes.
Optou-se pela seguinte forma: “Dado um , x é ímpar ou par?” (P2). Perceba que P2 só
pode ser respondido com sim ou não, sendo que sim signi�ca que x é ímpar e não indica que x é
par. Ainda é necessário determinar um método para realizar essa veri�cação. Um exemplo é o
algoritmo A apresentado abaixo:
i. leia x
ii. se x>0, diga SIM e pare 
iii. se x=0, diga NÃO e pare 
iv. Execute x-2
v. Volte ao passo i. 
É necessário também investigar se existe uma Máquina de Turing que aceite P2 e A, bem como
veri�car o tipo de linguagem empregada. Seja uma
Máquina de Turing, tem-se que os símbolos representam respectivamente:
 
        o alfabeto dos símbolos de entrada, neste caso 
         o conjunto �nito de estados possíveis da máquina.
       o programa ou função de transição, neste caso .
           o estado início da máquina.
        conjunto de estados �nais.
        V alfabeto auxiliar.
         símbolo especial branco.
       símbolo de início da �ta.
x  ∈ Z 
M   =  (∑,   Q,    ∏,   q0,   F ,   V ,   β,   ⊛)
∑ ∑ = Z
Q
∏ ∏ = A
q0
F
β
⊛ 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Todas as palavras possíveis do alfabeto são conhecidas, uma vez que . Nenhuma
entrada gerará um loop, pois todos as entradas de podem ser processadas usando o
algoritmo .
Assim, entende-se que a linguagem usada é uma linguagem recursiva. Portanto, podemos
concluir que o problema  é solucionável e, pelo Princípio da Redução, que o problema P2 também
é solucionável. Note que para números gigantes a execução do algoritmo seria inviável, mas isso
é irrelevante nesse momento porque essa análise se limita a determinar a solucionabilidade do
problema e não a sua complexidade.
Por �m, vale destacar que o estudo sobre a Máquina de Turing como reconhecedora de
linguagens é essencial para compreender as bases teóricas das linguagens formais,
compiladores, e outros tópicos fundamentais para as linguagens de programação (Diverio e
Menezes, 2009).  Além disso, compreender como estabelecer classes formais de objetos a partir
de suas propriedades, assim como analisar objetos com base em suas similaridades para
classi�cá-los, são habilidades fundamentais para compreender o paradigma da programação
orientada à objetos (Diverio e Menezes, 2009). 
Videoaula: Decidibilidade
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante!
Neste vídeo, entenderemos, de forma lúdica e objetiva, o conceito de solucionabilidade e a sua
importância. Veremos também como uma Máquina de Turing pode ser usada para veri�car se
um problema é solucionável ou não, e como investigar a classe de solucionabilidade de um
problema qualquer a partir de passos simples. Assista-o, pois as explicações contidas nele são
fundamentais para uma melhor compreensão sobre o conteúdo escrito desta aula e podem te
ajudar a esclarecer muitas dúvidas.
Saiba mais
∑ ∑ = Z
∑  
A
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Existem alguns simuladores da Máquina de Turing gratuitos e online que podem ser utilizados
para veri�car o comportamento de uma máquina frente a uma linguagem e um algoritmo
especí�co. Experimente!
PINTO, W. L. O; CARPES, L. M. Simulador de Máquina de Turing, 2016
Referências
https://wellmmer.github.io/tm-web-simulator-unasp/html/index.html
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computabilidade.
v.5 (Livros didáticos informática UFRGS). Porto Alegre: Bookman, 2009. Disponível em:
https://integrada.minhabiblioteca.com.br/books/9788577808311.
SIPSER, M.; QUEIROZ, R. J. G. B. D.; VIEIRA, N. J. Introdução à teoria da computação. [s.l.] São
Paulo: Thomson Learning, 2007.
VIEIRA, N. J. Introdução aos fundamentos da computação: linguagens e máquinas. São Paulo:
Pioneira Thomson Learning, 2006.
Aula 2
Indecidibilidade
Introdução
https://integrada.minhabiblioteca.com.br/books/9788577808311
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Olá, estudante! 
Esta aula abordará os problemas indecidíveis e a sua importância para a Teoria Computacional.
A partir da indecidibilidade pode-se compreender os limites da computação e distinguir
problemas solucionáveis e os não-solucionáveis.   
Os conteúdos discutidos a seguir irão te auxiliar a compreender os tipos de linguagens
relacionadas aos problemas indecidíveis, bem como os métodos para provar a indecidibilidade
desses problemas. De maneira mais especí�ca, será apresentada a Teoria do Reconhecimento e
aceitação de linguagens por Máquinas de Turing, o Problema da Aceitação, o Problema da
Parada e o Método de Diagonalização de Cantor. 
Esses conteúdos são importantes para te ajudar a construir uma base teórica consistente e
necessária para a resolução de diversos problemas ao longo da disciplina. Por meio do problema
de aceitação e o problema de parada, juntamente com o método da diagonalização e
redutibilidade, muitos problemas foram provados indecidíveis e são utilizados para avaliar outros
problemas da ciência da computação. 
Vamos começar? 
Problemas indecidíveis
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Na aula anterior, estudamos como a linguagem utilizada para representar um problema impacta
na sua solucionabilidade. Contudo, linguagens usadas para resolver um problema podem ser
classi�cadas em relação a outros aspectos, tais como a reconhecibilidade e a decidibilidade. 
Uma linguagem é Turing-reconhecível se for recursivamente enumerável, de outra forma ela não
é Turing-reconhecível. Ou seja, uma linguagem é reconhecível se existir uma Máquina de Turing
que a intérprete.  
Dizemos que uma linguagem é decidível se ela for recursiva, de outra forma ela é dita indecidível.
Em outras palavras, uma linguagem decidível possibilita a escrita de um algoritmo de decisão
que nunca entra em loop. 
As classes de solucionabilidade se relacionam com as categorias de decidibilidade e
reconhecibilidade da seguinte forma: 
Todo problema decidível é solucionável. 
Nenhum problema indecidível é totalmente solucionável. 
Problemas indecidíveis podem ser parcialmente solucionáveis, não-solucionáveis ou
totalmente insolucionáveis. 
Problemas baseados em linguagens reconhecíveis podem ser solucionáveis, parcialmente
solucionáveis ou não-solucionáveis. 
Os problemas indecidíveis são aqueles que, apesar de possuírem uma resposta binária, não
podem ser totalmente resolvidos por meio de um algoritmo de decisão, pois pelo menos uma de
suas entradas ocasionará um loop. Muitos dos principais problemas que serviram como base
para diversos resultados computacionais utilizados atualmente são indecidíveis. Abaixo são
listados cinco exemplos: 
1. Determinar se dois algoritmos são equivalentes.
2. Determinar se uma gramática livre-de-contexto é ambígua ou não.
3. Determinar equivalência entre duas gramáticas livres-de-contexto.
4. Problema das palavras em grupo. 
5. Entscheidungsproblem.
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Nesta aula, focaremos em dois problemas insolucionáveis de grande importância. Iniciaremos
com o Problema da Aceitação. “Dada uma Máquina de Turing M e uma string (ou palavra) w, M
aceita w?” 
Esse problema visa criar um algoritmo capaz de veri�car se um segundo algoritmofuncionará ou
não. De maneira intuitiva, a veri�cação de um programa por outro poderia ser algo simples,
entretanto trata-se de um problema que não é solucionável por um computador (Sipser, Queiroz;
eVieira, 2007). 
O Problema da Aceitação está associado a um outro problema indecidível, o Problema da
Parada. “Dadas uma descrição de um programa em uma entrada �nita e uma Máquina de Turing,
decida se o programa termina de rodar ou se ele rodará inde�nidamente.“ 
Em 1936, Alan Turing provou que é impossível desenvolver um algoritmo que resolva o problema
da parada para todas as entradas possíveis (Diverio e Menezes, 2009).  
Em 1873, o matemático Georg Cantor apresentou uma técnica chamada diagonalização que
pode ser utilizada para provar, também, a indecidibilidade do problema da parada. Cantor estava
tentando resolver a seguinte situação: se temos dois conjuntos in�nitos, como podemos
determinar se um é maior do que o outro, ou se eles têm o mesmo tamanho?  
Quando o conjunto é �nito essa questão é facilmente respondida, basta contar os elementos
desses conjuntos e determinar o seu tamanho. Entretanto, é impossível contar todos os
elementos de um conjunto in�nito, desse modo não se pode usar o método de contagem para
determinar o seu tamanho relativo (Sipser; Queiroz; Vieira, 2007) e (Deverioe Menezes, 2009). 
Cantor observou que ao emparelhar os elementos de dois conjuntos �nitos, eles terão o mesmo
tamanho. Esse método compara os tamanhos sem recorrer a contagem e é possível utilizá-lo
para contar conjuntos in�nitos. Nos próximos blocos, ele será apresentado em maiores detalhes.
Problemas de parada e diagonalização
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Um dos primeiros problemas indecidíveis a ser trabalhados foi o Problema de Aceitação.
Formalmente, a pergunta desse problema é: dada uma Máquina de Turing M e uma entrada w, M
aceita w? É possível veri�car essa condição com uma máquina AMT, sendo:
A máquina AMT segue o seguinte procedimento:
1. Simular M sobre a entrada w.
2. Se M em algum momento entrar em estado de aceitação, ACEITE.
3. Se M em algum momento entrar estado de rejeição, REJEITE.
Nesse caso, M e w são parâmetros de AMT. Observe que AMT entra em loop se M entrar em loop
com w, portanto, nesse caso, AMT não decide. Ou seja, AMT é incapaz de reconhecer que M não
está parando com uma entrada w, tornando impossível de computar esse problema.
Apesar desse problema ser indecidível, ele é Turing-reconhecível e pode ser utilizado para
determinar a indecidibilidade de vários outros problemas pelo método da redução. A prova do
Problema de Aceitação é feita utilizando o método da contradição, ou seja, assumimos que se
trata de um problema decidível e, ao �nal, chegamos em um absurdo / uma contradição (Sipser;
Queiroz; Vieira, 2007).
O Problema da Parada busca uma solução para a incapacidade de uma máquina reconhecer se
outra parou ou não, daí a origem do seu nome. Formalmente, a pergunta desse problema é:
AMT = { <M,  w> | M  aceita w}
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
“Dada uma descrição de um programa em uma entrada �nita e uma Máquina de Turing, decida
se o programa termina de rodar ou se ele rodará inde�nidamente”.
Esse problema também é provado por contradição. Considere uma máquina H que decide sobre
a máquina  de�nida anteriormente, ou seja:
Sobre a máquina H é construída uma nova máquina D, sendo:
Como D é de�nida como uma máquina universal que reconhece paradas, então, teoricamente,
ela deve ser capaz de analisar a sua própria parada, sendo assim iremos executá-la sobre si
mesma:
O que gera uma contradição, pois D sempre é obrigada a realizar o oposto do que está
executando, ela é abnegada. Desse modo, conclui-se que o problema de parada é indecidível
(Sipser; Queiroz; Vieira, 2007).
Uma outra forma de interpretar, de forma super�cial, essa demonstração é a seguinte. Imagine
uma Máquina de Turing M sobre uma string . Considere o domínio desse problema como o
conjunto de todas as Máquinas de Turing e todas as entradas  possíveis. Usamos uma segunda
Máquina de Turing P para veri�car se M vai parar ou não para cada entrada . A partir da
simulação da máquina P sobre o comportamento de M para as entradas  podemos veri�car que
o loop é inevitável, provando que esse problema é indecidível.
O Problema de Aceitação trata do reconhecimento de uma linguagem por uma Máquina de
Turing, enquanto o Problema da Parada, como o seu nome sugere, busca veri�car se um
algoritmo está rodando adequadamente ou não. Na realidade, o Problema da Aceitação pode ser
considerado uma redução do Problema da Parada.
A indecidibilidade do Problema da Parada também pode ser provada por meio do Método de
Diagonalização de Cantor, método esse que será explicado na sequência.
A diagonalização no estudo de linguagem
H(<M,w>) = {
ACEITE,  se M  aceita w
REJEITE,  se M  rejeita w
D(<M>) = {
ACEITE,  se M  rejeita <M>
REJEITE,  se M  aceita <M>
D(<D>) = {
ACEITE,  se D rejeita <D>
REJEITE,  se D aceita <D>
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Neste bloco, aprofundaremos a discussão a respeito do Método de Diagonalização de Cantor e a
sua utilização nos problemas de indecidibilidade.  
Cantor estava focado em tentar medir o tamanho de dois conjuntos in�nitos. Basicamente ele
queria responder a seguinte pergunta: “Se temos dois conjuntos in�nitos, como dizer se um é
maior do que o outro ou se eles são de mesmo tamanho?” (Sipser; Queiroz; Vieira, 2007). 
Essa medição não pode ser feita a partir do método de contagem. Contudo, Cantor notou que ao
emparelhar os elementos de dois conjuntos �nitos podemos concluir que eles terão o mesmo
tamanho, observe na Figura 1. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Figura 1| Exemplo do método de emparelhamento de conjuntos. Fonte: Elaborado pelo autor.
Na prática, ele estabeleceu uma correspondência entre todos os elementos do conjunto A e do
conjunto B, de modo que um conjunto mapeia o outro sem nenhuma repetição, ou seja, ele
estabeleceu uma função bijetora de A em B.
Essa correspondência (ou emparelhamento) é uma maneira de veri�car se a quantidade de
elementos no conjunto A é igual à quantidade de elementos no conjunto B, independentemente
se eles são �nitos ou in�nitos.
Por exemplo: o conjunto dos números pares tem o mesmo tamanho do conjunto dos números
naturais? Intuitivamente, é comum negar essa relação, uma vez que os números pares podem
ser reescritos como 2n, sendo , induzindo a supor que esse conjunto teria metade dos
elementos de . Entretanto, ao emparelhar os elementos de cada um dos conjuntos têm-se:
n ∈ N
N
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Figura 2 |Emparelhamento de elementos dos números primos e os números naturais. Fonte: Elaborado pelo autor.
É possível observar que sempre haverá um elemento par associado a um número natural, ou seja,
os conjuntos são enumeráveis e têm a mesma cardinalidade (quantidade de elementos).
Entretanto, ao tentar usar o mesmo método para os números racionais  há
um problema, pois não é possível contar os elementos de maneira sequencial, observe:
Q = m
n
   m,  n ∈ Z
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Figura 3 | Problema do emparelhamento de elementos dos números naturais e racionais. Fonte: Elaborado pelo autor.
Antes mesmo de chegar em um valor de há um número in�nito de elementos do tipo ,
desse modo não é possível emparelhar os conjuntos por esse método. Cantor então propôs a
seguinte solução para esse problema: a construção de uma matriz in�nita  para
enumerar os racionais positivos .
m ≥ 2  1
n
Mij = i
j
Q+
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Figura 4 | Exemplo de matriz de diagonalização para os números racionais. Fonte: Elaborado pelo autor.
Note que desse modo os elementos do conjunto dos números racionais podem ser
emparelhados com os números naturais, seguindoa sequência  e, portanto,
podem ser enumerados. Nesse método, a diagonal destacada em laranja reúne todos os
racionais que equivalem a 1, ela sempre se diferenciará das demais.
Esse método pode ser usado para provar a indecidibilidade do Problema da Parada, basicamente
criamos uma tabela em que cada linha representa um Máquina de Turing  e cada coluna
representa uma string (entrada) Mj que representa o resultado de saída de uma Máquina de
Turing, similar ao que �zemos com a máquina H citada anteriormente. Assim cada célula da
matriz representa a reação (aceita ou rejeita) de uma Máquina de Turing sobre uma entrada
qualquer. Aplicando o método da diagonalização temos:
1
1 ,   2
1 ,   1
2 ,   1
3 ,   …
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Figura 5 |Matriz de diagonalização para o Problema da Parada. Fonte: Elaborado pelo autor.
Se listarmos os resultados da diagonal destacada em laranja, ou seja, a sequência Aceita,
Rejeita, Aceita, veremos que ela é diferente em cada linha e se comporta diferentemente para
cada máquina, isso acontece porque ela corresponde à linguagem usada para de�nir a máquina
D que foi citada anteriormente, ou seja, a Máquina de Turing abnegada, corroborando com a tese
de que esse problema gera uma contradição e é indecidível.
Videoaula: Indecidibilidade
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante!  
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
No vídeo desta aula, estudaremos as linguagens reconhecíveis e decidíveis, e o que isso signi�ca
quando avaliamos a decibilidade de um problema. Além disso, serão apresentados dois
problemas indecidíveis: o Problema de Aceitação e o Problema da Parada. Veremos também o
método de diagonalização de Cantor e a sua relação com esses problemas. Assista ao vídeo
para compreender melhor esses conceitos e métodos, pois eles embasam resultados, práticas e
conceitos fundamentais na área de computação. 
Saiba mais
No site Wikipedia, podemos ler sobre os conceitos do Problema de Parada, tal como o seu
histórico e a sua prova formal. O site apresenta diversas referências complementares para te
ajudar a compreender melhor esse problema. Con�ra! 
Outra leitura muito interessante é sobre o argumento de Diagonalização de Cantor. Neste link
você encontrará uma explicação mais detalhada sobre a prova para incontabilidade de um
conjunto, a ilustração do argumento da diagonalização e a sua relação com outros problemas. 
Referências
https://pt.wikipedia.org/wiki/Problema_da_parada
https://pt.wikipedia.org/wiki/Argumento_de_diagonaliza%C3%A7%C3%A3o_de_Cantor
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computabilidade.
v.5 (Livros didáticos informática UFRGS). Porto Alegre: Bookman, 2009. Disponível em:
https://integrada.minhabiblioteca.com.br/books/9788577808311. Acesso em: 14 ago. 2023. 
SIPSER, M.; QUEIROZ, R. J. G. B.; VIEIRA, N. J. Introdução à teoria da computação. [s.l.] São Paulo:
Thomson Learning, 2007. 
VIEIRA, N. J. Introdução aos fundamentos da computação: linguagens e máquinas. São Paulo:
Pioneira Thomson Learning, 2006. 
Aula 3
Redutibilidade
Introdução
https://integrada.minhabiblioteca.com.br/books/9788577808311
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Olá, estudante!
Você já sabe que a Máquina de Turing pode ser utilizada para estipular os limites da computação
avaliando a decidibilidade, a solucionabilidade e o reconhecimento de determinados problemas e
linguagens. Você também viu como a indecidibilidade de um problema pode ser demonstrada,
por contradição, utilizando o método da diagonalização.
Nesta aula você, verá como o método da redutibilidade pode ser utilizado para avaliar se um
problema é decidível, solucionável ou Turing-reconhecível. Em particular, a discussão desta aula
será focada no método de redução por mapeamento.
A compreensão dessa técnica de redutibilidade irá te proporcionar uma visão mais crítica sobre
problemas, pois você conseguirá identi�car se um problema pode ser reduzido a um outro
problema conhecido ou não e, por meio disso, provar que ele é decidível, reconhecível ou
solucionável de forma mais prática. 
Redutibilidade
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Reduzir um problema a outro signi�ca repensar um problema A, de modo que ele se assemelhe a
um problema B o su�ciente para que a solução de B possa ser aplicada em A. Somos habituados
a reduzir problemas no nosso cotidiano, como, por exemplo:
Se localizar em uma cidade (Problema A) pode ser reduzido ao problema de abrir o
aplicativo de mapa no celular (Problema B).
Mensurar a área de um círculo (Problema A) pode ser reduzido a mensurar o raio de um
círculo (Problema B) que pode ser reduzido a calcular (Problema C).
Provar que um conjunto é contável (Problema A) pode ser reduzido ao problema de
estabelecer uma correspondência biunívoca entre esse conjunto e um conjunto contável
(Problema B).
Perceba que, em todos os exemplos citados, o problema B é um recorte do problema A, cuja
solução também resolve os dois problemas, A e B, no caso. A redutibilidade é uma técnica
importante, porque permite inferir a solução de um problema a partir de outro. Por meio da
redução, pode-se também classi�car se um problema é decidível, solucionável ou se é uma
linguagem é Turing-reconhecível (Sipser, Queiroz e Vieira, 2007).
Em linhas gerais, podemos dizer que reduzir um problema B a um problema A signi�ca que:
A é um “recorte” de B, A é uma simpli�cação de B ou A é “uma parte” de B.
A não pode ser mais fácil e nem mais difícil do que B.
πr2
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
A solução de B também resolve o problema A.
Se A for mais fácil do que B não sentido aplicar a redução, pois seria necessário resolver um
problema mais difícil do que o original. A não pode ser mais difícil do que B, porque não nesse
caso não se tem a certeza de que a solução de B se aplica ao problema A.
Ademais tem-se que, se A é redutível a B então:
Se B é decidível, solucionável ou Turing-reconhecível, então A também será
decidível/solucionável/Turing-reconhecível, pois a solução de B pode ser usada para
resolver A (Sipser, Queiroz e Vieira, 2007).
Se A for indecidível, insolucionável ou não Turing-reconhecível, então B também será
indecidível/insolucionável/não Turing-reconhecível, pois se houvesse uma solução para B
também haveria uma para A, gerando assim uma contradição (Sipser, Queiroz e Vieira,
2007).
Denotaremos a relação de redutibilidade entre A e B como  que deve ser lida “A se reduz a
B”. Pode-se representar da seguinte forma:
Figura 1 | Princípio da Redução. Fonte: Elaborado pelo autor. 
Observe que A ser decidível/solucionável/Turing-reconhecível não implica que B também tenha
essas características. Apesar da solução de B poder ser aplicada em A, a recíproca não é
necessariamente verdadeira, pois B pode ser indecidível.
Analogamente, B ser indecidível/insolucionável/não Turing-reconhecível não implica que A
também tenha essas características. Pode existir uma solução parcial para B que solucione
totalmente A, ou seja, que A seja decidível e B não.
Existem diferentes tipos de redução que se baseiam em diferentes de�nições formais do
conceito de redução. Nesta aula, focaremos na redutibilidade por mapeamento. Reduzir um
A ≤ B
A ≤ B 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
problema A ao problema B utilizando o método de redução por mapeamento, signi�ca
estabelecer uma função computável que converta as instâncias do problema A para instâncias
do problema B. Em outras palavras, usamos uma Máquina de Turing que resolve B para
solucionar também o problema A.
Redução por mapeamento
A noçãobásica de redutibilidade proposta por Alan Turing é útil para compreender e resolvermos
problemas computacionais, entretanto existem outros métodos que podem ser aplicados a essa
teoria, tais como “redução por tabela verdade” e “redução por mapeamento”, a qual iremos
estudar futuramente.
Antes de de�nir a redutibilidade por mapeamento (também conhecida como redutibilidade
muitos-para-um), vamos formalizar a de�nição de redução e de função computável.
Uma redução é uma técnica que converte um problema A em um problema B, de tal forma que a
solução de B também resolve A. Se existe uma redução de A para B, então (i) A não é mais difícil
do que B e (ii) B é no mínimo tão difícil quanto A.
Precisa da fórmula no doc
Demonstração do Problema da Parada usando a redução
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Precisa da fórmula no doc
Videoaula: Redutibilidade
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante!  
No vídeo desta aula, estudaremos o conceito de redutibilidade de modo informal e formal. Além
disso, o método de redução por mapeamento será apresentado e exempli�cado. Veremos,
também, como a redução pode ser utilizada para comprovar a indecidibilidade do Problema da
Parada. Este vídeo vai te ajudar a entender melhor os conceitos e as técnicas apresentadas ao
longo desta aula. Essa compreensão é fundamental, considerando a amplitude da aplicabilidade
do método de redução na computação e fora dela. 
Saiba mais
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
O conteúdo abordado até esta aula lhe proporcionou uma base teórica para resolução de
problemas e, também, uma visão crítica sobre as suas implicações. José Neto discute na Revista
de Computação e Tecnologia da PUC-SP sobre “A teoria da computação e o pro�ssional de
informática”, entenda a importância do domínio desses conteúdos e a sua aplicação.  
Referências
https://revistas.pucsp.br/index.php/ReCET/article/view/1572/1519
https://revistas.pucsp.br/index.php/ReCET/article/view/1572/1519
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
SIPSER, M.; QUEIROZ, R. J. G. B. D.; VIEIRA, N. J. Introdução à teoria da computação. [s.l.] São
Paulo: Thomson Learning, 2007. 
Aula 4
Tópicos avançados em computabilidade
Introdução
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Olá, estudante! 
As Máquinas de Turing (MT) podem ser empregadas para avaliar a reconhecibilidade,
adecidibilidade e a computabilidade de um problema. Nesta aula, um outro atributo interessante
às MTs será explorado: a capacidade de uma máquina reconhecer a si própria e fazer uso de seu
próprio código, ou seja, de autorreplicar.  
Esse atributo é assegurado pelo Teorema da Recursão, um resultado matemático que pode ser
utilizado para avaliar a decidibilidade de teorias matemáticas e para de�nir um outro método de
redutibilidade: a Turing-redutibilidade.  
Para compreendê-lo, você vai, primeiramente, estudar a terminologia utilizada para compreender
a linguagem formal da matemática. Na sequência, você estudará o Teorema da Recursão
propriamente dito e, por �m, verá alguns exemplos de aplicação desse teorema. Lembre-se de
explorar os materiais sugeridos na seção Saiba mais para aprofundar os seus conhecimentos. 
Bons estudos! 
Decidibilidade de teorias lógicas
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Nesta aula, você estudará o Teorema da Recursão, um resultado matemático que tem
implicações na Teoria da Computabilidade. Ele pode ser utilizado para investigar o próprio
raciocínio matemático.  
Na prática, esse teorema pode ser aplicado para avaliar a decidibilidade de Teorias Lógicas,
podendo ser usado para evidenciar que não é possível veri�car se determinada sentença é
verdadeira ou não, ou seja, se ela é indemonstrável (Sipser, Queiroz e Vieira, 2007).  Antes de
estudar esse teorema é importante se familiarizar com a linguagem matemática formal.  
É sabido que um universo é o conjunto de todos os valores possíveis que uma variável pode
assumir (Sipser, Queiroz e Vieira, 2007).  Uma relação é uma regra que estabelece uma
correspondência entre dois elementos de conjuntos diferentes do vazio, usualmente denotada
por R.
Uma operação é um tipo de relação que realiza um procedimento bem-de�nido sobre uma
determinada quantidade de elementos. Um quanti�cador matemático é um símbolo que indica a
quantidade de elementos sobre os quais uma relação pode ser aplicada. A Tabela 1 apresenta
alguns exemplos desses conceitos. 
Tabela 1 Exemplos de variáveis, operações, quanti�cadores e relações. Fonte: Elaborado pelo autor.
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Tabela 1: Exemplos de variáveis, operações, quanti�cadores e relações. Fonte: Elaborado pelo
autor. 
Uma fórmula é uma cadeia bem-de�nida de operações e quanti�cadores, como, por exemplo:
, a qual se lê “relação 1 sobre as variáveis ou relação 2 sobre
as variáveis (Sipser, Queiroz e Vieira, 2007).
A linguagem de um modelo matemático pode ser de�nida como uma coleção de fórmulas
descritas somente com símbolos de relação e um universo. Como exemplo, temos o modelo
, o qual se lê “modelo M de�nido sobre o universo de variáveis U e as
relações de até . 
Vale destacar que o signi�cado de uma variável depende do universo em que ela está inserida.
Destaca-se, também, que quanti�cadores diferentes podem ser associados a diferentes
variáveis. Usualmente, primeiro se apresenta as associações quanti�cador-variável e depois a
fórmula. Uma variável que não está ligada a um quanti�cador é chamada de variável livre. Uma
fórmula sem variáveis livres é chamada uma sentença ou enunciado (Sipser, Queiroz e Vieira,
2007).
Por exemplo, seja a sentença . Considere 
 um modelo de�nido sobre o universo dos números naturais e que seja a relação de (=), então
 pode ser reescrita como . A sentença é
verdadeira, pois para qualquer existe pelo menos um tal que  e
, basta que eles tenham o mesmo valor.
Com esses conhecimentos em vista, podemos estender o conceito de decidibilidade aos
fundamentos teóricos da matemática. A partir disso, pode-se demonstrar que, apesar dos
computadores serem capazes de operar de forma lógica, a pesquisa sobre matemática pura e
aplicada não pode ser mecanizada (Sipser, Queiroz e Vieira, 2007).
Alonzo Church provou que nenhum algoritmo é capaz de decidir, em geral, se as proposições
pertencentes à Teoria dos Números são verdadeiras ou falsas. Em outras palavras, determinar a
veracidade de enunciados dessa área de estudo, usualmente, é um problema indecidível (Sipser,
Queiroz e Vieira, 2007).
Formalmente, tem-se que , um modelo sobre os números naturais e as
operações de soma e produto, é uma teoria indecidível. Em resumo, esse resultado é
demonstrado por contradição reduzindo-o ao Problema da Aceitação via método de
redutibilidade. Existem teorias decidíveis, tais como  um modelo similar ao anterior,
mas agora sem o produto. Uma teoria matemática também pode ser classi�cada como
indemonstrável, caso não seja possível veri�cá-la, mesmo que ela seja verdadeira.
R1(x1,  x2) ∨ R2(x1,  x2) x1 e x2
x1 e x2n
M (U ,  R1,   … ,  Rn)
R1 Rnn
π ∀x1 ∃ x2[R1(x1,  x2) ∨ R1(x2,  x1)] M (N,  R1)
R1
π ∀x1 ∃ x2[R1(x1 =  x2) ∧ R1(x2 =  x1)] π
x1 ∈ N x2 ∈ N x1 = x2
x2 = x1
Th(N ,   +,   ×)
Th(N ,   +)
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Teorema da Recursão
A recursão é um processo de repetição de um objeto com base nele mesmo, ou seja, o objeto é
utilizado para gerar uma réplica de si mesmo. Um exemplo é a projeção da tela do computador
sobre si mesma, conforme ilustrado na Figura 1.
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Figura 1| Recursão usando a tela do computador. Fonte: Elaborado pelo autor.
Uma outra formade produzir uma recursão visual é colocar dois espelhos frente a frente, que
gerará uma imagem similar à da Figura 1. Recursões também são comuns em fractais. Observe
o Tapete de Sierpinski na �gura abaixo.
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Figura 2 | Recursão em um fractal – Tapete de Sierpinski. Fonte: RÖSSEL, J., 2008.
Ademais, a recursão pode ser aplicada em funções matemáticas. Uma função é dita recursiva
quando ela referência a si mesma em sua de�nição. Considere a sequência de Fibonacci que
pode ser de�nida como:
f(n)  =  
                           0,   se n = 0
                           1,   se n = 1
f(n − 1) + f(n − 2),   se n > 1
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Sendo  .
Observe que os dois primeiros resultados de são de�nidos de forma independente,
contudo, a partir de  , a função faz uso de si mesma para gerar os seus resultados,
caracterizando-se como recursiva. Diante desses exemplos, pondere: será que é possível
produzir um programa/MT recursivo?
Considere a possibilidade de produzir uma máquina que elabora outras máquinas, como uma
fábrica automatizada que faça computadores. Considerando que essa máquina é capaz de
processar o projeto dos computadores, infere-se que seu projeto é mais complexo do que o
utilizado como base para os computadores (Sipser, Queiroz e Vieira, 2007).  
Esse raciocínio pode ser estendido a um caso geral: para qualquer máquina A que produz uma
máquina B, A é mais complexa do que B. Suponha que A tente produzir a si mesma, teríamos,
então, que A seria mais complexa do que si mesma. Contudo, A não pode ser diferente de si
própria e, consequentemente, não é possível que A gere uma cópia de A. Essa linha de raciocínio
leva a uma contradição e faz com que o problema de construir uma máquina que se
autorreplicável pareça insolucionável, o que não é verdade (Sipser, Queiroz e Vieira, 2007).
A complexidade da máquina A e da máquina B não é um fator determinante para a produção de
uma máquina autorreplicável. Pode-se produzir uma MT que faz uso de si mesma para gerar
saídas, assim como constrói-se uma função que chama a si mesma. Considere a  de�nida
como: 
Tx = “Dada a entrada w":
1. Apague a �ta.
2. Imprima x e pare”.
Tx recebe um conjunto de caracteres  como entrada, e retorna . Pode-se de�nir uma MT R tal que:
R = “Dada a entrada :
1. Construa 
2.   Imprima em seguida e pare”.
Observe que a máquina R imprime a sua própria descrição a partir de uma composição entre fn e
R, de forma similar a  apresentada anteriormente. Essa possibilidade é assegurada pelo Teorema
da Recursão, o qual é de�nido da seguinte forma:
“Seja T uma MT que computa a função . Existe uma MT R que computa
uma função , na qual para todo .” (Sipser, Queiroz e Vieira,
2007). Em linhas gerais, esse teorema diz que um programa R pode produzir a sua própria
descrição (código) e usá-la, por meio de um programa T, em um cálculo. Ou seja, na prática R
reproduz a operação de T para embutir o seu código em si mesma. Essa relação é ilustrada na
Figura 3.
n ∈ N
f(n) 
n = 2
T⟨R⟩
⟨T⟨R⟩⟩ ⟨R⟩ 
t : ∑ . × ∑ . → ∑ .
r : ∑ . → ∑ .
w,  r(w) = t(⟨R⟩,w)
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Figura 3 | Relação recursiva entre as MT T e R. Fonte: Elaborado pelo autor.
Um vírus de computador é um exemplo de um programa autorreplicável. O Teorema da Recursão
mostra que é possível criar MTs autorreferenciadas que podem ser usadas para demonstrar que
certos problemas são incomputáveis ou indemonstráveis, tal como a conjectura de Goldbach.
Decidibilidade de teorias lógicas
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Um outro resultado importante relacionado à Teoria dos Números é o Primeiro Teorema da
Incompletude de Gödel, o qual a�rma: nenhum sistema consistente de axiomas, cujos teoremas
podem ser listados por um “método e�ciente”, é capaz de comprovar todas as relações
existentes entre números naturais (Sipser, Queiroz e Vieira, 2007).
Em outras palavras, existem relações matemáticas que são indemonstráveis, logo, é impossível
que um computador (“método e�ciente”) veri�que se os enunciados que estabelecem essas
relações são verdadeiros ou falsos.
Nesta aula, não serão apresentados os detalhes da demonstração do Teorema da Incompletude,
contudo, vale mencionar que ele faz uso de duas propriedades:
1. Solidez: se tem uma demonstração , então é verdadeira.
2. Veri�cabilidade: a linguagem é decidível.
Destaca-se que algumas proposições verdadeiras na forma são indemonstráveis.
O Teorema da Recursão pode ser utilizado para exempli�car uma situação em que isso ocorre
(Sipser, Queiroz e Vieira, 2007).
Objetivo: seja a a�rmação em que M é uma MT e A é uma linguagem não
Turing-reconhecível, ou seja, a máquina M rejeita a entrada 0. Mostre que é verdadeira e
indemonstrável.
∅ π ϕ
{ ⟨π,  ϕ⟩ | π é uma prova da afirmação ϕ}
⟨M,w⟩ ∈ A 
ϕE ⟨M, 0⟩ ∈ A 
ϕE
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Demonstração: considere a MT R tal que:
R = “Para qualquer entrada
1. Obtenha e use-o para obter .
2. Para cada prova possível 
                  Teste se  é uma prova de que é verdadeiro.
                  Se sim, então aceite. Caso contrário, continue.”
Note que:
1. Se uma prova  comprova , então R obtém a partir da entrada 0 e a aceita. Isso
implica que é falso, pois a entrada 0 foi reconhecida por R. Temos uma
contradição, porque é verdadeira e falsa.
1. Se é falsa, então R rejeita a entrada 0. Isso implica que é verdadeira,
pois a entrada 0 não é Turing-reconhecível. Temos uma contradição, porque é
verdadeira e falsa.
Desse modo o Teorema da Recursão foi usado para criar uma MT R que rejeita a string 0 e,
também, para evidenciar que se R aceita 0, então R rejeita 0 e vice-versa. Se a a�rmação fosse
falsa, então seria possível comprovar a sua falsidade. Analogamente, se fosse verdadeira seria
possível mostrar sua veracidade. Portanto, o único resultado viável aqui é que a a�rmação é
improvável.
Contudo, sabe-se que  é verdadeira porque se uma MT qualquer rejeita uma string, então essa
string pertence a uma linguagem não Turing-reconhecível. Porém, como exempli�cado, não é
possível provar que R rejeita 0. O que se mostrou aqui é que existem algumas a�rmações
improváveis, mesmo que elas sejam verdadeiras.
Dada uma linguagem B, tem-se que um dispositivo externo capaz de veri�car se uma string
qualquer w pertence ou não a B é um oráculo para B. Uma MT oráculo é uma máquina capaz de
consultar um oráculo. Assim, a notação MB indica uma MT M que é um oráculo para a linguagem
B (Sipser, Queiroz e Vieira, 2007).
Neste momento, não nos interessa compreender como o oráculo determina as suas respostas,
nosso foco aqui é a habilidade que essa máquina  tem de veri�car se uma determinada entrada
pertence a B.
Tem-se que uma linguagem A é Turing-redutível à uma linguagem B se A for decidível em relação
à B. Essa relação é denotada por . Em outras palavras, a linguagem A é interpretada
como um Problema de Decisão por meio de uma MT recursiva em relação a uma linguagem B.
⟨R⟩ ϕE
π = π1,   π2,  . . .
π ϕE
π ϕE ϕE
ϕE = ⟨R, 0⟩ ∈ A
ϕE
ϕE ϕE = ⟨R, 0⟩ ∈ A
ϕE
ϕE
A  ≤ T B
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Videoaula: Tópicos avançados em computabilidade
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante!
Neste vídeo, você aprenderá os conceitos que embasam a linguagem matemática formal e verá a
sua relação com o Teorema da Recursão. Você também compreenderá esse teorema e verá o
seu papel na veri�cação da decidibilidade de Teorias Lógicas. Além disso, entenderá o que é a
Turing-redutibilidade e qual é a sua relevância. Esse material é muito importante para te auxiliar a
consolidar o aprendizado desenvolvido ao longodesta aula.
Bons estudos!
Saiba mais
Nesta aula, você estudou sobre os conceitos fundamentais da linguagem matemática formal e
viu um pouco sobre os operadores matemáticos. Na nossa biblioteca virtual, você encontra o
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
livro Elementos da Matemática de José Bueno. Nele, você poderá estudar esses assuntos de
forma mais aprofundada.
BUENO, J. D. F. Elementos da matemática. Londrina: Editora e Distribuidora Educacional S.A.,
2017
No Wikipedia você pode ler mais sobre Recursividade e a sua aplicação em diversas áreas,
incluindo na computação. O site apresenta uma curadoria de referências complementares
disponíveis no formato de hiperlinks que podem te ajudar a explorar ainda mais esse universo.
Wikipedia. Recursividade.
Referências
SIPSER, M.; QUEIROZ, R. J. G. B. D.; VIEIRA, N. J. Introdução à teoria da computação. [s.l.] São
Paulo: Thomson Learning, 2007.
RÖSSEL, J. 6th Iteration of a Sierpinski carpet. 2008. Disponível em:
https://commons.wikimedia.org/wiki/File:Sierpinski_carpet_6,_white_on_black.svg. Acesso em:
03 set. 2023.
Aula 5
Revisão da unidade
https://www.biblioteca-virtual.com/detalhes/ebook/6087050054aa8872fc616f4f
https://pt.wikipedia.org/wiki/Recursividade
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Decibilidade e Máquinas de Turing
Olá, estudante!
Nesta aula, você revisará os conceitos fundamentais de computabilidade. Essa área estuda a
solução de problemas por meio da aplicação de linguagens formais, aquelas que podem ser
interpretadas por computadores, em problemas de decisão, e aqueles em que as respostas só
podem ser “sim” ou “não”, 1 ou 0 em linguagem binária (Diverio e Menezes, 2009).
No estudo desses tipos de problemas, você utilizará as Máquinas de Turing (MT), que são
máquinas teóricas sem limitações físicas e que podem ser utilizadas para resolver problemas
reais. Ao receber uma entrada, uma MT M pode retornar três tipos de resposta: M pode ACEITAR,
reconhecendo a entrada e parando; REJEITAR, dando uma resposta negativa e parando; ou não
reconhecer a entrada, entrar em LOOP e não parar nunca.
A partir da análise do problema e das possíveis respostas da MT sobre o problema, você pôde
determinar a solucionabilidade, reconhecibilidade e decibilidade desse problema. Um problema
pode ser totalmente solucionável, parcialmente solucionável, não-solucionável ou insolucionável
(Sipser, Queiroz e Vieira, 2007).  A Figura 1 apresenta a relação de classes de solucionabilidade.
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Figura 1 | Representação da relação entre problemas solucionáveis e não-solucionáveis. Fonte: Elaborado pelo autor.
Tão importante quanto saber a resposta para um problema, é saber se há ou não uma solução
para ele, pois isso pode reduzir gastos desnecessários de tempo e recursos caso não haja uma
solução (Diverio e Menezes, 2009).
No tocante a reconhecibilidade, uma linguagem pode ser Turing-reconhecível ou não Turing-
reconhecível. Em relação à decidibilidade, você poderá classi�car os problemas como decidíveis
ou indecidíveis. Problemas indecidíveis são aqueles que não podem ser totalmente resolvidos
por meio de um algoritmo de decisão.
Alguns problemas indecidíveis são muito importantes para a teoria da computação, como, por
exemplo o Problema de Aceitação, cujo enunciado é: “Dada uma Máquina de Turing M e uma
string , M aceita ?”
O objetivo desse algoritmo é veri�car se as entradas de um segundo algoritmo serão aceitas ou
não. Esse problema de aceitação está diretamente relacionado a um outro problema indecidível,
o Problema da Parada, que apresenta o seguinte enunciado: “Dadas uma descrição de um
programa, uma entrada �nita e uma Máquina de Turing, decida se o programa vai parar ou se ele
rodará inde�nidamente.”
Você verá que há algumas maneiras de provar que esse é um problema indecidível, sendo um
dos métodos conhecido como diagonalização de Cantor. A indecidibilidade do Problema da
Parada implica na indecidibilidade de vários outros problemas na área da computação, o que
pode ser demonstrado por meio da redutibilidade.
Você aplicará o princípio da redutibilidade para identi�car se um problema A pode ser reduzido a
B e se é decidível, solucionável ou Turing-reconhecível com base em um problema B relacionado
à A e com classi�cação já conhecida, conforme ilustrado na Figura 2.
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Figura 2 | Princípio da redução. Fonte: Elaborado pelo autor.
Por �m, você verá sobre o Teorema da Recursão, o qual viabiliza a criação de MTs que
referenciam a si mesmas (autorreferenciadas), e podem ser usadas para demonstrar que certos
problemas são incomputáveis e até mesmo que determinadas Teorias Lógicas da Matemática
são indemonstráveis (Sipser, Queiroz e Vieira, 2007).
Videoaula: Revisão da unidade
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante!
No vídeo de resumo desta unidade, você verá os principais conceitos estudados nas últimas
aulas. Esses conceitos são fundamentais para que você possa compreender a computabilidade
de problemas. Neste vídeo, apresenta-se uma revisão e a correção dos seguintes conteúdos:
problemas de decisão, solucionabilidade, decidibilidade, reconhecibilidade, problema da parada,
redutibilidade e recursão. Você será capaz de analisar e avaliar se os problemas da computação
e outras áreas de conhecimento são computáveis, além de se instrumentalizar para
provar/validar a sua análise. Bons estudos!
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Estudo de caso
Como pro�ssional da computação, você poderá se deparar com problemas computacionais
relacionados a diferentes áreas, tais como economia, logística, administração, entre outras.
Todos os problemas demandam alocação de tempo e recursos para serem resolvidos,
entretanto, só faz sentido engajar em um problema desconhecido se ele for solucionável.
No campo da pesquisa e desenvolvimento, é muito comum que os problemas desconhecidos
sejam abordados com o intuito de se produzir um novo produto ou, então, de se ofertar um novo
serviço. Nesse sentido é muito importante que você tenha uma ideia de como trabalhar um
problema aberto de modo que ele se torne um problema fechado e resolvível.
Diante disso, neste estudo de caso, você aplicará os conhecimentos adquiridos nesta unidade
para avaliar a decidibilidade de um problema aberto, interpretando-o e utilizando as ferramentas
estudadas para reescrevê-lo, analisá-lo e inferir se ele é decidível ou não.
Muitos problemas da Ciência da Computação têm relação com problemas da Teoria dos
Números. Em vista disso, o seu objetivo é avaliar a decidibilidade de uma conjectura famosa
desse campo de estudo, a Conjectura de Collatz. Essa conjectura tem esse nome devido ao
matemático alemão que a propôs em 1937, Lothar Collatz (Onody e Sintra, 2021). Ela apresenta o
seguinte enunciado:
Dado número natural n qualquer: se n for par, então divida n por 2: ; se n for ímpar,
multiplique n por 3 e some um (3n + 1).
( n
2
)
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Esse procedimento produz uma sequência numérica que o valor 1 entra em loop e reproduz a
sequência 1, 4, 2, 1, ... inde�nidamente. Supõe-se que esse fenômeno acontece para qualquer 
 tal que .
Até o momento, essa conjectura não foi demonstrada como verdadeira ou falsa para todos os
números naturais maiores do que 1, apesar dos esforços desempenhados no campo da
Matemática. Contudo, sabe-se que algumas conjecturas matemáticas podem ser demonstradas
por meio de provas computacionais ou numéricas (Onody e Sintra, 2021).
Extensos testes computacionais, realizados com diversos números naturais, inclusive valores de
grande magnitude, evidenciaram que esse procedimento sempre produz uma sequênciaque
termina em 1. Contudo, não se sabe se qualquer ponto de partida de fato chegará a 1. Esse
problema também é conhecido como problema 3x + 1 (Sipser, 2012).
Se o Problema da Parada fosse decidível, seria possível veri�car essa conjectura. Suponha que o
Problema da Parada por ser resolvido por uma MT P. Utilize P para descrever uma MT capaz de
veri�car o problema 3x + 1.
Para isso, siga os seguintes passos:
1. Analise o enunciado do problema 3x + 1 e o reescreva na forma de um Problema de
Decisão que possa ser resolvido usando a MT P.
2. Tente escrever o problema 3x + 1  como um algoritmo/MT.
3. Apresente a argumentação que evidencia como a MT criada resolve o problema 3x + 1 .
_____________
Re�ita
Você provavelmente já escreveu programas que não terminaram devido a algum tipo de
problema, causando um loop in�nito. Não seria bom se o compilador de alguma forma
conseguisse avaliar o seu código e avisasse, de antemão, que o seu programa entrará em um
loop?
Acontece que, nos paradigmas atuais, é impossível escrever um programa que consiga decidir se
qualquer programa pode terminar a sua execução em tempo �nito ou não. Esse problema está
relacionado ao problema de analisar a Conjectura de Collatz.
Perceba que a resolução da conjectura não é, necessariamente, complexa, uma vez que as
operações realizadas são simples (soma e produto). Contudo, apesar dos esforços, até hoje não
se conseguiu provar essa questão de forma algébrica.
O esforço de prová-la de forma computacional acontece de forma numérica, ou seja, testando-a
para uma quantidade imensa de números naturais. Esse processo pode levar muito tempo
considerando a in�nidade de números naturais maiores do que 1, além do risco de não gerar
nenhum resultado válido, de forma similar ao que pode acontecer com um programa que entra
em loop.
Por essa razão, a estratégia da redutibilidade é tão interessante para esse problema, pois, por
meio dela, pode-se inferir sobre a decidibilidade do problema sem precisar realizar longos testes,
correndo, assim, o risco de não obter um resultado relevante.
Analise o método utilizado para provar que os outros problemas e conjecturas foram provados
indecidíveis ou decidíveis, e, se precisar, realize pesquisas para compreender melhor esses
n ∈ N n > 1
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
métodos e se baseie nelas para construir o seu método de análise e argumentação.
Videoaula: Resolução do estudo de caso
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Observe que é necessário reescrever o problema como um Problema de Decisão, utilizando uma
linguagem formal. A reescrita pode ser feita de diversas formas. Nesta resolução, optou-se pela
seguinte: A conjectura de Collatz sempre chega em 1 para  sendo ?
 
Esse problema pode ser resolvido utilizando o MT C:
C = “Receba n:
Enquanto n repita:
1. Se n for ímpar: execute 3n + 1;
2. Se n for par: execute  .
Se n = 1 aceite e pare".
 
A MT C vai parar sempre que a sequência terminar com 1, caso contrário continuará executando
eternamente. Para compreender a execução desse algoritmo, considere n = 5, portanto, tem-se
que:
1ª Execução: Entrada n=5, saída n=16.
2ª Execução: Entrada n=16, saída n=8.
3ª Execução: Entrada n=8, saída n=4.
4ª Execução: Entrada n=4, saída n=2.
5ª Execução: Entrada n=2, saída n=1 (ACEITA e PARA).
Na Figura 3, apresenta-se uma representação grá�ca da execução de C para os valores 3, 5 e 13.
Vale ressaltar que o grá�co representa uma relação discreta, contudo, para facilitar a
visualização traçou-se uma reta pontilhada indicando a movimentação dos pontos isolados
n > 1  n ∈ N
n
2
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Figura 3 | Demonstração do comportamento de C para n igual à 3, 5 e 13. Fonte: Elaborado pelo autor.
Observe que todas as entradas chegam a n=1. Para esses valores, é possível obter 1 em poucos
ciclos, contudo, para valores maiores é necessário executar C muitas vezes. Por exemplo, para
n=27 é necessário executar C 100 vezes antes de chegar a 1.
Veri�car a conjectura para uma quantidade de números naturais su�ciente para validá-la é
trabalhoso e levaria muito tempo. Em vista disso, vale revisitar a estratégia utilizada nesse
estudo de caso e reformular o problema de decisão. Veja a seguir: Existe algum para o
qual C nunca para?
Para resolvê-lo, de�ne-se uma máquina V que usa a MT P para veri�car se a máquina C parou ou
não. Seja V:
V = “Receba n:
Enquanto P(C, n) estiver executando, faça:
n= n + 1 
FIM”
Observe que V está programada para testar todos os números naturais em C, por meio de um
processo iterativo que aumenta em uma unidade por ciclo. Tem-se certeza de que V é capaz
disso, porque a máquina hipotética P consegue determinar se uma MT parou ou não.
Executar a entrada n= 1 em V resultará em um dos seguintes resultados:
n ∈ N
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
1. Se V executar inde�nidamente, então pode-se inferir que o problema 3x +1 sempre
terminará em 1 para qualquer número natural. Ou seja, como não há contraexemplo à
conjectura de Collatz, ela deve ser verdadeira.
2. Se V parar, então conclui-se que C encontrou um número que não termina em 1. Logo,
existe um contraexemplo que invalida a generalização da conjectura.
Em suma, V faz uso da máquina P e C para descobrir se existe um contraexemplo que invalide a
generalização da conjectura. Se houver um, então V o encontrará com o tempo. Caso contrário, V
executará para sempre.
Resumo visual
Veja o resumo visual da unidade:
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Mapa Mental - Computabilidade
Referências
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computabilidade.
v.5 (Livros didáticos informática UFRGS). Porto Alegre: Bookman, 2009. Disponível em:
https://integrada.minhabiblioteca.com.br/books/9788577808311. Acesso: 31 out 2023.
SIPSER, M.; QUEIROZ, R. J. G. B.; VIEIRA, N. J. Introdução à teoria da computação. [S.l.] São
Paulo: Thomson Learning, 2007.
SIPSER, M. Introduction to the theory of computation. 3. ed. Boston: Cengage Learning, 2012.
ONODY, R. N.; SINTRA, R. A Conjectura de Collatz: Um problema insolúvel e “perigoso”. In:
Notícias. Universidade de São Paulo - Instituto de Física de São Carlos, 3 set. 2021. Disponível
em: https://www2.ifsc.usp.br/portal-ifsc/a-conjectura-de-collatz/. Acesso em: 6 set. 2023.
,
Unidade 3
Teoria da Complexidade: Análise de Algoritmos
Aula 1
Modelo de computação e e�ciência de algoritmos
Introdução
https://integrada.minhabiblioteca.com.br/books/9788577808311
https://www2.ifsc.usp.br/portal-ifsc/a-conjectura-de-collatz/
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Olá, estudante! 
Nesta aula, vamos explorar a complexidade de tempo e espaço dos algoritmos para entender
como eles usam os recursos temporais e de memória. Usaremos o "Modelo de Contagem
Simpli�cado" para medir a e�ciência dos algoritmos de maneira organizada. Você também
aprenderá mais sobre a complexidade nos casos pior e melhor, o que ajuda a ter uma visão
completa da e�ciência dos algoritmos. 
Usaremos palavras-chave, como "Teoria da Complexidade", para orientar a nossa exploração. No
�nal, você estará apto a analisar a complexidade de algoritmos usando técnicas formais. Os
resultados esperados incluem a compreensão da complexidade, a aplicação do Teorema Mestre,
o uso de notações. como big O, além de entender as diferentes classes de problemas e as suas
classi�cações. Venha conosco nesta jornada emocionante pelo mundo da e�ciência dos
algoritmos e pela Teoria da Complexidade. 
Bons estudos!  
Introdução à Complexidade de Algoritmos
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
A complexidade de algoritmosé um tópico fundamental na ciência da computação que nos
ajuda a compreender o desempenho e a e�ciência de diferentes soluções computacionais. Nesta
jornada de introdução à complexidade de algoritmos, o estudante explorará os principais
conceitos e ferramentas necessários para analisar e avaliar algoritmos de forma técnica e
precisa. 
As, a�nal, o que é a complexidade de algoritmos? Ela refere-se à medida de quão e�ciente um
algoritmo é em termos de tempo e espaço. Em outras palavras, ela nos ajuda a entender quanto
tempo um algoritmo leva para executar uma tarefa e quanto espaço de memória ele consome, à
medida que o tamanho da entrada aumenta. 
A complexidade de tempo de um algoritmo, por exemplo, avalia o número de operações que ele
realiza à medida que o tamanho da entrada aumenta. Isso nos permite quanti�car o tempo que o
algoritmo leva para completar uma tarefa. Para entender melhor, considere um exemplo simples. 
Suponha que você precise encontrar o maior número em uma lista de números não ordenados.
Se você veri�car cada número um por um, o número de operações que você realiza é diretamente
proporcional ao tamanho da lista. Portanto, a complexidade de tempo aqui é linear, representada
como O(n), em que 'n' é o tamanho da lista. 
Já a complexidade de espaço de um algoritmo mede a quantidade de memória que ele utiliza à
medida que a entrada cresce. Imagine que você está ordenando uma lista de números e decide
criar uma lista para armazenar os números ordenados. A complexidade de espaço seria então
proporcional ao tamanho da entrada. 
Para realizar a notação dessas análises de complexidade utilizamos alguns métodos e técnicas.
Entre estes, podemos citar, por exemplo: a notação assintótica. 
Essa notação é utilizada para representar a complexidade de algoritmos. Usamos a notação
assintótica, como O (grande O), Ω (ômega), e Θ (teta). Essas notações nos permitem descrever o
comportamento do algoritmo à medida que o tamanho da entrada se torna muito grande. 
O (grande O) descreve um limite superior para a complexidade. Por exemplo, se a complexidade
de tempo de um algoritmo é O(n), isso signi�ca que o tempo de execução cresce no máximo
linearmente com o tamanho da entrada. 
Ω (ômega) representa um limite inferior. Se a complexidade de tempo de um algoritmo é Ω(n),
isso indica que o tempo de execução cresce, no mínimo, linearmente. 
Θ (teta) é usado quando a complexidade de tempo é limitada tanto superior quanto
inferiormente. Por exemplo, se a complexidade de tempo de um algoritmo é Θ(n), isso signi�ca
que o tempo de execução cresce de forma linear e nenhum pior ou melhor, caso seja observado. 
A complexidade de algoritmos é fundamental para escolher a abordagem certa ao resolver um
problema. Ao analisar a complexidade de tempo e espaço, os estudantes podem identi�car
algoritmos mais e�cientes para diferentes tarefas. 
Por exemplo, ao resolver um problema de pesquisa em uma lista de dados, se você sabe que a
complexidade de tempo de um algoritmo de busca linear é O(n), enquanto a complexidade de
tempo de um algoritmo de busca binária é O (log n), você escolheria o último para conjuntos de
dados grandes, pois é mais e�ciente. 
A complexidade de algoritmos é um pilar fundamental da ciência da computação. Ela nos
permite entender e comparar algoritmos, escolher as melhores soluções para problemas e
desenvolver softwares mais e�ciente.
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Aprofundando nos conceitos de complexidade algorítmica
A análise de complexidade de tempo e espaço em algoritmos é uma habilidade essencial para
programadores e engenheiros de software. Vamos aprofundar o nosso conhecimento, tanto
teoricamente quanto na prática, sobre esses métodos, com um foco especial na aplicação e
desenvolvimento das seguintes notações matemáticas: Big O (O), Ω (ômega) e Θ (teta). Essas
notações são fundamentais para entender e quanti�car o desempenho dos algoritmos em
termos de tempo e espaço. 
Notação Big O 
Uma parte essencial da análise assintótica é a notação Big O (O), que descreve o limite superior
ou o pior caso do desempenho de um algoritmo. Quando dizemos que um algoritmo tem uma
complexidade de O(f(n)), estamos a�rmando que o tempo de execução ou o uso de memória do
algoritmo cresce, no máximo, proporcionalmente a uma função f(n), na qual "n" é o tamanho dos
dados de entrada. 
Para entender melhor, considere o exemplo da busca linear em uma lista não ordenada. A
complexidade de tempo desse algoritmo é O(n), em que "n" é o número de elementos na lista.
Isso signi�ca que, à medida que a lista cresce, o tempo necessário para encontrar um elemento
também aumenta linearmente. 
Notação Ω 
Além do Big O, também temos a notação Ω (ômega), que descreve o limite inferior ou o melhor
caso do desempenho de um algoritmo. Quando dizemos que um algoritmo tem uma
complexidade de Ω(g(n)), estamos a�rmando que o tempo de execução ou o uso de memória do
algoritmo cresce, no mínimo, proporcionalmente a uma função g(n). 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Considere a busca em uma lista ordenada. Nesse caso, a complexidade de tempo é Ω(1), porque,
no melhor caso, podemos encontrar o elemento desejado imediatamente, independentemente do
tamanho da lista. 
Notação Θ 
Finalmente, temos a notação Θ (teta), que é usada quando o limite superior e inferior do
desempenho de um algoritmo é iguais. Isso signi�ca que o algoritmo tem um comportamento
previsível e consistente em todos os casos. 
Um exemplo de algoritmo com complexidade Θ(n log n) é um algoritmo de ordenação por
comparação, como o merge sort ou o quicksort. Esses algoritmos têm um desempenho
previsível e e�ciente, que cresce quase linearmente em relação ao tamanho dos dados de
entrada. 
Além das notações Big O, Ω e Θ, existem outras notações que descrevem diferentes tempos de
execução. São elas: 
O(1): representa um tempo de execução constante, em que o algoritmo leva a mesma
quantidade de tempo, independentemente do tamanho da entrada. É conhecido como "tempo
constante". 
O(log n): descreve um tempo de execução logarítmico, que é mais e�ciente do que o tempo
linear. É comumente visto em algoritmos de busca binária. 
O(n²): refere-se a um tempo de execução quadrático, no qual o tempo aumenta quadrativamente
com o tamanho da entrada. Algoritmos de ordenação como o bubble sort têm essa
complexidade. 
O(n³): indica um tempo de execução cúbico, que é ainda mais lento do que o tempo quadrático. É
comum em algoritmos de multiplicação de matrizes tridimensionais. 
nO(1): esta notação representa um tempo de execução polinomial, em que o tempo de execução
é uma função polinomial do tamanho da entrada. 
2O(n): refere-se a um tempo de execução exponencial, no qual o tempo aumenta
exponencialmente com o tamanho da entrada. Algoritmos com essa complexidade são
geralmente considerados ine�cientes. 
A análise assintótica e as suas notações são ferramentas essenciais para avaliar e comparar
algoritmos. Ao compreender esses conceitos e notações adicionais, os programadores podem
tomar decisões informadas sobre a escolha de algoritmos para resolver problemas especí�cos e
criar softwares mais e�cientes.
Aplicação dos métodos de complexidade de tempo
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
A aplicação e a avaliação prática da complexidade de tempo e espaço em algoritmos é essencial
para tomar decisões informadas na escolha e otimização de soluções computacionais. Vamos
explorar como aplicar e avaliar esses conceitos de forma técnica e prática. 
Complexidade de tempo na prática 
A complexidade de tempo, representada usando notações como O (grande O), é crucial ao
determinar a e�ciência temporal dos algoritmos. Considere o exemplo da busca em uma lista
não ordenada versus uma lista ordenada. 
Para uma lista não ordenada, a busca linear (complexidade O(n)) veri�ca cada elemento, um por
um, até encontrar o desejado. 
Em uma lista ordenada, a busca binária (complexidade O(log n)) dividerepetidamente a lista pela
metade até encontrar o alvo. 
Aqui, a análise de complexidade de tempo orienta a escolha do algoritmo. Para grandes
conjuntos de dados, a busca binária é signi�cativamente mais rápida. 
Complexidade de espaço na prática 
A complexidade de espaço, também representada por notações como O (grande O), é relevante
para a alocação de memória em algoritmos. Imagine a ordenação de uma lista. 
Um algoritmo de ordenação por inserção (complexidade de espaço O(n)) cria uma cópia da lista
ordenada. 
Em contraste, um algoritmo de ordenação in-place como o quicksort (complexidade de espaço
O(log n)) utiliza menos memória. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Aqui, a complexidade de espaço in�uencia na escolha do algoritmo, principalmente em sistemas
com recursos limitados. 
Avaliação prática de complexidade 
Para avaliar a complexidade de tempo e espaço na prática, siga as seguintes etapas: 
1. Identi�que o algoritmo
Primeiro, identi�que o algoritmo que será utilizado para resolver o problema. Entenda como ele
opera e como ele consome recursos de tempo e espaço. 
2. Meça o desempenho
Implemente o algoritmo e meça o seu desempenho com entradas de diferentes tamanhos.
Registre o tempo de execução e o uso de memória. 
3. Analise os resultados
Utilize os dados coletados para calcular a complexidade de tempo e espaço. A complexidade de
tempo é geralmente medida em relação ao tamanho da entrada, enquanto a complexidade de
espaço é a quantidade máxima de memória utilizada. 
4. Compare com outros algoritmos
Compare o desempenho do algoritmo com outras opções. Avalie se ele atende aos requisitos de
e�ciência do projeto. 
5. Otimize, se necessário
Se o algoritmo não atender aos requisitos de desempenho, considere otimizá-lo ou escolher um
algoritmo diferente com melhor complexidade. 
A aplicação e a avaliação prática da complexidade de tempo e espaço são cruciais para a
tomada de decisões na programação. Isso permite escolher os algoritmos mais e�cientes,
economizando tempo e recursos. Lembre-se de que, na ciência da computação, a e�ciência é
fundamental, e a compreensão desses conceitos técnicos é um passo importante para se tornar
um programador mais habilidoso e e�caz. Portanto, continue explorando, experimentando e
aprimorando as suas habilidades nesta jornada emocionante da ciência da computação.
Videoaula: Modelo de computação e e�ciência de algoritmos
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, pessoal! 
No vídeo de hoje, vamos explorar um dos conceitos mais importantes em ciência da
computação: a complexidade de tempo e espaço. A complexidade de tempo e espaço nos
permite avaliar a e�ciência de algoritmos, o que é essencial para projetar e implementar soluções
computacionais e�cazes. 
Saiba mais
Parabéns, agora que chegou até aqui, vamos ao nosso Saiba mais. 
DE CASTRO BARBOSA, M. A.; TOSCANI, L. V.; RIBEIRO, L. Metodologia para o cálculo da
complexidade de algoritmos e o processo de avaliação das equações de complexidade. 
COELHO, H.; FÉLIX, N. Complexidade Assintótica de Programas X Análise Empírica.  
https://www.din.uem.br/sbpo/sbpo2002/pdf/arq0071.pdf
https://www.din.uem.br/sbpo/sbpo2002/pdf/arq0071.pdf
https://ww2.inf.ufg.br/~hebert/disc/aed1/AED1_03_complexidade.pdf
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Referências
CORMEN, T. Desmisti�cando Algoritmos. Grupo GEN, 2013. E-book. ISBN 9788595153929.
Disponível em: https://integrada.minhabiblioteca.com.br/#/books/9788595153929/. Acesso em:
28 ago. 2023. 
DASGUPTA, S.; PAPADIMITRIOU, C.; VAZIRANI, U. Algoritmos. Grupo A, 2009. E-book. ISBN
9788563308535. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788563308535/. Acesso em: 28 ago. 2023. 
DOBRUSHKIN, V. A. Métodos para Análise de Algoritmos. Grupo GEN, 2012. E-book. ISBN 978-85-
216-2989-4. Disponível em: https://integrada.minhabiblioteca.com.br/#/books/978-85-216-2989-
4/. Acesso em: 28 ago. 2023. 
SERPA, M. S.; RODRIGUES, T. N.; ALVES, I. C.; et al. Análise de Algoritmos. Grupo A, 2021. E-book.
ISBN 9786556901862. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9786556901862/. Acesso em: 28 ago. 2023.
Aula 2
Teorema Mestre
Introdução
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Olá, estudante! 
Imagine entrar em um mundo de desa�os computacionais fascinantes. Nesse cenário, três
portas se destacam. São elas: recorrência, método da substituição e Teorema Mestre. 
Na primeira parada, sobre recorrência, você adentrará na essência dos algoritmos recursivos.
Você aprenderá a resolver as equações de recorrência, uma habilidade vital para a análise de
algoritmos que se repetem.  
A próxima etapa revela um método poderoso. Aqui, você colocará em prática Método da
Substituição para provar a complexidade de tempo de algoritmos recursivos. É como montar
peça por peça um quebra-cabeça, substituindo recorrências por estimativas, o que proporciona
uma compreensão precisa da complexidade de tempo desses algoritmos. 
Por último, porém não menos importante, você será apresentado ao Teorema Mestre, uma
ferramenta mágica para analisar algoritmos de dividir e conquistar. Aprenderá, também, a
identi�car quando usar essa ferramenta e a como aplicar as suas fórmulas para calcular a
complexidade de tempo de algoritmos e�cientemente. 
Essas três ferramentas são as chaves para desvendar a complexidade de algoritmos. A sua
jornada começa aqui. Cada tópico oferece uma perspectiva única sobre como entender e
analisar os algoritmos. 
O que é recorrência, método de substituição e Teorema Mestre?
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Os conceitos de recorrência, método da substituição e Teorema Mestre juntos fornecem um
arcabouço teórico poderoso e fundamental que permite aos estudantes e pro�ssionais da
computação entender, analisar e classi�car algoritmos de maneira mais precisa e e�caz. 
Para compreender melhor o conceito de recorrência, precisamos analisar os algoritmos que se
repetem, uma característica comum em programação. Essa porta leva ao conceito de
recorrência, que permite modelar o tempo de execução de algoritmos recursivos por meio de
equações. A compreensão de equações de recorrência capacita o indivíduo a estimar como
esses algoritmos se comportam em vários cenários e com diferentes tamanhos de entrada. É
como desvendar um quebra-cabeça matemático que revela a e�ciência de algoritmos recursivos
em ação. 
Outro conceito importante que precisamos entender, é o método da substituição, que é uma
ferramenta valiosa para determinar a complexidade de tempo de algoritmos recursivos. Ao
aplicar esse método, o estudante ou pro�ssional desmonta a recorrência passo a passo,
substituindo-a por estimativas mais simples. Isso permite uma análise minuciosa que conduz a
uma compreensão precisa da complexidade de tempo desses algoritmos.  
Ao cruzar as etapas acima, você já compreendeu o que é recorrência e como utilizar o método de
substituição. Agora, vou apresentar a você uma ferramenta poderosa e elegante: o Teorema
Mestre. Esse teorema é especialmente útil para algoritmos de dividir e conquistar, um paradigma
de resolução de problemas amplamente utilizado. O Teorema Mestre oferece uma maneira
sistemática de analisar a complexidade de algoritmos que se encaixam nesse paradigma. Ele
permite que o estudante identi�que quando e como aplicar fórmulas especí�cas para determinar
a complexidade de tempo de maneira e�ciente. É como ter uma bússola con�ável para navegar
em terrenos desconhecidos de algoritmos para dividir e conquistar. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Esses três conceitos, recorrência, método da substituição e Teorema Mestre, são como asferramentas de um mestre artesão na computação. Eles capacitam o estudante a entender não
apenas o que os algoritmos fazem, mas também a medir, com precisão, o custo de suas
operações. Como um escultor que esculpe a beleza a partir de um bloco bruto de pedra, o
estudante ou pro�ssional pode aprimorar a sua arte de programação, otimizando algoritmos e
projetando soluções e�cientes. 
À medida que adentramos nesse mundo de análise de algoritmos, lembremo-nos de que esses
conceitos são como ferramentas valiosas em nosso cinto de utilidades. Juntos, eles constituem
uma base sólida para qualquer pessoa que deseja explorar os mistérios e os desa�os do vasto
campo da computação.
Aprofundando nos conceitos de recorrência, método de substituição e
Teorema Mestre
Recorrência em algoritmos é um conceito fundamental na análise de complexidade, que nos
permite avaliar o tempo de execução de algoritmos recursivos. Basicamente, envolve a
modelagem matemática do tempo de execução de um algoritmo em termos do tamanho da
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
entrada. A análise de recorrência é particularmente útil para algoritmos que se resolvem
dividindo o problema em subproblemas menores, como muitos algoritmos de "dividir e
conquistar". 
Para entender o funcionamento da recorrência, considere o exemplo do algoritmo Merge Sort,
amplamente utilizado para ordenar listas. Suponha que queremos determinar a sua
complexidade de tempo. Começamos com a análise de um único passo do algoritmo, que
envolve dividir a lista em duas metades. Digamos que isso custe O(1) (tempo constante). 
Em seguida, consideramos como essas duas metades são classi�cadas recursivamente. Se
denotarmos o tempo para classi�car uma lista de tamanho n como T (n), podemos escrever a
recorrência como T (n)=2T(n/2), porque estamos resolvendo duas metades com tamanho n/2. 
Podemos continuar expandindo essa recorrência, chegando a T(n)=2T(n/2)+O(n), em que  o
termo O (n) representa o custo de combinar as duas metades ordenadas. Agora, temos uma
recorrência completa que descreve o tempo de execução do Merge Sort. 
Identi�cada a recursividade, o método de substituição é uma técnica efetiva. Ela se baseia na
ideia de substituir uma recorrência originalmente complexa por uma estimativa mais simples,
que seja fácil de resolver matematicamente. 
Para compreender como funciona, podemos considerar o algoritmo recursivo, como o Quick
Sort. Suponha que queremos determinar a complexidade de tempo desse algoritmo.
Começamos com uma recorrência que descreve o tempo de execução do Quick Sort em uma
lista de tamanho T (n).  
A ideia-chave do método de substituição é encontrar uma estimativa para T (n) que seja mais
simples de resolver. Por exemplo, podemos tentar supor que T(n)≤a n2 para algum valor de
a que estamos tentando determinar. Em seguida, tentamos provar essa suposição por indução
matemática. Isso envolve demonstrar que, para algum valor base, a suposição T(n)≤a n2 é
verdadeira. Em seguida, assumimos que a suposição é verdadeira para n=k e tentamos provar
que ela também é verdadeira para n=k+1. Se conseguirmos fazer isso, então a suposição é
verdadeira para todos os valores n, e temos uma estimativa válida para a complexidade de
tempo.  
A dedução matemática no método de substituição pode ser desa�adora e requer habilidades de
raciocínio lógico e matemático. No entanto, é uma técnica e�caz para analisar algoritmos
recursivos e determinar a sua complexidade de tempo. 
O Teorema Mestre é uma ferramenta fundamental na análise de complexidade de algoritmos,
especialmente em algoritmos que seguem a abordagem "dividir e conquistar". Ele oferece uma
estrutura matemática para determinar a complexidade de tempo desses algoritmos de maneira
e�ciente. 
O teorema é geralmente utilizado para resolver recorrências do tipo "T(n) = aT(n/b) + f(n)", em
que "a" e "b" são constantes, e "f(n)" descreve o custo de dividir e combinar os subproblemas. O
objetivo é encontrar a complexidade assintótica em termos de notação Big O. 
O Teorema Mestre estabelece três casos principais:
Caso 1: se f(n) é assintoticamente menor do que , ou seja, para
algum , então a complexidade de tempo é dominada pela divisão dos subproblemas, e a
complexidade resultante é  .
nlogb(a) f(n) = O (nlogb(a)− ϵ)
ϵ > 0
T  (n) =  Θ (nlogb(a))
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Caso 2: se f(n) é assintoticamente igual à , ou seja, , então a
complexidade de tempo é in�uenciada igualmente pela divisão dos subproblemas e pelo custo
de combinar as soluções. A complexidade resultante é .
Caso 3: se f(n) é assintoticamente menor do que , ou seja, para
algum  , e se para algum , e para n su�cientemente grande,
então a complexidade de tempo é dominada pelo custo de combinar os subproblemas, e a
complexidade resultante é  .
A dedução matemática desses casos envolve substituir a recorrência original pela estimativa
adequada e, em seguida, veri�car as condições dos casos do teorema. Essa técnica permite
determinar a complexidade de algoritmos para dividir e conquistar de forma e�caz.
O Teorema Mestre é uma ferramenta de excelente aplicabilidade para analisar uma ampla
variedade de algoritmos, incluindo algoritmos de ordenação, como o Merge Sort e o Quick Sort,
bem como os algoritmos de divisão e conquista em geral. Ele simpli�ca a análise de
complexidade e ajuda os programadores a compreenderem o desempenho de seus algoritmos
em diferentes situações.
Aplicando o Teorema Mestre
nlogb(a) f (n) =  Θ (nlogb(a))
T  (n) =  Θ(nlogb(a) . logn)
nlogb(a) f(n) =  Ω (nlogb(a)+ ϵ)
ϵ > 0  af(n/b) ≤ kf(n) K < 1
T (n) = Θ(f(n))
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
A análise de algoritmos recursivos pode ser uma tarefa desa�adora, especialmente quando se
trata de determinar a sua complexidade de tempo. No entanto, o Teorema Mestre, uma
ferramenta muito e�caz na análise de algoritmos para dividir e conquistar, pode simpli�car
consideravelmente esse processo. Neste texto, vamos explorar como aplicar esse teorema em
um algoritmo recursivo, demonstrando o seu uso prático e de que forma ele pode ser valioso.
Entendendo melhor o Teorema Mestre
O Teorema Mestre lida com recorrências do tipo "T(n) = aT(n/b) + f(n)", em que:
"a" representa o número de subproblemas em que o problema original é dividido.
"b" é o fator pelo qual o tamanho do problema é reduzido a cada subdivisão.
"f(n)" denota o custo para combinar as soluções dos subproblemas e resolver o problema
original.
Passos para aplicação
Vamos analisar um exemplo prático para ilustrar o uso do Teorema Mestre. Considere o
algoritmo de divisão e conquista para calcular a potência de um número, cuja recorrência é dada
por:
T(n) = T(n/2) + O(1)
Aqui, "a" é igual a 1 (pois há apenas um subproblema), "b" é igual a 2 (pois o problema é dividido
pela metade), e "f(n)" é O(1) (o custo constante de combinação).
Aplicação passo a passo
Passo 1) Comparação dos termos: primeiro, comparamos "f(n)" com . No nosso exemplo 
, que é assintoticamente menor do que O(1). Portanto, estamos no caso 1 do
Teorema Mestre.
Passo 2) Cálculo da complexidade: no Caso 1, a complexidade é determinada pelo número de
chamadas recursivas. Neste exemplo, há apenas uma chamada recursiva (T(n/2)), então a
complexidade é  .
O Teorema Mestre é frequentemente aplicado em algoritmos que seguem o paradigma dividir e
conquistar, como algoritmos de ordenação (por exemplo, o Merge Sort e o Quick Sort) e
algoritmos de busca binária. Ele nos permite entender como o tempo de execução desses
algoritmos cresce à medida que o tamanho do problema aumenta.
Por exemplo, ao analisar o Merge Sort com o Teorema Mestre, podemos determinar que a sua
complexidade é . Isso é valioso ao escolher algoritmos para grandes conjuntos de
dados, pois sabemos que o Merge Sort tem um desempenho e�ciente. 
Em resumo, o Teorema Mestre é uma ferramenta potente para analisar algoritmos recursivos e
determinar a sua complexidade de tempode maneira e�ciente. Ao compreender os passos para
aplicá-lo e reconhecer como ele pode ser útil, os programadores podem tomar decisões
informadas sobre a escolha e a otimização de algoritmos em seus projetos. Portanto, dominar
essa técnica é um passo importantíssimo na jornada de qualquer estudante de ciência da
computação. 
nlogb(a)
nlog2 1  = n0 = 1
Θ(logn)
Θ(n  logn)
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Videoaula: Teorema Mestre
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante!
Você está pronto para desvendar os segredos da análise de algoritmos recursivos de forma
simples e e�caz? Não perca o nosso vídeo resumo da aula, no qual explicamos, de maneira
prática e envolvente, a aplicar o Teorema Mestre para entender a complexidade de tempo de
algoritmos de dividir e conquistar. Prepare-se para uma jornada de aprendizado empolgante e
aprofunde os seus conhecimentos em computação. Clique agora para assistir e fortaleça as
suas habilidades na análise de algoritmos!
Não perca tempo, assista ao vídeo agora!
Saiba mais
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Você chegou até o nosso saiba mais, então vamos nos aprofundar mais ainda nos nossos
estudos. O aprofundamento do conhecimento se faz necessário para um melhor desempenho na
aplicação dessas técnicas no nosso dia a dia.
Merge Sort na prática:
GeeksforGeeks. Merge Sort.
Animações dos métodos de ordenação:
Toptal. Sorting Algorithms Animations.
Cálculo do Teorema Mestre:
Project Nayuki. Master theorem solver (JavaScript).
Referências
CORMEN, T. Desmisti�cando Algoritmos. Grupo GEN, 2013. E-book. ISBN 9788595153929.
Disponível em: https://integrada.minhabiblioteca.com.br/#/books/9788595153929/ . Acesso em:
28 ago. 2023.
DASGUPTA, S.; PAPADIMITRIOU, C.; VAZIRANI, U. Algoritmos. Grupo A, 2009. E-book. ISBN
9788563308535. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788563308535/ . Acesso em: 28 ago. 2023.
DOBRUSHKIN, V. A. Métodos para Análise de Algoritmos. Grupo GEN, 2012. E-book. ISBN 978-85-
216-2989-4. Disponível em: https://integrada.minhabiblioteca.com.br/#/books/978-85-216-2989-
4/ . Acesso em: 28 ago. 2023.
SERPA, M. S.; RODRIGUES, T. N.; ALVES, I. C.; et al. Análise de Algoritmos. Grupo A, 2021. E-book.
ISBN 9786556901862. Disponível em:
https://www.geeksforgeeks.org/merge-sort/
https://www.toptal.com/developers/sorting-algorithms/
https://www.nayuki.io/page/master-theorem-solver-javascript/
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
https://integrada.minhabiblioteca.com.br/#/books/9786556901862/ . Acesso em: 28 ago. 2023.
Aula 3
Introdução à análise assintótica
Introdução
Olá, estudante! 
Na jornada da ciência da computação, você já se deparou com estes três pilares essenciais:
conceitos fundamentais, notações assintóticas e complexidades de pior e melhor caso. Essas
competências são fundamentais para a análise e otimização de algoritmos. 
Os conceitos fundamentais são a base de tudo. São eles que permitem entender o
funcionamento dos algoritmos, como medir o seu desempenho e avaliar sua e�ciência. Sem
essa compreensão sólida, a construção de algoritmos e�cazes se torna uma tarefa árdua. 
As notações assintóticas, por sua vez, são como uma linguagem universal. Permitem descrever
o comportamento dos algoritmos à medida que os dados de entrada crescem, facilitando a
comparação e a seleção dos melhores algoritmos para tarefas especí�cas. 
Por �m, as complexidades de pior e melhor caso ensinam a considerar cenários extremos. Ao
entender como um algoritmo se comporta em suas situações mais desa�adoras e favoráveis,
podemos projetar soluções que funcionem bem em todas as circunstâncias. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Dominar esses conceitos, métodos e técnicas é o primeiro passo para se tornar um mestre na
análise de algoritmos. Eles são a chave para o desenvolvimento de um software e�ciente e
escalável, preparando o estudante para enfrentar os desa�os da computação de forma con�ante
e habilidosa. 
Vamos começar? 
 Introdução aos fundamentos de algoritmos, notações assintóticas e
complexidades
Sobre os fundamentos de computação, os algoritmos são procedimentos projetados passo a
passo para resolver problemas. Nesta disciplina, você, estudante, vai aprofundar a sua
compreensão sobre a estrutura lógica subjacente aos algoritmos, aprendendo a decompor
problemas complexos em soluções algorítmicas elegantes e e�cazes. Eles exploram estruturas
de dados avançadas, como árvores, grafos e estruturas de dados dinâmicas, e aprendem a
aplicar estratégias de projeto, como divisão e conquista, algoritmos gulosos e programação
dinâmica, para resolver problemas complexos. Com essa base sólida, os vocês estarão
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
preparados para criar algoritmos que atendam aos requisitos de desempenho e e�ciência de
sistemas de computação em larga escala. 
A �m de mensurar e denotar a complexidade dos algoritmos, as notações assintóticas, como a
notação "Big O" (O), desempenham um papel fundamental na análise de algoritmos. O "Big O" é
usado para descrever o limite superior do tempo ou espaço necessário para a execução de um
algoritmo à medida que o tamanho dos dados de entrada aumenta (Serpa, Rodrigues, Alves e et
al, 2021). Por exemplo, um algoritmo com complexidade O(n) tem o seu tempo de execução
aumentando linearmente com o tamanho da entrada. Os estudantes de pós-graduação devem
compreender e aplicar essas notações para avaliar e comparar algoritmos, permitindo a seleção
da abordagem mais e�caz para um determinado problema. Essa capacidade é crucial na
otimização de sistemas e na escolha de algoritmos que atendam às necessidades especí�cas
do projeto. 
Outro aspecto fundamental é a análise das complexidades de melhor e pior Caso. Essa análise
examina o desempenho de um algoritmo em situações ideais (melhor caso) e adversas (pior
caso). É importante entender como um algoritmo se comporta em cenários extremos para tomar
decisões informadas sobre seu uso em aplicações do mundo real (Serpa, Rodrigues, Alves e et
al, 2021). É possível aprender a projetar algoritmos que lidam e�cazmente com situações de pior
caso, garantindo que o sistema funcione de maneira con�ável, independentemente das
condições. 
Esses conceitos não são apenas teóricos, eles têm aplicações profundas na prática. Por
exemplo, ao projetar um mecanismo de busca na web, os estudantes devem considerar a
e�ciência do algoritmo usado para indexar e recuperar páginas da web, garantindo uma resposta
rápida aos usuários. Ou ao criar softwares para processamento de dados em larga escala, como
em análises �nanceiras ou cientí�cas, a escolha dos algoritmos certos pode signi�car a
diferença entre uma análise que leva horas e uma que é concluída em minutos. 
Aprofundando os conhecimentos sobre fundamentos de algoritmos,
notações assintóticas e complexidades
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Um pilar fundamental desse estudo é a análise de algoritmos. Ela consiste na avaliação do
desempenho dessas sequências de instruções lógicas em diversos cenários, tais como os casos
de melhor, médio e pior. A análise do melhor caso ilustra o cenário mais otimista, no qual tudo
funciona perfeitamente, enquanto o caso médio considera condições típicas, levando em conta
entradas aleatórias. Por outro lado, a análise do pior caso investiga o tempo de execução mais
longo, que ocorre quando o algoritmo enfrenta as situações mais desa�adoras (Cormen, 2013). 
Para expressar essas complexidades, empregamos a notação "O" (Big O), que delimita o limite
superior da complexidade temporal. Por exemplo, se a�rmarmos que um algoritmo possui uma
complexidade de O(n), isso signi�ca que seu tempode execução cresce linearmente em relação
ao tamanho da entrada. Essa notação desempenha um papel central na seleção do algoritmo
apropriado para uma tarefa especí�ca, levando em consideração a e�ciência, seja no pior caso
ou no caso médio, conforme as necessidades do projeto. 
Ademais, a notação Big O fornece uma estrutura que auxilia na comparação de algoritmos e
orienta tomadas de decisões informadas durante o desenvolvimento de um software.
Compreender esses conceitos é crucial para estabelecer uma base sólida em ciência da
computação, o que é essencial para se destacar em diversas áreas pro�ssionais. 
Outro elemento vital é a análise do comportamento assintótico dos algoritmos, que permite
compreender como o desempenho de um algoritmo evolui à medida que o tamanho dos dados
de entrada cresce. Esse processo envolve a determinação de limites superiores e inferiores para
a complexidade do algoritmo. A notação Big O atua como uma ferramenta inestimável para
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
descrever esses comportamentos, recorrendo à relação de dominância para representar a
complexidade, (Cormen, 2013). 
Por exemplo, se um algoritmo possui uma complexidade de O(n^2), ele é superado por
algoritmos com complexidade de O(n^3) em termos de desempenho. Além disso, examinamos
casos especí�cos, como a complexidade constante (O(1)), que implica que o algoritmo leva um
tempo constante, independentemente do tamanho da entrada. A complexidade linear (O(n))
indica que o tempo de execução cresce linearmente com o tamanho da entrada, ao passo que a
complexidade logarítmica (O(log n)) sugere, portanto, um crescimento logarítmico. 
A capacidade de realizar essa análise de forma e�ciente é essencial para selecionar o algoritmo
mais adequado para cada situação, garantindo que a e�ciência seja maximizada. Em resumo, o
entendimento do comportamento assintótico e da notação Big O é uma habilidade fundamental
para a tomada de decisões informadas no desenvolvimento de algoritmos e�cientes,
contribuindo signi�cativamente para o sucesso na área da ciência da computação. Portanto,
explorar esses conceitos é uma jornada fundamental rumo à maestria na computação (Serpa,
Rodrigues, Alves e et al, 2021). 
Aplicação dos conceitos de fundamentos de algoritmos, notações
assintóticas e complexidades
Imagine que você está desenvolvendo um software para uma loja online e precisa criar um
algoritmo para calcular o preço total dos produtos no carrinho do cliente. Aqui, você estará
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
lidando com o conceito fundamental de algoritmos, que são sequências de passos bem
de�nidos para realizar uma tarefa.
Agora, suponha que você deseja analisar o desempenho desse algoritmo de cálculo de preço em
relação ao número de itens no carrinho. Usando as notações assintóticas, você pode descrever
como o tempo de execução do algoritmo cresce à medida que o número de itens aumenta.
Se você determinar que o tempo de execução é O(n), isso signi�ca que, à medida que o número
de itens no carrinho aumenta, o tempo de execução do algoritmo aumenta linearmente. Ou seja,
se o algoritmo leva 1 segundo para calcular o preço com 10 itens, levará aproximadamente 2
segundos com 20 itens.
Agora, vamos considerar diferentes cenários para o seu algoritmo de cálculo de preço. No
melhor caso, o carrinho tem apenas um item, e o algoritmo leva pouco tempo para calcular o
preço. Vamos dizer que isso seja O(1), ou seja, o tempo de execução é constante,
independentemente do número de itens.
No entanto, no pior caso, o carrinho tem centenas de itens, e o algoritmo leva mais tempo para
calcular o preço. Nesse caso, podemos dizer que a complexidade é O(n), em que  "n" é o número
de itens. Isso signi�ca que o tempo de execução cresce linearmente com o número de itens no
carrinho.
Exemplo prático e análise
Vamos exempli�car o passo a passo para realizar o cálculo da complexidade de tempo de um
algoritmo usando notação Big O. Vamos considerar um algoritmo simples que busca por um
número em uma lista não ordenada.
Passo 1: escolha do algoritmo
Primeiro, escolhemos o algoritmo que desejamos analisar. Neste exemplo, vamos usar um
algoritmo de busca linear em uma lista não ordenada, conforme Figura 1.
Figura 1 | Algoritmo percorre lista. Fonte: Elaborado pelo autor.
Este é um algoritmo, apresentado na Figura 1, é simples. Ele realiza o percurso em uma lista,
elemento por elemento até encontrar o valor desejado ou chegar ao �nal da lista.
Passo 2: identi�cação do tamanho da entrada
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Em seguida, identi�camos a variável que representa o tamanho da entrada. No caso da busca
linear, o tamanho da entrada é o número de elementos na lista, que podemos representar como
"n", equivalente a entrada do usuário.
Passo 3: contagem de operações básicas
Agora, contamos quantas operações básicas o algoritmo realiza em termos do tamanho da
entrada "n". Operações básicas são aquelas que ocorrem em um passo constante, como
atribuições, comparações e operações matemáticas simples.
No caso da busca linear, o algoritmo realiza uma comparação entre o elemento atual e o alvo em
cada iteração do loop. Portanto, para uma lista de tamanho "n", o algoritmo realiza "n"
comparações no pior caso, pois pode ter que percorrer toda a lista.
Passo 4: expressão da complexidade em notação Big O
Finalmente, expressamos a complexidade do algoritmo em notação Big O com base na
contagem de operações básicas. Para a busca linear, que realiza "n" comparações no pior caso,
podemos dizer que a complexidade de tempo é O(n).
Isso signi�ca que o tempo de execução do algoritmo cresce linearmente em relação ao tamanho
da entrada. Se tivermos uma lista com o dobro de elementos, o algoritmo levará,
aproximadamente, o dobro do tempo para concluir a busca.
Neste exemplo prático, seguimos o passo a passo para calcular a complexidade de tempo de um
algoritmo de busca linear. Identi�camos o tamanho da entrada, contamos as operações básicas
e expressamos a complexidade em notação Big O, que é O(n) neste caso.
Esse processo nos ajuda a compreender como o desempenho do algoritmo é afetado pelo
tamanho da entrada e nos permite tomar decisões informadas ao escolher algoritmos para
diferentes cenários.
Videoaula: Introdução à análise assintótica
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante! 
Convido você a assistir a nossa videoaula de resumo, a qual vai desmisti�car os conceitos
apresentados nesta aula. 
Aqui, você encontrará explicações claras e exemplos práticos que o ajudarão a compreender
como medir o desempenho de algoritmos, avaliar a sua e�ciência e escolher as melhores
soluções para diferentes cenários.  
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Saiba mais
Vamos, agora, aprofundar um pouco mais nos nossos conhecimentos por meio destes links
importantes inseridos no saiba mais. 
Nagoya Foundation. Introdução à complexidade de algoritmos. Medium, 2023.  
Chaimo, L. Aula 2 - Complexidade assintótica. Temas em Ciência da Computação, 2023.  
Referências
https://medium.com/nagoya-foundation/introdu%C3%A7%C3%A3o-%C3%A0-complexidade-de-algoritmos-4a9c237e4ecc
https://www.scielo.br/j/tema/a/G7Ybrdy6w4K6gFYRvSj4tft/?format=html&lang=pt
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
CORMEN, T. Desmisti�cando Algoritmos. Grupo GEN, 2013. E-book. ISBN 9788595153929.
Disponível em: https://integrada.minhabiblioteca.com.br/#/books/9788595153929/ . Acesso em:
28 ago. 2023. 
DASGUPTA, S.; PAPADIMITRIOU, C.; VAZIRANI, U. Algoritmos. Grupo A, 2009. E-book. ISBN
9788563308535. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788563308535/ . Acesso em: 28 ago. 2023. 
DOBRUSHKIN, V. A. Métodos para Análise de Algoritmos.Grupo GEN, 2012. E-book. ISBN 978-85-
216-2989-4. Disponível em: https://integrada.minhabiblioteca.com.br/#/books/978-85-216-2989-
4/ . Acesso em: 28 ago. 2023. 
SERPA, M. S.; RODRIGUES, T. N.; ALVES, IC.; et al. Análise de Algoritmos. Grupo A, 2021. E-book.
ISBN 9786556901862. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9786556901862/ . Acesso em: 28 ago. 2023. 
Aula 4
Classes de problemas
Introdução
https://integrada.minhabiblioteca.com.br/#/books/9788595153929/
https://integrada.minhabiblioteca.com.br/#/books/9788563308535/
https://integrada.minhabiblioteca.com.br/#/books/978-85-216-2989-4/
https://integrada.minhabiblioteca.com.br/#/books/978-85-216-2989-4/
https://integrada.minhabiblioteca.com.br/#/books/9786556901862/
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Olá, estudante! 
Nesta aula sobre o universo das Classes de Problemas Computacionais, nosso foco será as três
principais categorias: P, NP e NP-Completo. Essas classes são essenciais para qualquer
estudante ou entusiasta da ciência da computação e áreas a�ns, pois elas funcionam como
verdadeiros guias em um vasto número de possibilidades para solucionar problemas em
algoritmos e outros desa�os computacionais. 
Compreender as Classes de Problemas é como adquirir um conjunto de ferramentas valiosas
para o mundo da ciência da computação e da solução de problemas complexos. Imagine ter a
capacidade de classi�car problemas com base em sua di�culdade e na e�ciência dos algoritmos
que podem resolvê-los. Essa é a habilidade que as Classes P, NP e NP-Completo oferecem. 
O estudo dessas classes é crucial não apenas do ponto de vista acadêmico, mas também na
prática. Ao compreender as nuances que diferenciam os problemas solucionáveis e�cientemente
(Classe P), os problemas de veri�cação rápida (Classe NP) e os problemas intrinsecamente
difíceis (Classe NP-Completo), o aluno estará mais bem preparado para enfrentar desa�os
complexos na área de ciência da computação. Essa compreensão também auxilia na tomada de
decisões informadas sobre quais problemas podem ou não ser resolvidos de forma e�caz e
e�ciente. 
Nesta empolgante jornada, lembre-se de que o conhecimento adquirido não é meramente
teórico, mas uma valiosa ferramenta que abrirá portas para desa�os e oportunidades
emocionantes. Encare a complexidade como uma oportunidade de crescimento. Dominar as
Classes de Problemas pode ser desa�ador, mas cada obstáculo superado o torna um
pro�ssional mais competente e preparado. O aprendizado desses conceitos é uma aventura
grati�cante que está apenas começando. Vamos explorar juntos as maravilhas das Classes de
Problemas!  
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
 Classes de Problemas: P, NP e NP-Completo
Tudo começou em meados do século XX, quando brilhantes matemáticos e cientistas da
computação começaram a investigar a natureza dos problemas computacionais. Eles queriam
entender até que ponto os computadores podiam ir à questão de resolução de problemas e se
poderiam estabelecer limites claros. Foi aí que as Classes de Problemas, como a Classe P,
entraram em cena. 
A Classe P é como o reino dos problemas solucionáveis e�cientemente. Aqui, você encontrará
problemas que podem ser resolvidos em tempo polinomial, ou seja, no tempo necessário para
encontrar uma solução que cresce de maneira razoável, à medida que o tamanho do problema
aumenta. Um exemplo clássico é o algoritmo de ordenação de listas, que pode ser realizado em
tempo polinomial. Dominar a Classe P é como adquirir a chave para resolver problemas que não
consomem o seu tempo de forma desproporcional. 
Notação: P = {problemas para os quais existe um algoritmo cujo tempo de execução é limitado
por uma função polinomial em relação ao tamanho da entrada do problema} 
A Classe NP é um pouco mais intrigante. Ela engloba problemas cujas soluções podem ser
veri�cadas em tempo polinomial, mesmo que encontrar a solução em si possa ser uma tarefa
complexa. Um exemplo é o problema do caixeiro-viajante, em que encontrar a melhor rota entre
várias cidades é difícil, mas veri�car se uma dada rota é a mais curta é rápido. Essa classe
desa�a a nossa capacidade de veri�car soluções de forma e�ciente. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Notação: NP = {L | L é uma linguagem para a qual, se uma solução candidata for fornecida, ela
pode ser veri�cada em tempo polinomial} 
Aqui, chegamos à fronteira do intratável, a Classe NP-Completo. Problemas dessa classe são tão
difíceis que, se alguém encontrasse um algoritmo e�ciente para resolvê-los, poderia revolucionar
a computação. Eles são, de certa forma, os "mais difíceis" dentro da Classe NP. Resolver um
problema NP-Completo e�cientemente implica em resolver todos os outros problemas NP em
tempo polinomial. Até hoje, ninguém conseguiu encontrar uma solução e�ciente para todos os
problemas NP-Completo conhecidos (Cormen, 2013). 
Notação: NP-Completo = {L | L está em NP e é tão difícil quanto o problema mais difícil em NP} 
Entender as Classes de Problemas é essencial para cientistas da computação, programadores e
engenheiros de software. Seus conceitos fornecem uma estrutura para classi�car problemas,
prever a sua di�culdade e, até mesmo, determinar se os problemas são intratáveis. Por exemplo,
ao projetar algoritmos ou sistemas, é fundamental saber se você está lidando com um problema
em P, NP ou NP-Completo, pois isso afetará diretamente a e�ciência de sua solução. 
As Classes de Problemas nos permitem compreender a complexidade dos problemas que
encontramos em nossa jornada tecnológica. Ao entender esses conceitos, você estará equipado
para enfrentar desa�os computacionais com con�ança, identi�car problemas que podem ser
resolvidos e�cientemente e, também, reconhecer aqueles que ainda desa�am as maiores
mentes da computação.
Complexidade de problemas computacionais: otimização, busca e decisão
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Imagine determinada situação em que você precise ordenar uma lista de números em ordem
crescente. Um exemplo clássico de algoritmo para essa tarefa é o "Quick Sort". Embora o tempo
de execução do "Quick Sort" seja proporcional ao quadrado do número de elementos na lista em
seu pior caso, ele ainda é considerado e�ciente, pois o seu crescimento é polinomial. Em outras
palavras, o tempo de execução aumenta de maneira razoável à medida que o tamanho da
entrada cresce. 
A Classe P abarca todos os problemas de decisão que podem ser resolvidos em tempo
polinomial por uma Máquina de Turing determinística. Isso signi�ca que problemas como
ordenação, que realizam busca em uma lista ordenada e até mesmo efetuam operações
matemáticas complexas podem ser solucionados de forma e�caz (Cormen, 2013). 
Agora, no caso das classes NP, podemos nos colocar diante de um problema que envolve
encontrar um subconjunto de números em uma lista cuja soma seja igual a um valor especí�co,
como 42, por exemplo. Encontrar esse subconjunto pode ser um desa�o, pois exigiria testar
várias combinações possíveis. No entanto, se alguém lhe apresentar um subconjunto candidato,
você pode veri�car facilmente se a soma é realmente 42. Esse é um exemplo da Classe NP. 
A Classe NP engloba problemas que, se uma solução candidata for fornecida, eles podem ser
veri�cados em tempo polinomial. Embora encontrar a solução possa ser difícil, veri�car se uma
solução é correta é relativamente simples. Problemas como o "Problema da Mochila", no qual 
você precisa escolher itens com valores diferentes para maximizar o valor total, respeitando um
limite de peso, são exemplos de problemas pertencentes à NP (Cormen, 2013).  
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Já a Classe NP-Completo é a mais desa�adora das três. Ela abrange problemas que são tão
difíceis quanto o problema mais difícil em NP. Um exemplo clássico de um problema NP-
Completo é o "Problema do Caixeiro Viajante", no qual um viajante deve visitarvárias cidades
apenas uma vez e retornar ao seu local de origem, minimizando a distância total percorrida no
percurso (Cormen, 2013). 
O que torna os problemas NP-Completo tão intrigantes é que, se você conseguir encontrar um
algoritmo e�ciente para resolver um desses problemas, será capaz de resolver e�cazmente
todos as situações em NP. A questão fundamental que permanece em aberto na ciência da
computação é se existe um algoritmo e�ciente para resolver problemas NP-Completo. Essa é
uma das questões mais notáveis e desa�adoras da matemática e da computação. 
Podemos ir ainda mais fundo conceitualmente. Considere o problema do "Isomor�smo de
Grafos", que se refere à questão de determinar se dois grafos são isomorfos, ou seja, se eles
podem ser transformados um no outro apenas renomeando seus vértices. Enquanto o problema
do "Isomor�smo de Subgrafos" é NP-Completo, o problema do "Isomor�smo de Grafos" é
suspeito de não estar em P nem ser NP-Completo, embora esteja claramente em NP. 
As classes P, NP e NP-Completo são de suma importância para cientistas da computação. Elas
nos auxiliam a categorizar a complexidade de problemas e nos lançam em busca de respostas
para questões fundamentais sobre o poder computacional. À medida que exploramos mais
profundamente esse campo, é importante lembrar que essas classes não são meras abstrações
teóricas; elas têm aplicações práticas em todas as áreas da computação e são ferramentas
essenciais para avaliar a complexidade de algoritmos e problemas do mundo real. Ao dominar
esses conceitos, você estará mais bem preparado para enfrentar desa�os computacionais e
explorar novas fronteiras na ciência da computação
Na prática: problemas P, NP e NP-Completo
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Para entender a complexidade dos problemas computacionais, é fundamental começar com
exemplos práticos que representem diferentes categorias. Abaixo, apresentaremos três tipos de
problemas, discutindo as suas teorias subjacentes e fornecendo exemplos de código em
Python. 
Entender se um algoritmo é da ordem P (complexidade polinomial) é uma questão fundamental
na teoria da computação. Algoritmos da ordem P são aqueles cujo tempo de execução cresce de
forma polinomial com o tamanho da entrada. Para determinar se um algoritmo é da ordem P,
você deve analisar o tempo de execução em relação ao tamanho da entrada e veri�car se ele é
limitado por um polinômio. 
Vou fornecer um exemplo de um algoritmo simples em Python e explicar por que ele é da ordem
P. 
Exemplo de algoritmo: soma de números 
def soma_até_n(N): 
 soma = 0 
 for i in range(1, N + 1): 
 soma += i 
 return soma 
Comentário do código linha a linha: 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
def soma_ate_n(N):: define uma função chamada “soma_até_n”, a qual recebe um
argumento N. 
soma = 0: inicializa uma variável soma com o valor zero. 
for i in range(1, N + 1): inicia um loop que varre todos os números de 1 até N (inclusive). 
soma += i: adiciona o valor de i à variável soma a cada iteração. 
return soma: retorna o valor final da soma. 
Esse algoritmo é da ordem P, porque o seu tempo de execução é limitado por um polinômio em
relação ao tamanho da entrada N. Mais especi�camente, o loop for executa exatamente N
iterações, e dentro de cada iteração, há uma operação de adição. Portanto, o tempo de execução
é proporcional a N. 
A complexidade temporal desse algoritmo é O(N), o que signi�ca que o tempo de execução
cresce linearmente com o tamanho da entrada. Isso é um exemplo de complexidade polinomial,
pois o tempo de execução é limitado por um polinômio de grau 1 (no caso, O(N)). Além disso, o
algoritmo não possui loops aninhados ou recursão que aumentariam a complexidade para além
de um polinômio. 
Um exemplo clássico de um problema NP (Nondeterministic Polynomial) é o Problema da
Mochila 0/1 (0/1 Knapsack Problem). Nele, dado um conjunto de itens com pesos e valores, e
uma capacidade máxima da mochila, o objetivo é determinar a seleção de itens que maximiza o
valor total, respeitando a capacidade da mochila. 
Aqui está um exemplo de um algoritmo para o Problema da Mochila 0/1 em Python, e explicarei
por que ele pertence à classe NP. 
def knapsack_01(values, weights, capacity): 
 n = len(values) 
 # Inicializa uma matriz para armazenar os resultados intermediários 
 dp = [[0] * (capacity + 1) for _ in range(n + 1)] 
 # Preenche a matriz dp usando programação dinâmica 
 for i in range(1, n + 1): 
 for w in range(capacity + 1): 
 if weights[i - 1] <= w: 
 dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]) 
 else: 
 dp[i][w] = dp[i - 1][w] 
 # Reconstrói a solução selecionando os itens 
 selected_items = [] 
 w = capacity 
 for i in range(n, 0, -1): 
 if dp[i][w] != dp[i - 1][w]: 
 selected_items.append(i - 1) 
 w -= weights[i - 1] 
 return dp[n][capacity], selected_items 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Comentário do código linha a linha: 
def knapsack_01(values, weights, capacity): define uma função knapsack_01, que recebe listas
de valores, pesos e a capacidade da mochila. 
n = len(values): calcula o número de itens. 
dp = [[0] * (capacity + 1) for _ in range(n + 1)]: inicializa uma matriz dp para armazenar os
resultados intermediários. dp[i][w] representará o valor máximo possível com i itens e uma
capacidade w. 
O código usa programação dinâmica para preencher a matriz dp, calculando o valor
máximo possível com diferentes combinações de itens. 
A matriz dp é preenchida iterativamente usando dois loops for. 
A última parte do código reconstrói a seleção dos itens que maximizam o valor, seguindo as
entradas na matriz dp. 
O Problema da Mochila 0/1 é um problema clássico de otimização combinatória. A
complexidade de tempo desse algoritmo é da ordem de O(n * capacity), em que n é o número de
itens e capacity é a capacidade da mochila. Portanto, o tempo de execução desse algoritmo é
limitado por um polinômio em relação ao tamanho da entrada. 
No entanto, o Problema da Mochila 0/1 é considerado um problema NP, porque a veri�cação de
uma solução (ou seja, veri�car se uma seleção de itens dada é válida e maximiza o valor dentro
da capacidade) pode ser feita em tempo polinomial. A veri�cação envolve apenas somar os
valores e os pesos dos itens selecionados, o que pode ser feito em tempo O(n). Portanto, se
alguém fornecer uma solução candidata, é possível veri�car em tempo polinomial se essa
solução é válida e e se atinge o valor máximo. 
Assim, o Problema da Mochila 0/1 é classi�cado como NP devido à sua capacidade de
veri�cação em tempo polinomial, embora o algoritmo de resolução também seja e�ciente em
termos de tempo. Isso o coloca na classe de problemas NP. 
Um problema famoso que é NP-Completo é o Problema do Caixeiro Viajante (Traveling Salesman
Problem, TSP). Nele, dado um conjunto de cidades e as distâncias entre cada par destas, o
objetivo é encontrar o caminho mais curto que visita cada cidade exatamente uma vez e retorna
ao local de origem. O TSP é conhecido por ser NP-Completo, o que signi�ca que não se conhece
um algoritmo e�ciente que resolva todas as instâncias do problema em tempo polinomial. 
Aqui está um exemplo simpli�cado do TSP em Python usando a abordagem de força bruta, que
não é e�ciente para instâncias grandes, mas ilustra a natureza exponencial do problema: 
import itertools 
def tsp_bruteforce(graph): 
 num_cities = len(graph) 
 cities = list(range(num_cities)) 
 shortest_path = None 
 shortest_distance = float('inf') 
 for path in itertools.permutations(cities): 
 distance = 0 
 for i in range(num_cities - 1): 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
 distance += graph[path[i]][path[i + 1]] 
 distance += graph[path[-1]][path[0]] # Volta à cidade de origemif distance < shortest_distance: 
 shortest_distance = distance 
 shortest_path = path 
 return shortest_path, shortest_distance 
# Exemplo de uso 
graph = [ 
 [0, 29, 20, 21], 
 [29, 0, 15, 17], 
 [20, 15, 0, 28], 
 [21, 17, 28, 0] 
] 
shortest_path, shortest_distance = tsp_bruteforce(graph) 
print ("Caminho mais curto:", shortest_path) 
print("Distância total:", shortest_distance) 
Comentário do código linha a linha: 
import itertools: Importa a biblioteca itertools para gerar todas as permutações de cidades. 
 
def tsp_bruteforce(graph): define uma função tsp_bruteforce que recebe uma matriz graph
representando as distâncias entre as cidades. 
num_cities = len(graph): calcula o número de cidades no grafo. 
 
cities = list(range(num_cities)): cria uma lista de cidades representadas por números inteiros. 
 
O código usa uma abordagem de força bruta para gerar todas as permutações possíveis
das cidades e calcular a distância total de cada permutação. 
 
A variável shortest_path armazena o caminho mais curto encontrado, e a shortest_distance
armazena a distância total desse caminho. 
 
Ao final, a função retorna o caminho mais curto e a distância total. 
 
Um exemplo de uso é fornecido usando uma matriz graph que representa as distâncias
entre as cidades. 
O Problema do Caixeiro Viajante (TSP) é considerado NP-Completo devido à sua complexidade
computacional. Existem várias maneiras de provar que o TSP é NP-Completo, mas uma
abordagem comum é mostrar que ele é pelo menos tão difícil quanto outro problema NP-
Completo, como, por exemplo, o Problema do Circuito Hamiltoniano. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
A classe NP-Completo é composta por problemas para os quais é preciso achar uma solução em
tempo polinomial para uma instância. Portanto, você pode achar uma solução em tempo
polinomial para todos os problemas na classe NP, tornando-os polinomialmente equivalentes. 
Esses algoritmos representam diferentes classes de complexidade computacional. O Problema
da Mochila é e�cientemente solucionável (P) e o Problema do Caixeiro Viajante é intratável (NP),
o que o coloca entre os problemas mais difíceis e intrigantes da ciência da computação. A
classi�cação desses problemas é fundamental para entender a sua di�culdade e aplicar
estratégias apropriadas para resolvê-los.
Videoaula: Classes de problemas
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, pessoal! 
No vídeo de hoje, vamos abordar um dos conceitos mais importantes em ciência da
computação: as Classes de Problema, P, NP e NP-Completo.  
Então, prepare-se para aprender sobre esses conceitos extremamente signi�cativos para todos
nós da área de computação! 
Saiba mais
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Parabéns, agora que você chegou até aqui, vamos ao nosso Saiba mais. 
Plataforma de exercícios de P, NP e NP-Completo 
Artigos  
COELHO, E. M. M. et al. O Problema do Número Clique Orientado Absoluto é NP-completo. In:
Anais do VII Encontro de Teoria da Computação. SBC, 2022. p. 13-16.  
COSTA, D. R. P.; DOS SANTOS, V. F.; MOURA, P. F.S. Problemas de Particionamento de Grafos em
Árvores Monocromáticas. In: Anais do VII Encontro de Teoria da Computação. SBC, 2022. p. 113-
116.  
ALVES, M. S. D.. Coloração de Grafos (r,l). 2023.  
Referências
https://www.beecrowd.com.br/judge/pt/login
https://sol.sbc.org.br/index.php/etc/article/view/20647
https://sol.sbc.org.br/index.php/etc/article/view/20652
https://sol.sbc.org.br/index.php/etc/article/view/20652
https://app.uff.br/riuff/handle/1/30595
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
CORMEN, T. Desmisti�cando Algoritmos. Grupo GEN, 2013. E-book. ISBN 9788595153929.
Disponível em: https://integrada.minhabiblioteca.com.br/#/books/9788595153929/ . Acesso em:
28 ago. 2023. 
DASGUPTA, S.; PAPADIMITRIOU, C.; VAZIRANI, U. Algoritmos. Grupo A, 2009. E-book. ISBN
9788563308535. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788563308535/ . Acesso em: 28 ago. 2023. 
DOBRUSHKIN, V. A. Métodos para Análise de Algoritmos. Grupo GEN, 2012. E-book. ISBN 978-85-
216-2989-4. Disponível em: https://integrada.minhabiblioteca.com.br/#/books/978-85-216-2989-
4/ . Acesso em: 28 ago. 2023. 
SERPA, M. S.; RODRIGUES, T. N.; ALVES, I. C.; et al. Análise de Algoritmos. Grupo A, 2021. E-book.
ISBN 9786556901862. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9786556901862/ . Acesso em: 28 ago. 2023. 
Aula 5
Revisão da unidade
 Revisando a disciplina
https://integrada.minhabiblioteca.com.br/#/books/9788595153929/
https://integrada.minhabiblioteca.com.br/#/books/9788563308535/
https://integrada.minhabiblioteca.com.br/#/books/978-85-216-2989-4/
https://integrada.minhabiblioteca.com.br/#/books/978-85-216-2989-4/
https://integrada.minhabiblioteca.com.br/#/books/9786556901862/
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Olá, caro estudante. Nesta jornada de aprendizado, você desenvolveu habilidades fundamentais
no campo da ciência da computação, especi�camente na compreensão da complexidade de
algoritmos, na análise de recorrências, no método de substituição, no Teorema Mestre e,
também, na compreensão das classes de problemas computacionais. Agora, vamos recapitular
o que você aprendeu e entender a importância desses conhecimentos: 
A complexidade de algoritmos é essencial para avaliar o desempenho e a e�ciência das soluções
computacionais. Durante esse processo, você aprendeu que a complexidade de tempo quanti�ca
o número de operações realizadas por um algoritmo à medida que a entrada cresce, enquanto a
complexidade de espaço mensura a quantidade de memória consumida. Esses conceitos são
cruciais para a seleção apropriada de abordagens na resolução de problemas e, também, para a
identi�cação de algoritmos mais e�cazes. 
Você explorou notações, como O (grande O), Ω (ômega) e Θ (teta), para descrever o
comportamento dos algoritmos à medida que a entrada aumenta. Essas notações funcionam
como uma linguagem universal que cientistas da computação utilizam para comunicar, de
maneira precisa e sucinta, a complexidade de algoritmos. 
A análise de recorrências desempenha um papel vital na compreensão de algoritmos recursivos.
Você também adquiriu conhecimento sobre o método da substituição e o Teorema Mestre,
ferramentas poderosas para a análise de complexidade de algoritmos, especialmente aqueles
que se encaixam no paradigma "dividir e conquistar". Essas técnicas possibilitam uma análise
precisa do desempenho de algoritmos em diversos cenários. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Você conheceu as classes de problemas P, NP e NP-Completo. Compreendeu que a Classe P
engloba problemas que podem ser resolvidos de maneira e�ciente em tempo polinomial; que a
Classe NP abrange problemas cujas soluções podem ser veri�cadas de forma e�caz em tempo
polinomial; e entendeu que a Classe NP-Completo abarca problemas intratáveis que desa�am os
mentores da computação. Essas classes são cruciais para a categorização de problemas, na
antecipação de suas di�culdades e para a orientação na criação de soluções e�cazes. 
Sendo assim, você percebeu como esses conceitos têm aplicações no mundo real. Por exemplo,
ao projetar sistemas de busca na web ou software para processamento de dados em larga
escala, a compreensão da complexidade dos algoritmos é essencial para garantir e�ciência e
desempenho para os usuários. 
Essas competências são imprescindíveis para qualquer pessoa que deseja sobressair-se no
campo da ciência da computação, pois elas possibilitam tomar decisões bem fundamentadas na
escolha de algoritmos e na resolução de problemas complexos. Continue a explorar e aprofundar
os seus conhecimentos, pois eles constituem a base de uma carreirasólida e bem-sucedida na
área da computação. Parabéns por seu progresso até o momento! 
Videoaula: Revisão da unidade
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante!  
Se você quer recapitular e aprofundar os conhecimentos essenciais que adquiriu sobre a
complexidade de algoritmos, a análise de recorrências, as notações assintóticas, as classes de
problemas e as suas aplicações práticas, este vídeo é para você! Vamos explorar juntos esses
conceitos fundamentais da ciência da computação. Assista para fortalecer as suas habilidades e
compreender como o conhecimento do assunto pode moldar o mundo da programação.  
Estudo de caso
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Imagine-se trabalhando para uma empresa de entregas online que está crescendo rapidamente e
ganhando cada vez mais clientes. Essa empresa conecta restaurantes locais aos consumidores,
permitindo que as pessoas peçam comida de seus restaurantes favoritos e a recebam em casa.
Esse setor é altamente competitivo, e a empresa está determinada a oferecer o melhor serviço
possível aos seus clientes. 
Recentemente, a empresa tem enfrentado desa�os relacionados à e�ciência de seus algoritmos
de roteirização de entregas. À medida que o número de pedidos aumenta, torna-se crucial
otimizar os algoritmos para garantir que as entregas sejam feitas de forma rápida e e�ciente,
minimizando o tempo de espera dos clientes e os custos operacionais. 
Situação-problema 
A empresa está em busca de uma solução para otimizar a alocação de entregas aos seus
entregadores. Atualmente, os algoritmos utilizados não são e�cientes o su�ciente para lidar com
a crescente demanda, resultando em atrasos nas entregas e, consequentemente, na insatisfação
dos clientes. 
Desa�o 
Seu desa�o como membro da equipe de desenvolvimento é aplicar os conceitos que você
aprendeu sobre complexidade de algoritmos, notações assintóticas e análise de recorrências
para aprimorar o algoritmo de roteirização de entregas. Você deve encontrar maneiras de reduzir
o tempo de processamento necessário para calcular as rotas ideais e alocar pedidos aos
entregadores. 
Tarefas 
Analisar o algoritmo de roteirização de entregas atual da empresa para identi�car os
gargalos de desempenho. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Propor melhorias ou otimizações no algoritmo que reduzam a complexidade de tempo e
espaço, tornando-o mais e�ciente. 
Utilizar notações assintóticas, como O (grande O), Ω (ômega) e Θ (teta), para descrever e
comunicar a complexidade dos algoritmos propostos. 
Implementar as melhorias no algoritmo e realizar testes de desempenho para avaliar a
e�cácia das mudanças. 
Apresentar um relatório à equipe de gerenciamento, demonstrando como as suas
otimizações reduziram o tempo de processamento e melhoraram a e�ciência das
entregas. 
Resultado esperado 
Espera-se que, ao concluir este estudo de caso, você seja capaz de: aplicar os conceitos de
complexidade de algoritmos na prática; identi�car oportunidades de otimização em algoritmos
existentes e implementar melhorias que resultem em um desempenho mais e�ciente. Isso não
apenas ajudará a empresa a oferecer um serviço de entrega de alta qualidade, mas também
fortalecerá as suas habilidades como pro�ssional da ciência da computação. 
Lembre-se de que a otimização de algoritmos é uma habilidade valiosa em um mercado de
trabalho cada vez mais competitivo. Este estudo de caso oferece uma oportunidade realista de
aplicar os seus conhecimentos e aprimorar as suas habilidades práticas em um ambiente
pro�ssional. Boa sorte na resolução deste desa�o!
________
Re�ita
Estudante, explorar as classes de problemas na computação é como desvendar um mapa em
nossa jornada na ciência da computação e na resolução de problemas reais. 
Na Classe P, encontramos problemas solucionáveis e�cientemente, como trilhas claras em
nosso caminho. Dominar essa classe abre portas para soluções e�cazes. 
A Classe NP desa�a a nossa capacidade de veri�car soluções e�cientemente, como questionar
se a nossa solução está correta. Ela aprimora as nossas habilidades de veri�cação, essenciais
na computação. 
A Classe NP-Completo é um terreno misterioso, no qual problemas difíceis desa�am até mesmo
os melhores pro�ssionais da computação. Resolvê-los e�cientemente abriria portas para
soluções de inúmeros outros problemas. 
Na prática, essas classes de problemas são como mapas. Ao enfrentar um problema no mundo
real, classi�cá-lo nessas classes economiza tempo e esforço na escolha de estratégias de
resolução. 
Esses conceitos são aplicáveis na ciência da computação e na engenharia de software. Eles
ajudam na escolha de algoritmos e estratégias para tomar decisões e�cazes. 
Lembre-se: as classes de problemas são aliadas na jornada pela computação, como faróis,
guiando-o com con�ança e destreza. Use esse conhecimento para enfrentar desa�os
computacionais com sucesso!  
Videoaula: Resolução do estudo de caso
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Competências necessárias 
Para resolver esse desa�o, é essencial ter um profundo entendimento da complexidade de
algoritmos, notações assintóticas e classes de problemas. Além disso, você precisará aplicar os
seguintes conceitos e habilidades: 
Complexidade de algoritmos: você deve ser capaz de analisar e escolher algoritmos e�cientes
para resolver o problema de otimização de rotas. Isso envolve entender a complexidade de
tempo e espaço de diferentes algoritmos e selecionar o mais apropriado. 
Notações assintóticas: utilize as notações "Big O" (O), Ω, e Θ para descrever o desempenho dos
algoritmos em relação ao tamanho dos dados de entrada. Isso ajudará a estimar o tempo de
execução do algoritmo. 
Classes de problemas: compreenda a natureza do problema de otimização de rotas e relacione-o
às classes de problemas, como P, NP ou NP-Completo. Isso pode ajudar a determinar a
complexidade do problema em questão. 
Questionamentos relevantes 
Como você representaria o problema de otimização de rotas em termos de algoritmos e
estruturas de dados? 
Quais algoritmos você consideraria para resolver esse problema? Qual é a complexidade de cada
um deles? 
Como você avaliaria a e�cácia do algoritmo em otimizar as rotas? Quais métricas seriam
relevantes? 
Como a notação "Big O" pode ser aplicada para descrever a complexidade do algoritmo
desenvolvido? 
Considerando as classes de problemas, como você classi�caria o problema de otimização de
rotas? 
Este estudo de caso oferece uma oportunidade prática para aplicar os conhecimentos teóricos
adquiridos e desenvolver uma solução e�ciente para um problema do mundo real. Ao fazer isso,
você contribuirá para o sucesso da plataforma de entregas online, melhorando, assim,  a
experiência dos clientes e dos motoristas
Resumo visual
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Veja o resumo visual da unidade:
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Referências
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
CORMEN, T. Desmisti�cando Algoritmos. Grupo GEN, 2013. E-book. ISBN 9788595153929.
Disponível em: https://integrada.minhabiblioteca.com.br/#/books/9788595153929/. Acesso em:
28 ago. 2023. 
DASGUPTA, S.; PAPADIMITRIOU, C.; VAZIRANI, U. Algoritmos. Grupo A, 2009. E-book. ISBN
9788563308535. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788563308535/. Acesso em: 28 ago. 2023. 
DOBRUSHKIN, V. A. Métodos para Análise de Algoritmos. Grupo GEN, 2012. E-book. ISBN 978-85-
216-2989-4. Disponível em: https://integrada.minhabiblioteca.com.br/#/books/978-85-216-2989-4/. Acesso em: 28 ago. 2023. 
SERPA, M. S.; RODRIGUES, T. N.; ALVES, I. C.; et al. Análise de Algoritmos. Grupo A, 2021. E-book.
ISBN 9786556901862. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9786556901862/. Acesso em: 28 ago. 2023. 
,
Unidade 4
Teoria da Complexidade: Projeto de Algoritmos
Aula 1
Ordenação de dados
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Introdução
Olá, estudante! 
Algoritmos de ordenação desempenham um papel essencial dentro da teoria da computação.
Uma das aplicações mais conhecidas para essa classe de algoritmos é o uso nas operações
básicas de inserções, deleções e buscas.  
Neste estudo, passaremos pelos métodos de ordenação simples, por exemplo Insertion Sort
(ordenação por inserção); e métodos de ordenação e�cientes, como, por exemplo, Merge Sort
(dividir-para-conquistar), comparando tais estratégias. Mostraremos a importância da escolha
adequada do método de ordenação segundo o contexto da situação-problema, algo que
in�uencia de maneira crucial na escolha da tecnologia/ferramenta que você deseja usar para o
desenvolvimento da solução. Ao �nal, esperamos que você, estudante, esteja apto para analisar
outros métodos de ordenação e identi�car qual é a sua complexidade.  
Vamos começar? 
 Métodos de ordenação
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Seja v uma sequência numérica com n elementos, e sendo n um número inteiro positivo, dizemos
que v está em ordem crescente se: 
 v[0] ≤ v[1]≤…≤v[n],  
e em ordem decrescente se: 
v[0] ≥ v[1]≥…≥v[n].  
Para pequenas quantidades de dados, o problema de ordenação não assume uma relevância
signi�cativa. Porém, para quantidades muito grandes, como, por exemplo, em Big Data, entender
e analisar quais algoritmos de ordenação são mais vantajosos em determinada situação, faz
toda diferença. 
Métodos de ordenação simples 
Os métodos de ordenação simples são, em sua maioria, os métodos de ordenação que
intuitivamente usamos no nosso dia a dia, comparando elemento a elemento até obter a
ordenação desejada. Tais métodos são fáceis de entender e implementar, porém não são
adequados para grandes conjuntos de dados, uma vez que possuem, no pior caso, O(n²)
operações, em que n é quantidade de elementos da sequência. Alguns exemplos desses
métodos são: Insert Sort, Select Sort e Bubble Sort.  
Insert Sort  
Este algoritmo de ordenação é bastante simples de ser implementado. A ideia principal é
comparar cada elemento com os demais elementos restantes, e inseri-lo na posição correta. Não
é indicado para conjuntos grandes de dados, pois em seu pior caso será necessário n²
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
operações, O(n²), em que n é quantidade de elementos da sequência. Porém, é considerado um
algoritmo estável, ou seja, a ordem relativa de elementos iguais na sequência não é alterada no
decorrer do processo de ordenação.  
Bubble Sort 
Assim como o Insert Sort, o Bubble Sort é um algoritmo de ordenação bastante simples de
implementar. A diferença entre ambos os algoritmos de ordenação é que o Bubble Sort percorre
a lista numérica ordenando pares consecutivos de números, passando pela lista várias vezes. Em
seu pior caso também possui ordem quadrática, isto é, O(n²) operações.   
Métodos de ordenação e�cientes 
Os métodos de ordenação e�cientes são aqueles desenvolvidos com o objetivo de minimizar a
quantidade de operações e tempo de execução, visando a sua utilização em grandes
quantidades de dados. Com esse objetivo em mente, esses métodos acabam perdendo a noção
intuitiva dos métodos simples. São métodos que, em sua maioria, o pior caso é O(n log n)
operações. Alguns exemplos dos métodos e�cientes são: Merge Sort, Quick Sort e Shell Sort.  
Merge Sort 
Este é um algoritmo bastante e�ciente computacionalmente. Ele usa a abordagem “dividir para
conquistar”, quebrando a sequência em subsequência de tamanho unitário na fase “dividir” e,
depois, juntando de maneira ordenada na fase “conquistar”. Foi criado pelo matemático John
Von Neumann por volta de 1945, e o seu pior caso é O(n log n) operações. É considerado um
algoritmo estável. Uma outra vantagem desse algoritmo é que ele pode ser facilmente
paralelizado, otimizando, assim, a sua execução.   
Quick Sort 
Assim como o Merge Sort, o algoritmo Quick Sort aplica o princípio “dividir para conquistar” para
dividir a sequência numérica em duas listas a partir do elemento, o qual chamamos de pivot. A
primeira lista com itens menores do que o pivot, e a segunda lista com itens maiores do que o
pivot. O algoritmo então ordena ambas as listas recursivamente até que a lista resultante esteja
completamente ordenada. Logo, a complexidade computacional depende da escolha do pivot,
variando do melhor caso O(n log n) operações, quando escolhemos o pivot próximo à mediana
da sequência, e O(n²) operações quando escolhemos o pivot próximo aos valores extremos da
sequência. Uma das grandes vantagens do Quick Sort é que, assim como o Merge Sort, ele é um
algoritmo fácil de paralelizar. 
Análise entre os métodos
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Vamos analisar um exemplo de método simples, o Insert Sort. E, também, um exemplo de
método e�ciente, o Merge Sort, ilustrando o comportamento de ambos. 
Insert Sort 
Para ilustrar o seu comportamento, ordenamos a sequência numérica 5, 8 ,4, 3 e 2. 
8<5? Não, logo mantemos os números 5 e 8 nas suas posições 5, 8 ,4, 3, 2.  
Note que a subsequência 5, 8 está ordenada.  
4<8? Sim, invertemos as posições destes números 5, 4 ,8, 3, 2 (inserimos o 4 na posição
em que estava o 8).  
4<5? Sim, invertemos as posições destes números 4, 5 ,8, 3, 2.  
Assim, a subsequência 4, 5, 8 está ordenada. 
Continuando as comparações e inserções de posições com 3 e 2, obtemos a sequência
ordenada 2, 3, 4, 5, 8.  Note que começamos as comparações pelo segundo elemento da
sequência, o número 8. E, para esse número, �zemos somente uma comparação. Em seguida,
com o terceiro elemento da sequência, o número 4, �zemos duas comparações. Usando esse
raciocínio, com o quarto elemento da sequência, o número 3, �zemos 3 comparações e com o
quinto elemento, o número 2, �zemos 4 comparações. Logo, o total de operações é: 
1 + 2 + 3 + 4 = 10 = (5 x 4)/2 = (n x (n-1))/2, 
sendo n=5 o número de elementos da sequência. No caso geral, para uma sequência com n
elementos, n um inteiro positivo, a quantidade de operações no Insert Sort é dada pela soma da
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
PA: 
1 + 2 + 3 + … + (n-1) = (n x (n-1))/2 = (n²- n)/2 = O(n²),  
ou seja, para o pior caso, o Insert Sort possui complexidade quadrática. A fórmula acima foi
mostrada somente de maneira intuitiva, pois a demonstração formal envolve técnicas que não
fazem parte do escopo deste curso. 
Merge Sort 
Usaremos o Merge Sort para ordenar novamente a sequência numérica 5, 8 ,4, 3 e 2. 
Dividimos a sequência numérica 5, 8 ,4, 3 e 2 ao meio, criando as duas subsequências 5, 8 e
4, 3, 2.  
A subsequência 5, 8 é novamente dividida em duas, obtendo somente os números 5 e 8. A
subsequência 4, 3, 2 também é dividida em duas: 4 e 3, 2. Na última divisão, obtemos os
números 3 e 2. Totalizando 5 subsequências unitárias: 5; 8; 4; 3; 2. 
O próximo passo é juntar as sequências de maneira ordenada, obtendo as subsequências:
5, 8; 4; 2, 3. Repetindo o procedimento anterior, obtemos: 5, 8; 2, 3, 4. E, por último, a
sequência ordenada 2, 3, 4, 5, 8.  
Seja n, inteiro positivo, o número de elementos da sequência que desejamos ordenar. Ao utilizar
o Merge Sort, a primeira etapa é a divisão. Nesse caso, dividimos até que restem somente
subsequência unitárias, ou seja, precisamos fazer k passos até que: 
Isto é, em  passos, obtemos subsequências unitárias. Em cada um dos 
 passos dessa fase, realizamos operações de divisões que são de ordem constante, O(1). Na
fase de “conquistar”, o algoritmo realiza os mesmos  , porém ordenando ao juntar as
subsequências.Em cada um dos  , passos dessa fase, o número máximo de
comparações é n, totalizando   operações. Portanto, podemos considerar como o número
total de operações realizadas pelo algoritmo:
Comparação entre os métodos
n/2k=1= logn2 =log2k
2 ⇒k = logn2  
k  =  logn2 k  =  logn2
k  =  logn2
k  =  logn2
n logn2
logn2   +  n logn2   =  O(n logn2  )
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Usando como ponto de partida a análise que �zemos na última seção, vamos comparar o Insert
Sort, método simples, e o Merge Sort, método e�ciente. Considere a tabela abaixo:
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Tabela 1 | Ordem de grandezas das operações. Fonte: Elaborado pelo autor.
Na coluna , veri�camos o pior caso para o Merge Sort, e na coluna  o pior caso para o
Insert Sort. Fica evidente, já na primeira iteração, n=10, que o método simples Insert Sort em seu
pior caso, possui um desempenho muito pior do que o Merge Sort em seu pior caso. Para ilustrar
a diferença discutida acima, �zemos o grá�co até n=1.000.000:
Figura 1 | Grá�co de comparação da complexidade Insert Sort e Merge Sort.
n logn2
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Figura 1 | Grá�co de comparação da complexidade Insert Sort e Merge Sort.
Formalmente, para mostrar que O( ) possui um crescimento menor do que O(n²), basta
mostrar que /n) = 0, porém esse não é o escopo deste curso. Supondo que um
computador possui 10 GHz ( operações por segundo) podemos estimar o tempo de
ordenação dos algoritmos acima por:
     1 Mi de elementos:
     Insert Sort: 1.000.000.000.000 op. / (1010 op./seg) = 100 segundos.
     Merge Sort: 19.931.568 op. / ( 1010 op./seg) = 0,001 segundos.
     10 Mi de elementos:
     Insert Sort: 100.000.000.000.000 op. / (1010 op./seg) = 10.000 segundos.
 
     Merge Sort: 232.534.967 op. / (1010 op./seg) = 0,02 segundos.
     100 Mi de elementos:
     Insert Sort: 10.000.000.000.000.000 op. / (1010 op./seg) = 1.000.000 segundos.
n logn2
limn→+∞ (logn2
1010
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
     Merge Sort: 2.657.542.476 op. / (1010 op./seg) = 0,26 segundos.
     1 Bi de elementos:
     Insert Sort: 100.000.000.000.000 op. /  (1010 op./seg) = 100.000.000 segundos.
Merge Sort: 29.897.352.854 op. /  (1010 op./seg) = 2,99 segundos.
Usando o caso 1 Bi de elementos a serem ordenados, o método simples Insert Sort nas
condições acima gasta cerca de 3 anos para conseguir produzir a nossa ordenação, porém o
método e�ciente Merge Sort gasta apenas 3 segundos aproximadamente. É uma diferença
impressionante, e que mostra a importância da escolha apropriada do algoritmo levando em
consideração o problema a ser resolvido. O caso 1 Bi de elementos pode parecer, a princípio,
extremo, porém, hoje com a variedade e a velocidade de captação e, também, com a
disponibilização dos dados, a tarefa de ordenar 1 Bi de elementos é muito mais comum do que
possamos imaginar. 
Devemos jogar fora os métodos simples? Não. Como foi visto acima, eles não têm grandes
aplicações práticas, mas a sua utilização para pequenas tarefas é razoável. Além disso, esses
métodos trazem uma abordagem didática muito forte, introduzindo o problema de ordenação
aos estudantes e possibilitando o desenvolvimento prático dos primeiros algoritmos dentro do
percurso de aprendizagem.
Videoaula: Ordenação de dados
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante!
Neste vídeo, você aprenderá a respeito dos métodos de ordenação simples e e�cientes. Como
exemplo, analisaremos as diferenças entre o Insert Sort, método de ordenação simples, e o
Merge Sort, método de ordenação e�ciente, mostrando as suas implementações e as suas
complexidades computacionais. Ao �nal, discutiremos, dentre as abordagens apresentadas, o
contexto das suas aplicações. 
Saiba mais
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Outro algoritmo muito importante dentro do tema de ordenação é o Heap Sort. Ele foi
desenvolvido por J. W. J. Williams e também é um algoritmo linearítmico (O( n log n)).
Referências
https://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/hpsrt.html
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Algorithms 1999-4893. Disponível em: https://www.proquest.com/publication/2032439?
accountid=134629. Acesso em: 31 out 2023.
BACKES, A. R. Algoritmos e Estruturas de Dados em Linguagem C. Rio de Janeiro: LTC, 2023.
Disponível em: https://integrada.minhabiblioteca.com.br/books/9788521638315. Acesso em: 31
out 2023.
JR., Di. Algoritmos e Programação de Computadores. Rio de Janeiro: GEN LTC, 2019. Disponível
em: https://integrada.minhabiblioteca.com.br/books/9788595150508. Acesso em: 31 out 2023.
NASCIMENTO, J. N. R. D. Ciência da computação II. Londrina: Editora e Distribuidora Educacional
S.A., 2018. 2018 ISBN 9788552210924. Disponível em: https://biblioteca-
virtual.com/detalhes/ebook/6087055554aa8872fb666b55 . Acesso em: 31 out 2023.
Bibliogra�a complementar
ACM Computing Surveys. ISSN 1557-7341. Disponível em:
https://www.proquest.com/publication/47570?accountid=134629&decadeSelected=2020+-
+2029&yearSelected=2023&monthSelected=03&issueNameSelected=02023Y03Y01$23Mar+202
3$3b++Vol.+55+$283$29 . Acesso em: 31 out 2023.
DALE, N.; LEWIS, J. Ciência da Computação. 4ª edição. Rio de Janeiro: LTC, 2010. Disponível em:
https://integrada.minhabiblioteca.com.br/books/9788521635215 . Acesso em: 31 out 2023.
DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computabilidade.
v.5 (Livros didáticos informática UFRGS). Porto Alegre: Bookman, 2009. Disponível em:
https://integrada.minhabiblioteca.com.br/books/9788577808311 . Acesso em: 31 out 2023.
SZWARCFITER, J. L. Teoria Computacional de Grafos - Os Algoritmos. Rio de Janeiro: GEN LTC,
2018. Disponível em: https://integrada.minhabiblioteca.com.br/books/9788595155183 . Acesso
em: 31 out 2023.
https://www.proquest.com/publication/2032439?accountid=134629
https://www.proquest.com/publication/2032439?accountid=134629
https://integrada.minhabiblioteca.com.br/books/9788521638315
https://integrada.minhabiblioteca.com.br/books/9788595150508
https://biblioteca-virtual.com/detalhes/ebook/6087055554aa8872fb666b55
https://biblioteca-virtual.com/detalhes/ebook/6087055554aa8872fb666b55
https://www.proquest.com/publication/47570?accountid=134629&decadeSelected=2020+-+2029&yearSelected=2023&monthSelected=03&issueNameSelected=02023Y03Y01$23Mar+2023$3b++Vol.+55+$283$29
https://www.proquest.com/publication/47570?accountid=134629&decadeSelected=2020+-+2029&yearSelected=2023&monthSelected=03&issueNameSelected=02023Y03Y01$23Mar+2023$3b++Vol.+55+$283$29
https://www.proquest.com/publication/47570?accountid=134629&decadeSelected=2020+-+2029&yearSelected=2023&monthSelected=03&issueNameSelected=02023Y03Y01$23Mar+2023$3b++Vol.+55+$283$29
https://integrada.minhabiblioteca.com.br/books/9788521635215
https://integrada.minhabiblioteca.com.br/books/9788577808311
https://integrada.minhabiblioteca.com.br/books/9788595155183
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Aula 2
Algoritmos de programação dinâmica
Introdução
Olá, estudante! 
Dentro da Teoria da Computabilidade, estudar as funções de�nidas por meio de si mesmas
representa não somente ganhos em termos de produção de códigos, mas também em termos da
interpretação dessas funções. Tal estudo abre novas possibilidades para soluções de problemas
mais complexos amparados pela recursão e pelo armazenamento. Nesse contexto,
apresentamos a programação dinâmica, uma técnica que aproveita da recursividade e do
armazenamento para obter soluções ótimas aos problemas de otimização (maximização e
minimização). Por meio desse novo paradigma de construção de algoritmos, construímos, nesta
aula, um exemplo de sequênciade Fibonacci mais e�ciente, e ainda como aplicação, mostramos
o exemplo do troco com mínimo de moedas possíveis. Esperamos que ao �nal, você, estudante,
possa estar apto para aplicar esse novo paradigma nas soluções de problemas complexos do
seu dia a dia.  
Vamos começar? 
 Recursividade e programação dinâmica
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
De�nimos o fatorial de um número inteiro positivo n, por: 
n! = 1 x 2 x….x (n - 1) x n. 
Para o caso n=0, de�nimos 0! = 1. Como exemplo, podemos calcular o fatorial de 10: 
10! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 = 3.628.800. 
Ao calcular o fatorial de 10, note que poderíamos ter escrito 10! = 9! x 10, pois: 
9! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9, 
ou seja, supondo que já calculamos 9!, basta multiplicar o resultado por 10 para obter o valor de
10!. De maneira geral, sendo n um número inteiro positivo não é difícil veri�car que: 
n! = (n-1)! x n. 
Logo, sempre podemos recorrer aos valores já calculados para obter o valor do fatorial de um
número. Considere a função f(n) = n!, que calcula o fatorial de um número inteiro positivo n.
Seguindo a notação acima, podemos escrever: 
f(n) = n! = (n-1)! x n = f(n-1) x n. 
Uma função que recorre a si mesma durante uma execução é dita função recursiva. A função
fatorial, f(n) = n!, vista a pouco, é um exemplo clássico de função recursiva. Considere a seguinte
função recursiva segundo Backes (): 
T(n) = T(n - 1) + 3. 
Como T(n-1) = T(n - 2) + 3 e T(n-2) = T(n - 3) + 3, temos: 
 T(n) = T(n - 1) + 3 = (T(n - 2) + 3) + 3 = T(n - 2) + 6 = (T(n - 3) + 3) + 6 = T(n - 3) + 9. 
T(n) = T(n - 3) + 3 x 3. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Assim, podemos veri�car que:  
T(n) = T(n - k) + 3 x k. 
Dessa forma o, caso base, ou seja, o início da recursão acima é em n - k = 1, isto é, k = n - 1.
Substituindo na fórmula acima: 
T(n) = T(1) + 3 x (n - 1) = T(1) + 3 x n - 3. 
Sabendo o valor de T(1), podemos calcular T(n) facilmente para qualquer inteiro positivo n.
Ilustramos, com o exemplo acima, que em alguns casos podemos obter uma fórmula fechada
para a função recursiva. Isto pode facilitar o cálculo, porém encontrar tal fórmula nem sempre é
possível, e quando isso ocorre, é necessária uma análise criteriosa.  
Voltando ao tema da recursividade, as funções recursivas são exemplos de relações de
recorrência, isto é, “uma expressão que descreve uma função em termos de entradas menores
da função”, conforme explica Backes (2023). Abstraindo esse conceito, o que de fato estamos
fazendo é repartir o problema inicial em subproblemas, cuja solução esperamos ser mais
simples, e uma vez que esta seja armazenada, se torna possível usar as subsunções para
resolver o problema inicial. A essa técnica damos o nome de programação dinâmica (PD). Assim,
a programação dinâmica descreve uma maneira de resolvermos problemas complexos por meio
da solução de problemas mais simples. Usando como exemplo o algoritmo de ordenação Merge
Sort, note que temos duas fases: 1 - dividir e 2 - conquistar. Na fase de dividir, a sequência é
quebrada até obtermos sequências unitárias, para que na fase de conquistar tais sequências
unitárias sejam ordenadas, armazenadas e agregadas, até a ordenação completa da sequência. 
Identi�cando problemas de PD
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Para resolvermos problemas por meio da programação dinâmica, é preciso identi�car as duas
características:
1 - Subproblemas coincidentes: quando as soluções para os mesmos subproblemas são
repetidamente usadas para resolver o problema atual.
2 - Subestrutura ótima: quando solução ótima (melhor solução) de um determinado problema
pode ser obtida usando soluções ótimas de seus subproblemas.
Como exemplo das características acima, vamos analisar a sequência de Fibonacci:
0, 1, 1, 2, 3, 5, 8, 13, ….
Podemos veri�car que a função recursiva que de�ne a sequência de Fibonacci é dada por:
F(0) = 0; F(1) = 1,
F(n) = F(n - 1) + F(n - 2), n>1.
Usando a função recursiva acima, notamos que a solução ótima para F(n) depende da solução
ótima de F(n-1) e F(n-2), o que caracteriza uma subestrutura ótima. Além disso, para obter F(n),
precisamos de F(n-1) e F(n-2), sendo que para calcular F(n-1) é necessário F(n-2), o que
caracteriza subproblemas coincidentes. Portanto, o problema de computar os termos da
sequência de Fibonacci é um exemplo em que podemos usar a programação dinâmica. Mas
como? Para ilustrar a construção do algoritmo usando programação dinâmica e a diferença entre
programação dinâmica e somente recursividade, analisaremos o algoritmo que calcula os
termos da sequência de Fibonacci. Veja a seguir
seq_fib(n):
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
   se n≤1
      retorne n
senão: 
      retorne seq_fib(n-1) + seq_fib(n-2)  
Ao calcular seq_�b(4), obtemos: 
Figura 1 | Calculando a sequência de Fibonacci para n=4. Fonte: Elaborado pelo autor. 
Na Figura 1, percebemos que seq_�b(2) é calculado duas vezes, ou seja, é algo que utiliza
demasiadamente tempo e armazenamento, o que torna o algoritmo seq_�b(n) ine�ciente,
mesmo sendo recursivo. Escrevendo o algoritmo em termos de programação dinâmica, temos: 
seq_fib2(n): 
   x(0)=0 
   x(1)=0  
   para i=2 até n faça: 
      x(i) = x(i-1) + x(i-2) 
   retorne x(n) 
Usando o algoritmo seq_�b2(n), para n=4, calculamos em sequência: 
1. x(2), obtido por meio da soma x(1) + x(0) 
2. x(3), computado por meio da soma x(2) + x(1), sendo x(2) já conhecido,  
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
e armazenamos os resultados de maneira, que quando n=4, já sabemos os valores de x(2) e x(3),
conseguindo facilmente x(4) e, por consequência, conseguimos seq_�b2(4). Ou seja, usamos a
recursividade e o armazenamento para tornar a maneira de calcular os termos da sequência de
Fibonacci mais e�ciente por meio da programação dinâmica.  
A abordagem do algoritmo seq_�b2(n), é dita “bottom-up”, o que em tradução livre signi�ca “de
baixo para cima”, pois resolve o problema de calcular seq_�b2(n), dos casos mais triviais (baixo)
para o caso mais complexo (cima). Fazendo algumas modi�cações no algoritmo seq_�b2(n),
conseguimos a abordagem “top-down”, em tradução livre signi�ca “de cima para baixo”, partindo
da solução geral do problema (cima) para as soluções triviais (baixo)
PD aplicada ao problema do troco
Tendo disponíveis as moedas de 1, 5, 10, 25, 50 e 100 centavos (R$ 1,00), qual é a melhor forma
(usando menos moedas) de fornecer um troco de R$ 1,00? Nesse caso simples, basta usar uma
moeda de R$ 1,00 como troco. Ou seja, usamos somente uma moeda, e essa é a solução ótima
para a nossa pergunta! Imagine agora que o troco a ser dado é de R$ 0,68, qual será a melhor
maneira de fornecê-lo? Para organizar a nossa maneira de pensar, vamos, primeiramente,
fornecer a solução por meio da abordagem que chamamos de “gulosa”.  
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Nela, usamos a moeda de maior valor até que não seja mais possível. Assim, no nosso caso,
começamos com uma moeda de R$ 0,50, já que duas moedas de R$ 0,50 excedem o nosso
troco. Em seguida, a maior moeda disponível será R$ 0,10, sendo escolhida somente uma moeda
também desse valor. A próxima moeda será R$ 0,05. Restando escolhermos no �nal três moedas
de R$ 0,01. Portanto, a nossa solução usando a abordagem gulosa é 6 moedas {R$ 0,50; R$ 0,10;
R$ 0,05; R$ 0,01; R$ 0,01; R$ 0,01}. Nem sempre ela fornece a solução ótima, como, por exemplo,
no seguinte cenário: supondo que desejamos dar de troco R$ 0,14, e temos somente moedas de
R$ 0,01, R$ 0,07 e R$ 0,10, a abordagem gulosa tem como resultado 5 moedas {R$ 0,10; R$ 0,01;
R$ 0,01; R$ 0,01; R$ 0,01}, que claramente não é a solução ótima, pois duas moedas de R$ 0,07
fornecem o troco desejado com o menor número de moedas. Utilizando a programação
dinâmica, dividimos o problema do troco de R$ 0,14 em subproblemas, analisando as
possibilidades de usodas moedas de R$ 0,01, R$ 0,07 e R$ 0,10, como mostra a �gura a seguir. 
Figura 2 | Divisão em subproblemas para o troco de R$ 0,14. Fonte: Elaborado pelo autor. 
Note que o menor caminho, isto é, a solução ótima (representada na �gura pelo caminho em
negrito) coincide com nossa intuição, duas moedas de R$ 0,07. Os casos destacados em
vermelho devem ser eliminados, pois saem fora do escopo do nosso problema. Outra
observação importante é que, seguindo o extremo esquerdo da �gura, na linha 14, 13, 12, ….,
obtemos o caminho mais longo, aquele usando somente moedas de R$ 0,01. Além disso,
podemos identi�car as características de programação dinâmica ao olhar a Figura 2. Primeiro,
subproblemas coincidentes, os números 6 e 3, por exemplo, aparecem repetidas vezes nessa
�gura. Subestrutura ótima, a solução ótima do problema é obtida por meio da solução ótima dos
subproblemas.  
Voltando ao caso dos R$ 0,68, não é difícil observar que o caminho mínimo, isto é, solução ótima
usando programação dinâmica, de fato é a solução apresentada {R$ 0,50; R$ 0,10; R$ 0,05; R$
0,01; R$ 0,01; R$ 0,01}. 
Videoaula: Algoritmos de programação dinâmica
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante!
Neste vídeo, você aprenderá a respeito do método de solução de problemas: a programação
dinâmica. Como exemplo, comparamos a maneira de calcular a sequência de Fibonacci com e
sem as técnicas da programação dinâmica, mostrando a e�ciência dessa programação. Por
último, atacamos o problema do troco usando a quantidade mínima de moedas disponíveis.
Saiba mais
Um exemplo que podemos usar em programação dinâmica para obter uma solução ótima é no
problema de segmento de soma máxima de um vetor, conforme podemos ver no artigo: Quarto
algoritmo: Programação dinâmica.
Referências
https://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/max-sum-segment.html#sec:PD
https://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/max-sum-segment.html#sec:PD
https://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/max-sum-segment.html#sec:PD
https://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/max-sum-segment.html#sec:PD
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Algorithms 1999-4893. Disponível em: https://www.proquest.com/publication/2032439?
accountid=134629. Acesso em: 31 out 2023.
BACKES, A. R. Algoritmos e Estruturas de Dados em Linguagem C. Rio de Janeiro: LTC, 2023.
Disponível em: https://integrada.minhabiblioteca.com.br/books/9788521638315. Acesso em: 31
out 2023.
JR., D. Algoritmos e Programação de Computadores. Rio de Janeiro: GEN LTC, 2019. Disponível
em: https://integrada.minhabiblioteca.com.br/books/9788595150508. Acesso em: 31 out 2023.
NASCIMENTO, J. N. R. D. Ciência da computação II. Londrina: Editora e Distribuidora Educacional
S.A., 2018. 2018 ISBN 9788552210924. Disponível em: https://biblioteca-
virtual.com/detalhes/ebook/6087055554aa8872fb666b55. Acesso em: 31 out 2023.
Bibliogra�a complementar
ACM Computing Surveys. ISSN 1557-7341. Disponível em:
https://www.proquest.com/publication/47570?accountid=134629&decadeSelected=2020+-
+2029&yearSelected=2023&monthSelected=03&issueNameSelected=02023Y03Y01$23Mar+202
3$3b++Vol.+55+$283$29. Acesso em: 31 out 2023.
DALE, N.; LEWIS, J. Ciência da Computação. 4ª edição. Rio de Janeiro: LTC, 2010. Disponível em:
https://integrada.minhabiblioteca.com.br/books/9788521635215. Acesso em: 31 out 2023.
DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computabilidade.
v.5 (Livros didáticos informática UFRGS). Porto Alegre: Bookman, 2009. Disponível em:
https://integrada.minhabiblioteca.com.br/books/9788577808311. Acesso em: 31 out 2023.
SZWARCFITER, J. L. Teoria Computacional de Grafos - Os Algoritmos. Rio de Janeiro: GEN LTC,
2018. Disponível em: https://integrada.minhabiblioteca.com.br/books/9788595155183. Acesso
em: 31 out 2023.
https://www.proquest.com/publication/2032439?accountid=134629.Acesso
https://www.proquest.com/publication/2032439?accountid=134629.Acesso
https://integrada.minhabiblioteca.com.br/books/9788521638315
https://integrada.minhabiblioteca.com.br/books/9788595150508
https://biblioteca-virtual.com/detalhes/ebook/6087055554aa8872fb666b55
https://biblioteca-virtual.com/detalhes/ebook/6087055554aa8872fb666b55
https://www.proquest.com/publication/47570?accountid=134629&decadeSelected=2020+-+2029&yearSelected=2023&monthSelected=03&issueNameSelected=02023Y03Y01$23Mar+2023$3b++Vol.+55+$283$29
https://www.proquest.com/publication/47570?accountid=134629&decadeSelected=2020+-+2029&yearSelected=2023&monthSelected=03&issueNameSelected=02023Y03Y01$23Mar+2023$3b++Vol.+55+$283$29
https://www.proquest.com/publication/47570?accountid=134629&decadeSelected=2020+-+2029&yearSelected=2023&monthSelected=03&issueNameSelected=02023Y03Y01$23Mar+2023$3b++Vol.+55+$283$29
https://integrada.minhabiblioteca.com.br/books/9788521635215
https://integrada.minhabiblioteca.com.br/books/9788577808311
https://integrada.minhabiblioteca.com.br/books/9788595155183
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Aula 3
Algoritmos gulosos
Introdução
Olá, estudante! 
Nesta aula, abordaremos o método de solução de problemas de otimização chamado de
algoritmo guloso. Esse termo é uma tradução livre do inglês greedy (ambicioso, ganancioso), e
expressa a característica principal do método: escolher soluções locais sem se preocupar com
os demais passos. Em alguns casos, fazer essa escolha de ótimo local pode nos conduzir para
soluções globais que não são ótimas. Fazendo um paralelo com as nossas vidas, uma escolha
local ótima para matar a fome é o fast food. Rápido e saboroso! Porém, globalmente esse tipo de
comida está longe de ser uma solução ótima.  
Para ilustrar algumas aplicações com o método guloso, abordaremos o problema do troco e o
problema da mochila. Por �m, analisaremos a complexidade de uma implementação que resolve
o problema da mochila fracionária por meio do método guloso. 
Vamos começar? 
 Algoritmos gulosos
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Tendo disponíveis as moedas de 1, 5, 10, 25, 50 e 100 centavos (R$ 1,00), qual é a melhor forma
(usando menos moedas) de fornecer um troco de R$ 1,00? Nesse caso simples, basta usar uma
moeda de R$ 1,00 como troco. Ou seja, usamos somente uma moeda, e essa é a solução ótima
para a nossa pergunta! Imagine agora que o troco a ser dado é de R$ 0,68, qual será a melhor
maneira de fornecê-lo? Para organizar nossa maneira de pensar, vamos, primeiramente, fornecer
a solução por meio da abordagem que usamos a moeda de maior valor até que não seja mais
possível. Assim, no nosso caso, começamos com uma moeda de R$ 0,50, já que duas moedas
de R$ 0,50 excedem o nosso troco. Em seguida, a maior moeda disponível será R$ 0,10, sendo
escolhida somente uma moeda desse valor. A próxima moeda será R$ 0,05. Restando no �nal
escolhermos três moedas de R$ 0,01. Portanto, a nossa solução usando essa abordagem são 6
moedas {R$ 0,50; R$ 0,10; R$ 0,05; R$ 0,01; R$ 0,01; R$ 0,01}. Nem sempre ela fornece a solução
ótima, como, por exemplo, no seguinte cenário: supondo que desejamos fornecer de troco R$
0,14, e temos somente moedas de R$ 0,01, R$ 0,07 e R$ 0,10, a abordagem descrita acima tem
como resultado 5 moedas {R$ 0,10; R$ 0,01; R$ 0,01; R$ 0,01; R$ 0,01}, que claramente não é a
solução ótima, pois duas moedas de R$ 0,07 fornecem o troco desejado com menor número de
moedas. 
A primeira coisa a ser notada no exemplo acima é que estamos trabalhando com um problema
de otimização, isto é, um problema que busca uma solução ótima (solução máxima ou mínima).
No caso das moedas, queremos prover o troco usando o menor número de moedas possíveis.  
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Estabelecidoo tipo de problema e a sua solução, denotamos por algoritmo guloso, aquele que
resolve um problema de otimização, tal que em cada passo é determinada uma solução ótima
para ele, por meio das regras pré-estabelecidas, sem preocupação com as demais fases do
processo, no intuito de obter uma solução ótima para o problema mais geral. Ou seja, são
determinadas soluções ótimas locais (para cada passo), quase que independentes, para a
construção da solução ótima global (para o problema geral).  
Analisando o exemplo do troco, ao estabelecer o uso das moedas de maior valor até exaurir as
possibilidades, não estamos preocupados em quantas moedas vamos usar, mas somente em
obter uma solução ótima (local). No caso do troco de R$ 0,14, somente com as moedas de R$
0,01, R$ 0,07 e R$ 0,10, �ca explícito que a estratégia gulosa faz escolhas que são ótimas para o
momento, sem se preocupar com os próximos passos, ainda que nem sempre a estratégia
gulosa resulta em uma solução ótima global.
Onde usar a abordagem gulosa
Os problemas nos quais a estratégia gulosa possui maior chance de obter uma solução ótima,
possui duas principais características. Sendo elas: 
1. Subestrutura ótima: o problema tem essa característica se for possível dividi-lo várias
vezes e, assim, a junção das soluções ótimas dos subproblemas (soluções ótimas locais)
resulta em uma solução ótima global.
2. Propriedade gulosa: podemos construir a solução ótima global fazendo escolhas (gulosas)
pelos ótimos locais. 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
As características acima não determinam os problemas em que serão obtidas soluções ótimas
globais pela estratégia gulosa, mas sim os problemas que podemos aplicá-la. Novamente
analisando o problema do troco, veri�camos que ele possui tais características. Veremos, agora,
um outro exemplo que possui tais características e a estratégia gulosa ao ser aplicada produz
uma solução ótima.   
Problema da mochila 
Imagine que você está voltando de viagem dos EUA e pode trazer somente uma mochila com
capacidade (em kg) máxima W. Porém, você comprou no país n itens distintos, cada um com
valor v1, …., vn e peso w1, w2, …., wn, respectivamente. Quais itens vamos escolher trazer para o
Brasil de maneira que a mochila venha carregada com maior valor e respeitando a sua
capacidade W? 
Matematicamente, equacionamos o problema acima da seguinte forma: 
Existem duas versões para o problema acima, a primeira versão é a booleana (0 ou 1, ou não leva
o item ou leva o item). Já a segunda versão é a fracionária, na qual é possível levar frações dos
itens. Na segunda versão, existem x1, x2, …, xn (0,1], tais que:
Em ambos os casos, versão binária e fracionária, o problema pode ser quebrado de maneira a
possuir a característica de subestrutura ótima. Porém, no caso da versão binária, não temos a
propriedade gulosa como veremos no exemplo a seguir. Suponha que:
n=4 e W=50 kg
ob1: v1= R$ 60,00 e w1=10 kg
ob2: v2= R$ 100,00 e w2=20 kg
ob3: v3= R$ 120,00 e w3=30 kg
ob4: v4= R$ 160,00 e w4=50 kg
A melhor escolha local é pegar inicialmente ob4, já que v4= R$ 160,00 e w4=50 kg. Nesse caso,
trazemos somente o item ob4 na mochila. Porém, a escolha dos itens ob2 e ob3, nos dá o valor
de R$ 220,00 e peso de 50 kg. Assim, não chegamos em um ótimo global a partir de escolhas
gulosas.
Para ilustrar que o problema fracionário possui propriedade gulosa, vamos dividir o valor pelo
peso para entender qual produto vale mais por unidade de peso:
ob1: v1/w1 = R$ 60,00 / 10 kg = R$ 6,00 / kg
ob2: v2/w2 = R$ 100,00 / 20 kg = R$ 5,00 / kg
maxI⊂{1, 2, ..., n} ∑i∈I vi
∑i∈I wi ≤ W
maxI⊂{1, 2, ..., n} ∑i∈I vixi
∑i∈I wi xi ≤ W
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
ob3: v3/w3 = R$ 120,00 / 30 kg = R$ 4,00 / kg
ob4: v4/w4 = R$ 160,00 / 50 kg = R$ 3,20 / kg
Vamos escolher de maneira gulosa os itens acima:
O item ob1 é escolhido por completo, x1=1, valor acumulado de R$ 60,00 e peso acumulado
de 10 kg.
O item ob2 é escolhido por completo, x2=1, valor acumulado de R$ 160,00 e peso
acumulado de 30 kg.
O item ob3 é escolhido fracionado, x3=2/3, valor acumulado de R$ 240,00 (160 + 120) e peso
acumulado de 50 kg (30 + 30).
Note que a solução na abordagem gulosa supera os R$ 220,00 da solução anterior. Portanto,
fazendo escolhas ótimas locais, conseguimos um ótimo global. O que caracteriza a propriedade
gulosa.
Análise de complexidade
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Vamos veri�car o algoritmo da mochila fracionária, analisando a sua complexidade. Considere
Obj vetor de objetos distintos que desejamos colocar na mochila, p vetor com os pesos em Kg
dos objetos de Obj, v vetor com os valores em R$ dos objetos de Obj e W a capacidade máxima
em Kg da mochila. Assim, o primeiro objeto que queremos levar na mochila (Obj[1]) tem peso
p[1] e valor v[1], por exemplo. Segue uma implementação:
new_W = W # linha 3 
new_f = ordenacao(f) # linha 4 
x = vetor nulo de tamanho n # linha 5 
idx = resgata os índices de new_f # linha 6 
new_p = p com a ordem idx # linha 7 
para i=1 até n: # linha 8 
se new_p[i]
≤ 
new_W faça: # linha 9 
x[i] = 1 # linha 10 
new_W = new_W - new_p[i] # linha 11 
senão: # linha 12 
x[i] = new_W / new_p[i] # linha 13 
new_W = 0 # linha 14 
retorne x # linha 15 
Em um primeiro momento, vale pontuar que na linha 4 estamos ordenando f de maneira
decrescente, isto é, começamos do maior custo por kg até o menor custo por kg. Ao fazer tal
ordenação, é preciso usar os novos índices para usarmos corretamente os pesos em p (linhas 6
e 7). Na ordenação, linha 4, podemos escolher o algoritmo que bem entendermos, por exemplo, o
Merg Sort que tem complexidade O( ). Já na linha 5, iniciamos com o vetor x que
armazena os coe�cientes que representam as quantidades que levaremos dos objetos. Na linha
8, o loop percorre n vezes preenchendo o vetor de coe�cientes x. Note que o preenchimento pode
ser feito com um número no intervalo fechado [0,1]. Na linha 9, veri�camos se o peso do objeto é
menor do que a capacidade atual. Caso seja menor, levaremos este objeto inteiro (x=1) e
atualizaremos a capacidade atual, retirando o peso do objeto escolhido nessa iteração. Mas caso
não seja possível levar o objeto inteiro, determinaremos a fração que levaremos por meio da
linha 13. Nesse caso, o algoritmo determinará, por meio da linha 13, a maior fração possível, e na
linha 14 atribuirá 0 a capacidade atual. A partir desse momento, os demais coe�cientes x serão
0, pois já esgotamos a capacidade da mochila.  
Voltando na linha 8 e analisando a complexidade do loop, veri�camos que existem somente
comparações (n vezes) e atribuições, algo que possui complexidade O(n). Portanto, o algoritmo
moch_frac possui complexidade O 
Videoaula: Algoritmos gulosos
n log2n
(n log2n)
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante!
Neste vídeo, abordaremos o método de solução de problemas de otimização chamado de
algoritmo guloso. Esse termo é uma tradução livre do inglês greedy (ambicioso, ganancioso), e
expressa a característica principal desse método: escolher soluções locais sem se preocupar
com os demais passos. Mostraremos a aplicação dos algoritmos gulosos no problema do troco
e, também, no problema da mochila.
Saiba mais
Algoritmos gulosos são bastantes úteis dentro do contexto dos grafos. Um exemplo é no caso
da árvore geradores de um grafo, como podemos explorar mais no artigo: Árvores geradoras de
grafos. 
https://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/spanning-trees.html
https://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/spanning-trees.html
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Referências
Algorithms 1999-4893. Disponível em: https://www.proquest.com/publication/2032439?accountid=134629. Acesso em: 31 out 2023. 
BACKES, A. R. Algoritmos e Estruturas de Dados em Linguagem C. Rio de Janeiro: LTC, 2023.
Disponível em: https://integrada.minhabiblioteca.com.br/books/9788521638315. Acesso em: 31
out 2023. 
JR., D. Algoritmos e Programação de Computadores. Rio de Janeiro: GEN LTC, 2019. Disponível
em: https://integrada.minhabiblioteca.com.br/books/9788595150508. Acesso em: 31 out 2023. 
NASCIMENTO, J. N. R. D. Ciência da computação II. Londrina: Editora e Distribuidora Educacional
S.A., 2018. 2018 ISBN 9788552210924. Disponível em: https://biblioteca-
virtual.com/detalhes/ebook/6087055554aa8872fb666b55 . Acesso em: 31 out 2023. 
Bibliogra�a complementar 
ACM Computing Surveys. ISSN 1557-7341. Disponível em:
https://www.proquest.com/publication/47570?accountid=134629&decadeSelected=2020+-
+2029&yearSelected=2023&monthSelected=03&issueNameSelected=02023Y03Y01$23Mar+202
3$3b++Vol.+55+$283$29 . Acesso em: 31 out 2023. 
DALE, N.; LEWIS, J. Ciência da Computação, 4ª edição. Rio de Janeiro: LTC, 2010. Disponível em:
https://integrada.minhabiblioteca.com.br/books/9788521635215 . Acesso em: 31 out 2023. 
DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computabilidade.
v.5 (Livros didáticos informática UFRGS). Porto Alegre: Bookman, 2009. Disponível em:
https://integrada.minhabiblioteca.com.br/books/9788577808311 . Acesso em: 31 out 2023. 
SZWARCFITER, J. L.. Teoria Computacional de Grafos - Os Algoritmos. Rio de Janeiro: GEN LTC,
2018. Disponível em: https://integrada.minhabiblioteca.com.br/books/9788595155183 . Acesso
https://www.proquest.com/publication/2032439?accountid=134629
https://www.proquest.com/publication/2032439?accountid=134629
https://integrada.minhabiblioteca.com.br/books/9788521638315
https://integrada.minhabiblioteca.com.br/books/9788595150508
https://biblioteca-virtual.com/detalhes/ebook/6087055554aa8872fb666b55
https://biblioteca-virtual.com/detalhes/ebook/6087055554aa8872fb666b55
https://www.proquest.com/publication/47570?accountid=134629&decadeSelected=2020+-+2029&yearSelected=2023&monthSelected=03&issueNameSelected=02023Y03Y01$23Mar+2023$3b++Vol.+55+$283$29
https://www.proquest.com/publication/47570?accountid=134629&decadeSelected=2020+-+2029&yearSelected=2023&monthSelected=03&issueNameSelected=02023Y03Y01$23Mar+2023$3b++Vol.+55+$283$29
https://www.proquest.com/publication/47570?accountid=134629&decadeSelected=2020+-+2029&yearSelected=2023&monthSelected=03&issueNameSelected=02023Y03Y01$23Mar+2023$3b++Vol.+55+$283$29
https://integrada.minhabiblioteca.com.br/books/9788521635215
https://integrada.minhabiblioteca.com.br/books/9788577808311
https://integrada.minhabiblioteca.com.br/books/9788595155183
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
em: 31 out 2023. 
Aula 4
Algoritmos de divisão e conquista
Introdução
Olá, estudante! 
Nesta aula, abordaremos o método de desenvolvimento de algoritmos chamado “dividir e
conquistar” (divide-and-conquer). Esse método é dado por três características principais: dividir,
conquistar e combinar.  
Apesar do método dividir e conquistar ser direcionado para maior e�ciência na solução de
problemas, ressaltamos que nem sempre esse método produz os algoritmos mais e�cientes do
que os tradicionais, porém a sua implementação traz um approch característico da computação
paralela.  
Para ilustrar algumas aplicações com o método “dividir e conquistar”, abordaremos o problema
de ordenação de números por meio do Merge Sort e Quick Sort. Por �m, analisaremos a
complexidade dos algoritmos mencionados, mostrando a sua e�ciência no problema de
ordenação. 
Vamos começar? 
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Algoritmos por divisão e conquista
Dentro dos paradigmas de desenvolvimento de algoritmos, podemos destacar o método de
“dividir e conquistar”. Ele é composto por três fases: 
1 - Dividir: fase na qual o problema é quebrado até chegar em subproblemas semelhantes ao
problema inicial, cujas soluções podem ser obtidas de maneira mais simples. 
2 - Conquistar: responsável por resolver os subproblemas de forma recursiva. 
3 - Combinar: as soluções obtidas no passo anterior são combinadas para resolução do
problema inicial. 
Tradicionalmente na fase 1 - Dividir, cada problema é particionado ao meio tal que em
k = logn2
passos, obtemos instâncias únicas. Outra informação bastante relevante é que esse método é
construído nativamente para ser implementado em situações de paralelismo. Como primeiro
exemplo, vamos ordenar a lista de 5, 8 ,4, 3 e 2, usando o Merge Sort. 
Merge Sort 
Usaremos o Merge Sort para ordenar a sequência numérica 5, 8 ,4, 3 e 2. 
Dividimos a sequência numérica 5, 8 ,4, 3 e 2 ao meio, criando as duas subsequências 5, 8 e
4, 3, 2.  
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
A subsequência 5, 8 é novamente dividida em duas, obtendo somente os números 5 e 8. A
subsequência 4, 3, 2 também é dividida em duas: 4 e 3, 2. Na última divisão, obtemos os
números 3 e 2, totalizando 5 subsequências unitárias: 5, 8, 4, 3; 2. 
O próximo passo é juntar as sequências de maneira ordenada, obtendo as subsequências:
5, 8, 4, 2, 3. Repetindo o procedimento anterior, obtemos: 5, 8, 2, 3, 4. E, por último, a
sequência ordenada 2, 3, 4, 5, 8.  
A próxima �gura ilustra esse processo: 
Figura 1 |Merge Sort. Fonte: Elaborado pelo autor.
Seja n, inteiro positivo, o número de elementos da sequência que desejamos ordenar. Ao utilizar
o Merge Sort, a primeira etapa é a divisão. Nesse caso, dividimos até que restem somente
subsequência unitárias, ou seja, precisamos fazer k passos até que:
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Já nas fases de “conquistar” e “combinar”, o algoritmo realiza os mesmos , porém
ordenando ao juntar as subsequências. Em cada um dos passos dessa fase, o
número máximo de comparações é n, totalizando  operações nesse momento. Portanto,
podemos considerar o número total de operações realizadas pelo algoritmo:
Além da utilização nos algoritmos de ordenação como visto acima, o método de “dividir e
conquistar” também é usado em uma variedade de outros domínios. Um exemplo notável é o
algoritmo de pesquisa binária, que aproveita a natureza ordenada de uma lista para encontrar
rapidamente um elemento especí�co. Nesse algoritmo, o conjunto de dados é dividido
repetidamente ao meio até que o elemento desejado seja encontrado ou, então, seja
determinado que ele não existe na lista. A pesquisa binária tem uma complexidade de tempo de
O(log n), tornando-a uma escolha e�caz para grandes conjuntos de dados ordenados. Outro
exemplo do método de dividir e conquistar são em problemas de divisão de tarefas, como o
algoritmo Strassen para multiplicação de matrizes, e o algoritmo de Karatsuba para
multiplicação de números grandes. Esses algoritmos dividem os problemas em subproblemas
menores e utilizam estratégias inteligentes para reduzir o número de operações necessárias,
melhorando, signi�cativamente, a e�ciência.
Identi�cando problemas de D-C
n
2k = 1 ⇒  n =  2k ⇒  k  =  logn2
k  =  logn2
k  =  logn2
n logn2
logn2   +  n logn2   =  O (n logn2 )
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
As três condições abaixo sugerem os tipos de problemas que são resolvidos de forma e�ciente
pelo método de “dividir e conquistar” (D-C):
1 - O problema pode ser quebrado em subproblemas.
2 - Os subproblemas devem ser semelhantes.
3 - A junção das soluções dos subproblemas devem ser uma solução e�ciente do problema
geral.
Quando analisamos o problema de ordenar a sequência numérica 2, 3, 4, 5, 8, não é natural
pensarmos em fazer subsequências para realizar a ordenação. Isso acontece devido ao tamanho
da nossa sequência ser pequena, porém se você quer ordenar uma sequência com 1000
números, por exemplo, a divisão das subsequências é quase que automática. Veri�cando a
primeira característica acima no problema de ordenação da sequência, ao dividirmos as
subsequências comofoi mencionado anteriormente, os subproblemas a serem resolvidos são
semelhantes entre si, e ao problema inicial também, o que marca a presença da característica 2.
Ao ordenarmos as subsequências, elas são combinadas, organizando de maneira mais fácil a
sequência inicial. De fato, o problema de ordenação da sequência numérica possui as três
características acima. A �gura abaixo ilustra uma maneira de separar as fases do “dividir e
conquistar” usando como exemplo o Merge Sort.
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Figura 2 | Dividir e Conquistar. Fonte: Elaborado pelo autor.
Apesar do método de “dividir e conquistar” ser direcionado para maior e�ciência na solução
desse problema, ressaltamos que nem sempre esse método produz os algoritmos mais
e�cientes do que os tradicionais. Ao realizar um somatório de números, por exemplo, não
necessariamente a quebra em subsomas será mais e�ciente do que somar tudo por força bruta. 
Porém, esse método possui um approch voltado para paralelização da solução, isto é, imagine,
por exemplo, que no caso do Merge Sort as subsequências podem ser paralelizadas ao serem
quebradas, tornando o tempo de processamento muito menor.
Assumindo que a sequência tem tamanho n, dizemos que:
T(n) = a T(n/b) + f(n)
é a recorrência geral do método de dividir e conquistar. Aqui estamos considerando que n é uma
potência de b, e que e que a≥1, b>1. A função f é determinada pelo método de “dividir e
combinar” as soluções. Além disso, a ordem de grandeza de T(n) depende diretamente das
constantes a e b. Na próxima seção, usaremos T(n) para analisar a complexidade do Quick Sort.
O Quick Sort foi desenvolvido por C.A.R. Hoare, em 1960, quando visitou a Universidade de
Moscovo como estudante. Esse algoritmo é amplamente utilizado para ordenação e seleção de
elementos em sequências numéricas. O Quick Sort escolhe um elemento pivô na sequência
numérica, reorganiza os elementos para que os menores do que o pivô �quem à esquerda e os
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
maiores à direita. Em seguida, ele aplica recursivamente o mesmo processo às duas partições
resultantes. O Quick Sort é conhecido por sua e�ciência em média e tem uma complexidade de
tempo média de O(n log n), embora possa degradar para O(n²) no pior caso. Esse algoritmo será
explorado com mais detalhes na próxima sessão.
Análise de complexidade do Quick Sort
Quick Sort é outro algoritmo de ordenação importante baseado na abordagem dividir e
conquistar. Ao contrário do Merge Sort, que divide seus elementos de entrada de acordo com sua
posição, o Quick Sort os divide de acordo com seu valor. Uma partição é feita na sequência, e
esta é reordenada de maneira que todos os elementos à esquerda de algum elemento A[s] são
menores ou iguais a A[s], e todos os elementos à direita de A[s] são maiores ou iguais a A[s]. O
elemento A[s] é chamado de pivô, e existem algumas maneiras de fazer a escolha deste
elemento. O processo é repetido até a ordenação da sequência numérica. Vale ressaltar a
diferença com o Merge Sort, no Merge Sort a divisão em subproblemas é imediata e a ordenação
acontece na fase combinação, porém no Quick Sort a ordenação acontece na fase de divisão
sem necessidade da fase de combinação. Uma implementação simples do Quick Sort é dada
por:
quick_sort(A[l,...,r]):
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
se l<r faça # linha 1
s = Particao(A[l,..., r]) # linha 2
quick_sort(A[l, …, s-1]) # linha 3
quick_sort(A[s+1, …, r]) # linha 4
No algoritmo acima, usamos um outro algoritmo chamado de Particao(A[l, …, r]). Ele é
responsável por rearranjar a sequência de maneira que os elementos à esquerda do pivô sejam
menores ou iguais ao  pivô, e os elementos à direita deste sejam maiores ou iguais ao pivô. Nele,
fazemos somente comparações, atribuições e trocas de posições, fazendo a complexidade �nal
O(n). Escolhemos não o implementar aqui para não perdermos o foco principal.
O pior caso para o Quick Sort é quando o pivô é sempre escolhido nas iterações como sendo o
menor ou maior valor da sequência, gerando partições desbalanceadas. Nesse caso, levando em
consideração a complexidade do algoritmo Particao(A[l, …, r]), podemos escrever a complexidade
na iteração n como:
T(n) = T(n-1) + T(0) + O(n).
T(n) = T(n-1) + 0 +  n-1 = T(n-1) + n-1.
O O(n) vem da complexidade do algoritmo Particao(A[l, …, r]), que no pior caso (n-1) faz
comparações por etapa. Já T(0) vem da partição que possui somente um elemento e, portanto,
T(0)=0. E T(n-1) da partição com (n-1) elementos.
Já no caso melhor caso, o pivô é escolhido de maneira que os segmentos resultantes à esquerda
e à direita não ultrapassam (n/2). Portanto:
T(n) = T(n/2) + T(n/2) + O(n).
Usando o mesmo raciocínio acima, veri�camos que o caso médio também é na ordem de O(
). Assim, de maneira geral, o Quick Sort mostra-se uma boa escolha de algoritmo de
ordenação. Porém, vale ressaltar que ele não é estável. Além disso, o modo de particionar
é muito in�uente no desempenho do algoritmo. Só para título de curiosidade, os métodos mais
conhecidos para particionar são o de Lomuto e o de Hoare, sendo o de Hoare mais complicado
de implementar e, também, o mais e�ciente.
Videoaula: Algoritmos de divisão e conquista
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante!
T (n)  =  2 T (n/2)  +  O(n)  =  O(n logn2 )
n logn
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Neste vídeo, abordaremos o método de desenvolvimento de algoritmos chamado “dividir e
conquistar” (divide-and-conquer). O método é dado por três características principais: dividir,
conquistar e combinar. Aplicaremos esse método na ordenação de sequências numéricas por
meio do Merge Sort e Quick Sort, analisando as suas complexidades, e mostrando a sua
e�ciência no problema de ordenação. 
Saiba mais
Com a estratégia de dividir e conquistar, podemos implementar soluções mais e�cientes para
diversos problemas, como, por exemplo: Multiplicação de inteiros grandes e par de pontos mais
próximos.
Referências
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Algorithms 1999-4893. Disponível em: https://www.proquest.com/publication/2032439?
accountid=134629. Acesso em: 31 out 2023.
BACKES, A. R. Algoritmos e Estruturas de Dados em Linguagem C. Rio de Janeiro: LTC, 2023.
Disponível em: https://integrada.minhabiblioteca.com.br/books/9788521638315. Acesso em: 31
out 2023.
JR., D. Algoritmos e Programação de Computadores. Rio de Janeiro: GEN LTC, 2019. Disponível
em: https://integrada.minhabiblioteca.com.br/books/9788595150508. Acesso em: 31 out 2023.
NASCIMENTO, J. N. R. D. Ciência da computação II. Londrina: Editora e Distribuidora Educacional
S.A., 2018. 2018 ISBN 9788552210924. Disponível em: https://biblioteca-
virtual.com/detalhes/ebook/6087055554aa8872fb666b55 . Acesso em: 31 out 2023.
Bibliogra�a complementar
ACM Computing Surveys. ISSN 1557-7341. Disponível em:
https://www.proquest.com/publication/47570?accountid=134629&decadeSelected=2020+-
+2029&yearSelected=2023&monthSelected=03&issueNameSelected=02023Y03Y01$23Mar+202
3$3b++Vol.+55+$283$29 . Acesso em: 31 out 2023.
DALE, N.; LEWIS, J. Ciência da Computação, 4ª edição. Rio de Janeiro: LTC, 2010. Disponível em:
https://integrada.minhabiblioteca.com.br/books/9788521635215 . Acesso em: 31 out 2023.
DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computabilidade.
v.5 (Livros didáticos informática UFRGS). Porto Alegre: Bookman, 2009. Disponível em:
https://integrada.minhabiblioteca.com.br/books/9788577808311 . Acesso em: 31 out 2023.
SZWARCFITER, J. L. Teoria Computacional de Grafos - Os Algoritmos. Rio de Janeiro: GEN LTC,
2018. Disponível em: https://integrada.minhabiblioteca.com.br/books/9788595155183. Acesso
em: 31 out 2023.
https://www.proquest.com/publication/2032439?accountid=134629https://www.proquest.com/publication/2032439?accountid=134629
https://integrada.minhabiblioteca.com.br/books/9788521638315
https://integrada.minhabiblioteca.com.br/books/9788595150508
https://biblioteca-virtual.com/detalhes/ebook/6087055554aa8872fb666b55
https://biblioteca-virtual.com/detalhes/ebook/6087055554aa8872fb666b55
https://www.proquest.com/publication/47570?accountid=134629&decadeSelected=2020+-+2029&yearSelected=2023&monthSelected=03&issueNameSelected=02023Y03Y01$23Mar+2023$3b++Vol.+55+$283$29
https://www.proquest.com/publication/47570?accountid=134629&decadeSelected=2020+-+2029&yearSelected=2023&monthSelected=03&issueNameSelected=02023Y03Y01$23Mar+2023$3b++Vol.+55+$283$29
https://www.proquest.com/publication/47570?accountid=134629&decadeSelected=2020+-+2029&yearSelected=2023&monthSelected=03&issueNameSelected=02023Y03Y01$23Mar+2023$3b++Vol.+55+$283$29
https://integrada.minhabiblioteca.com.br/books/9788521635215
https://integrada.minhabiblioteca.com.br/books/9788577808311
https://integrada.minhabiblioteca.com.br/books/9788595155183
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Aula 5
Revisão da unidade
Classes de algoritmos
A área de computação é um campo dinâmico e em constante evolução, com uma ampla gama
de algoritmos e técnicas de programação. Nesse cenário, uma competência fundamental para
qualquer estudante que deseja atuar nesse domínio é a capacidade de identi�car a
complexidade de diversas classes de algoritmos e técnicas de programação. Essa habilidade
não só é crucial para o desenvolvimento de softwares mais e�cientes, mas também para
solucionar problemas complexos e tomar decisões na área de computação. Algoritmos mais
e�cientes requerem menos recursos e são executados em menos tempo, enquanto algoritmos
ine�cientes podem demandar uma quantidade signi�cativamente maior de recursos e tempo. 
Atualmente, com o paradigma de Cloud Computing, no qual se paga pelos recursos usados, a
capacidade de escolher algoritmos e�cientes pode fazer a diferença entre um sistema que
consome milhões de reais ou não. Por exemplo, em áreas como a inteligência arti�cial, a análise
de dados em grande escala e a simulação de sistemas complexos, os algoritmos desempenham
um papel crucial. Podemos citar os gastos no treinamento dos modelos LLMs (Large Language
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Models), que ultrapassam centenas de milhões de dólares. Uma escolha errada de técnicas de
algoritmos nesse caso, pode representar a perda de centenas de milhões de dólares. Algumas
das principais considerações que in�uenciam o custo de treinamento de um LLMs incluem:  
A duração do treinamento: o tempo necessário para treinar um LLMs é um fator importante
no custo. O treinamento pode levar semanas ou até meses, dependendo do hardware
utilizado e das con�gurações.  
Hardware e infraestrutura: o uso de hardware de alto desempenho, como GPUs ou TPUs, é
essencial para treinar modelos grandes de forma e�ciente. Isso envolve custos
signi�cativos de infraestrutura.  
Quantidade de dados de treinamento: LLMs exigem grandes conjuntos de dados para
treinamento. Adquirir, limpar e armazenar esses dados também pode ter custos.  
Despesas gerais: existem despesas gerais associadas ao treinamento de modelos, como
energia, resfriamento de servidores e manutenção de hardware.  
Então, ter a capacidade de identi�car a complexidade de algoritmos em todos os passos acima
permite você escolher as abordagens mais adequadas para lidar com esses desa�os, levando a
soluções mais e�cazes e resultados mais precisos, resultando em economia signi�cativa para a
empresa em que você trabalha.  
Com isso em mente, nesta aula, vamos desenvolver o estudo de caso que aborda algoritmos de
ordenação de dados e complexidade computacional. Eles são muito utilizados nas operações
básicas da computação, como, por exemplo: deleção, buscas e inserção. Como já discutimos
anteriormente, �ca claro que, analisar e saber aplicar a análise de complexidade de algoritmos
também no contexto de ordenação, pode ser trade off entre resolver ou não o problema em
questão. Mais ainda, analisando a complexidade dos algoritmos além da e�cácia, ganhamos
e�ciência na ordenação dos nossos dados.  
Portanto, esperamos que ao �nal desta unidade você esteja confortável não somente com a
implementação de técnicas dos algoritmos, mas também consiga analisar os seus algoritmos
para torná-los mais e�cientes.
Videoaula: Revisão da unidade
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
Olá, estudante!  
Neste vídeo, passaremos pelos tópicos: Ordenação de dados; Algoritmos de programação
dinâmica; Algoritmos Gulosos e Algoritmos de divisão e conquista. A ideia é pincelar os
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
momentos mais importantes que passamos nesta unidade de Teoria da Complexidade: projeto
de algoritmos, por meio de alguns exemplos de aplicação. Ao �nal, você estará apto a aplicar os
conceitos de análise de algoritmos em seus problemas reais. 
Estudo de caso
Em um mundo cada vez mais orientado por dados, a análise de complexidade de algoritmos de
ordenação é uma questão crítica para empresas e organizações que lidam com grandes volumes
de informações. Imagine uma empresa de análise de dados que coleta, processa e analisa dados
de clientes de todo o mundo. Eles enfrentam o desa�o de classi�car e organizar conjuntos de
dados massivos, muitas vezes com bilhões de registros, para fornecer insights valiosos aos seus
clientes. 
A empresa, que chamaremos de "DataCorp", trabalha com clientes de diversos setores, como
varejo, saúde e �nanças. Eles coletam dados de vendas, registros de pacientes e transações
�nanceiras, entre outras atividades. A e�ciência na classi�cação e ordenação desses dados é
fundamental para a precisão das análises e para atender às necessidades de seus clientes em
tempo real. 
A equipe de desenvolvimento da DataCorp enfrenta o desa�o de selecionar o algoritmo de
ordenação mais adequado para as necessidades especí�cas. Eles consideram o uso do
Quicksort, Heapsort e do Radix Sort, cada um com suas próprias características e
complexidades. A escolha do algoritmo errado pode resultar em atrasos signi�cativos no
processamento de dados, o que é inaceitável para uma empresa que atende a clientes que
exigem respostas rápidas. Portanto, vocês decidem que é essencial realizar uma análise
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
detalhada da complexidade dos algoritmos em questão. Isso envolve examinar não apenas o
desempenho médio, mas também os piores casos possíveis. O desempenho médio é importante
para avaliar a e�ciência geral, enquanto os piores casos são cruciais para garantir que o sistema
não sofra interrupções inesperadas em situações extremas. 
Quicksort: é conhecido por ser e�ciente em média e, geralmente, supera outros algoritmos
em muitas situações. No entanto, o pior caso ocorre quando o pivô escolhido divide os
dados em conjuntos extremamente desbalanceados. 
Heapsort: é e�ciente em todos os casos e não requer uma memória adicional, mas pode
ser um pouco mais lento em média. A equipe deve avaliar se a diferença de desempenho é
aceitável em comparação com a robustez do algoritmo.  
Radix Sort: é e�caz para ordenar números inteiros ou strings alfanuméricas, mas não é
apropriado para todos os tipos de dados. A equipe deve determinar se esse algoritmo é
apropriado para o escopo de dados que eles lidam. 
A equipe da DataCorp precisa analisar as complexidades teóricas dos algoritmos e, também,
considerar as características especí�cas de seus dados e a natureza das operações que
realizam. Essa análise ajudará a empresa a escolher o algoritmo de ordenação que atenda
melhor às suas necessidades, garantindo e�ciência, con�abilidade e capacidade de
escalabilidade,que são fundamentais em um contexto de big data. Além disso, é importante
destacar que, em muitas situações do mundo real, uma análise empírica dos algoritmos é
fundamental. Isso pode envolver simulação de testes práticos para veri�car como os algoritmos
se comportam em situações especí�cas. Dessa forma, a DataCorp pode tomar uma decisão
ainda mais fundamentada para atender às suas necessidades exclusivas.
_________
Re�ita
Ao estudar a complexidade de algoritmos, você desenvolve a capacidade de analisar e, por
consequência, escolher as melhores possibilidades de implementação para soluções reais, algo
que faz toda a diferença dado o cenário de grandes volumes de dados atualmente. Algoritmos
com implementações O(n²), ou O(n!) são tidos como algoritmos para �ns didáticos, pois em sua
maioria são fáceis de implementar e muito lerdos. Porém, até mesmo alguns casos O(n log n)
que a princípio parecem bons, dependendo do volume de dados, eles acabam sendo inviáveis
sua aplicação. Existem ainda situações em que os algoritmos são apropriados para tipos
especí�cos de dados, mas não são apropriados para todos os tipos de dados. Isso deve ser
levado em consideração para analisar e de�nir uma estratégia que atenda à solução para a sua
demanda. Além disso, é importante conhecer a diferença de crescimento entre as funções mais
usadas dentro da análise de complexidade de algoritmos. Para isso, use um software de grá�co
e faça alguns dos grá�cos das funções de complexidades mais usadas para ter certeza quando
for comparar os algoritmos. 
Videoaula: Resolução do estudo de caso
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Este conteúdo é um vídeo!
Para assistir este conteúdo é necessário que você acesse o AVA pelo
computador ou pelo aplicativo. Você pode baixar os vídeos direto no
aplicativo para assistir mesmo sem conexão à internet.
O Quicksort é um algoritmo que usa a técnica de dividir e conquistar e tem uma complexidade
média de tempo de O(n log n), o que o torna um dos algoritmos de ordenação mais e�ciente em
média. No entanto, em seu pior caso, ele pode ter uma complexidade de tempo de O(n²),
tornando-se menos e�ciente. O pior caso ocorre quando o pivô escolhido em cada etapa divide a
lista em conjuntos extremamente desbalanceados, resultando em uma árvore de recursão
profundamente enraizada. Embora o pior caso seja uma possibilidade, ele é raro na prática e
pode ser mitigado por escolhas de pivô mais inteligentes, como pivôs medianos.  
O Heapsort é um algoritmo de ordenação e�ciente com análises de complexidade consistentes
em todos os casos. Tanto em seu caso médio quanto no pior caso, ele possui uma complexidade
de tempo de O(n log n), em que "n" é o número de elementos a serem ordenados. Isso signi�ca
que, independentemente da distribuição dos dados de entrada, o desempenho do Heapsort
permanece constante e e�ciente. Ao contrário de outros algoritmos, como o Quicksort, que
podem enfrentar um desempenho ruim no pior caso, o Heapsort oferece uma garantia de
desempenho estável. Ele também é e�ciente em termos de espaço, uma vez que não requer
memória adicional, além daquela usada para armazenar os próprios elementos a serem
classi�cados.  
O Radix Sort é um algoritmo de ordenação e�caz para números inteiros ou strings alfanuméricas,
que têm complexidade constante de O(n x k) para todos os casos, em que "n" representa o
número de elementos a serem ordenados e "k" é o número médio de dígitos nos elementos.
Portanto, o Radix Sort não é afetado por desempenho ruim no pior caso, já que o seu tempo de
execução permanece inalterado em qualquer situação. No entanto, é importante destacar que o
desempenho do Radix Sort depende diretamente da magnitude dos dígitos a serem ordenados.
Se "k" for signi�cativamente grande, o algoritmo pode se tornar menos e�ciente. O Radix Sort é
frequentemente usado em situações em que a magnitude dos números é limitada, como
classi�car números inteiros com um número �xo de dígitos.  
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Tabela 1 | Ordem de grandezas das funções de complexidade. Fonte: Elaborado pelo autor. 
Levando em consideração as análises de complexidade acima, a escolha para algoritmo geral é
o Heap Sort. Em casos especí�cos, como ordenação de números inteiros ou strings
alfanuméricas, em que o tamanho da string não é muito grande, o Radix Sort é um algoritmo de
ordenação e�ciente. Por exemplo, quando k = 1 Mi, ou seja, temos uma string com 1 Mi de
elementos, no caso de n = 1 Mi, temos n x k = n² = 1.000.000.000.000, o que torna o caso muito
custoso. Logo, é necessário fazer uma escolha adequada do tamanho de k, na qual podemos
usar o Radix Sort.
Olá, estudante!
Clique Aqui! E acesse o roteiro de aula prática.
Resumo visual
https://cm-kls-content.s3.amazonaws.com/AMPLI/RAP/ANALISE_DE_COMPUTABILIDADE_E_COMPLEXIDADE_DE_ALGORITMOS/RAP.pdf
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Resumidamente, na unidade 4 destacamos os aspectos mais importantes de cada tema.
Disciplina
Análise de Computabilidade e
Complexidade de Algoritmos
Referências
BACKES, A. R. Algoritmos e Estruturas de Dados em Linguagem C. Rio de Janeiro: LTC, 2023.
Disponível em: https://integrada.minhabiblioteca.com.br/books/9788521638315. Acesso em: 31
out 2023.
JR., D. Algoritmos e Programação de Computadores. Rio de Janeiro: GEN LTC, 2019. Disponível
em: https://integrada.minhabiblioteca.com.br/books/9788595150508. Acesso em: 31 out 2023.
https://integrada.minhabiblioteca.com.br/books/9788521638315
https://integrada.minhabiblioteca.com.br/books/9788595150508