EITC/IS/CCTF Computational Complexity Theory Fundamentals é o programa europeu de certificação de TI sobre aspectos teóricos dos fundamentos da ciência da computação que também são uma base da criptografia de chave pública assimétrica clássica amplamente utilizada na Internet.
O currículo dos Fundamentos da Teoria da Complexidade Computacional do EITC/IS/CCTF abrange o conhecimento teórico sobre os fundamentos da ciência da computação e modelos computacionais sobre conceitos básicos como máquinas de estado finito determinísticas e não determinísticas, linguagens regulares, gramática livre de contexto e teoria das linguagens, teoria dos autômatos, Turing Máquinas, resolvebilidade de problemas, recursão, lógica e complexidade de algorítmica para aplicações fundamentais de segurança dentro da seguinte estrutura, englobando conteúdo didático em vídeo abrangente como referência para esta Certificação EITC.
A complexidade computacional de um algoritmo é a quantidade de recursos necessários para operá-lo. Os recursos de tempo e memória recebem atenção especial. A complexidade de um problema é definida como a complexidade dos melhores algoritmos para resolvê-lo. A análise de algoritmos é o estudo da complexidade de algoritmos dados explicitamente, enquanto a teoria da complexidade computacional é o estudo da complexidade das soluções de problemas com os algoritmos mais conhecidos. Ambos os domínios estão interligados porque a complexidade de um algoritmo é sempre uma restrição superior na complexidade do problema que ele resolve. Além disso, frequentemente é necessário comparar a complexidade de um determinado algoritmo com a complexidade do problema a ser resolvido ao construir algoritmos eficientes. Na maioria das circunstâncias, a única informação disponível sobre a dificuldade de um problema é que ela é menor do que a complexidade das técnicas conhecidas mais eficientes. Como resultado, há muita sobreposição entre a análise de algoritmos e a teoria da complexidade.
A teoria da complexidade desempenha um papel importante não apenas nos fundamentos dos modelos computacionais como base para a ciência da computação, mas também nos fundamentos da criptografia assimétrica clássica (a chamada criptografia de chave pública) que é amplamente difundida nas redes modernas, especialmente na Internet. A criptografia de chave pública é baseada na dificuldade computacional de certos problemas matemáticos assimétricos como por exemplo a fatoração de grandes números em seus fatores primos (esta operação é um problema difícil na classificação da teoria da complexidade, pois não se conhecem algoritmos clássicos eficientes para resolver com recursos escalando polinomialmente em vez de exponencialmente com o aumento do tamanho da entrada do problema, o que contrasta com uma operação reversa muito simples de multiplicar por fatores primos conhecidos para fornecer o grande número original). Usando esta assimetria em uma arquitetura de criptografia de chave pública (definindo uma relação computacionalmente assimétrica entre a chave pública, que pode ser facilmente computada a partir de uma chave privada, enquanto a chave privada não pode ser facilmente computada a partir de uma chave pública, pode-se anunciar a chave pública e permitir que outros lados da comunicação a utilizem para criptografia assimétrica de dados, que só poderão ser descriptografados com a chave privada acoplada, não disponível computacionalmente para terceiros, tornando a comunicação segura).
A teoria da complexidade computacional foi desenvolvida principalmente em conquistas de pioneiros da ciência da computação e algorítmica, como Alan Turing, cujo trabalho foi fundamental para quebrar a cifra Enigma da Alemanha nazista, que desempenhou um papel profundo na vitória dos aliados na Segunda Guerra Mundial. Criptoanálise com o objetivo de conceber e automatizar os processos computacionais de análise de dados (principalmente comunicação criptografada) a fim de descobrir as informações ocultas foi usada para violar sistemas criptográficos e obter acesso ao conteúdo da comunicação criptografada, geralmente de importância militar estratégica. Foi também a criptoanálise que catalisou o desenvolvimento dos primeiros computadores modernos (que foram inicialmente aplicados a um objetivo estratégico de quebra de código). O Colosso Britânico (considerado o primeiro computador eletrônico e de programação moderno) foi precedido pela “bomba” polonesa, um dispositivo computacional eletrônico projetado por Marian Rejewski para auxiliar na quebra de cifras da Enigma, e entregue à Grã-Bretanha pela inteligência polonesa juntamente com a máquina de criptografia alemã Enigma capturada, depois que a Polônia foi invadida pela Alemanha em 1939. Com base nesse dispositivo, Alan Turing desenvolveu sua contraparte mais avançada para quebrar com sucesso a comunicação criptografada alemã, que mais tarde foi desenvolvida em computadores modernos.
Como a quantidade de recursos necessários para executar um algoritmo varia com o tamanho da entrada, a complexidade geralmente é expressa como uma função f(n), onde n é o tamanho da entrada e f(n) é a complexidade do pior caso ( a quantidade máxima de recursos necessários em todas as entradas de tamanho n) ou a complexidade de caso médio (a média da quantidade de recursos em todas as entradas de tamanho n). O número de operações elementares necessárias em uma entrada de tamanho n é comumente declarado como complexidade de tempo, onde acredita-se que as operações elementares levam um tempo constante em um computador específico e mudam apenas por um fator constante quando executadas em uma máquina diferente. A quantidade de memória requerida por um algoritmo em uma entrada de tamanho n é conhecida como complexidade de espaço.
O tempo é o recurso mais comumente considerado. Quando o termo “complexidade” é usado sem qualificador, geralmente se refere à complexidade do tempo.
As unidades tradicionais de tempo (segundos, minutos e assim por diante) não são empregadas na teoria da complexidade, pois dependem muito do computador escolhido e do avanço da tecnologia. Por exemplo, um computador hoje pode executar um algoritmo substancialmente mais rápido do que um computador da década de 1960, mas isso se deve a avanços tecnológicos no hardware do computador, e não a uma qualidade inerente do algoritmo. O objetivo da teoria da complexidade é quantificar as necessidades de tempo inerentes dos algoritmos, ou as limitações de tempo fundamentais que um algoritmo imporia a qualquer computador. Isso é feito contando quantas operações básicas são executadas durante o cálculo. Esses procedimentos são comumente chamados de etapas porque são considerados como tendo tempo constante em uma máquina específica (ou seja, não são afetados pela quantidade de entrada).
Outro recurso crucial é a quantidade de memória do computador necessária para executar algoritmos.
Outro recurso muito utilizado é a quantidade de operações aritméticas. Nesse cenário, o termo “complexidade aritmética” é usado. A complexidade de tempo é geralmente o produto da complexidade aritmética por um fator constante se uma restrição superior no tamanho da representação binária dos números que ocorrem durante uma computação for conhecida.
O tamanho dos inteiros utilizados durante uma computação não é restrito para muitos métodos, e não é realista supor que as operações aritméticas requerem uma quantidade fixa de tempo. Como resultado, a complexidade de tempo, também conhecida como complexidade de bits, pode ser significativamente maior que a complexidade aritmética. A dificuldade aritmética de calcular o determinante de uma matriz inteira nn, por exemplo, é O(n^3) para técnicas padrão (eliminação gaussiana). Como o tamanho dos coeficientes pode expandir exponencialmente durante o cálculo, a complexidade de bits dos mesmos métodos é exponencial em n. Se essas técnicas forem usadas em conjunto com a aritmética multimodular, a complexidade do bit pode ser reduzida para O(n^4).
A complexidade de bits, em termos formais, refere-se ao número de operações em bits necessárias para executar um algoritmo. Ele iguala a complexidade temporal até um fator constante na maioria dos paradigmas de computação. O número de operações em palavras de máquina exigidas pelos computadores é proporcional à complexidade dos bits. Para modelos realistas de computação, a complexidade de tempo e a complexidade de bits são, portanto, idênticas.
O recurso que geralmente é considerado na classificação e pesquisa é a quantidade de comparações de entradas. Se os dados estiverem bem organizados, este é um bom indicador da complexidade do tempo.
Em todas as entradas potenciais, é impossível contar o número de passos em um algoritmo. Como a complexidade de uma entrada aumenta com seu tamanho, ela é comumente representada como uma função do tamanho da entrada n (em bits) e, portanto, a complexidade é uma função de n. Para as entradas de mesmo tamanho, no entanto, a complexidade de um algoritmo pode variar substancialmente. Como resultado, uma variedade de funções de complexidade são empregadas rotineiramente.
A complexidade do pior caso é a soma de toda a complexidade para todas as entradas de tamanho n, enquanto a complexidade do caso médio é a soma de toda a complexidade para todas as entradas de tamanho n (isso faz sentido, pois o número de entradas possíveis de um determinado tamanho é finito). Quando o termo “complexidade” é usado sem ser definido, a complexidade de tempo do pior caso é levada em consideração.
A complexidade do pior caso e do caso médio são notoriamente difíceis de calcular corretamente. Além disso, esses valores exatos têm pouca aplicação prática porque qualquer mudança na máquina ou no paradigma de cálculo variaria ligeiramente a complexidade. Além disso, o uso de recursos não é crucial para valores pequenos de n, portanto, a facilidade de implementação geralmente é mais atraente do que a baixa complexidade para n pequeno.
Por essas razões, mais atenção é dada ao comportamento da complexidade para n alto, ou seja, seu comportamento assintótico à medida que n se aproxima do infinito. Como resultado, a notação O grande é comumente usada para indicar complexidade.
Modelos computacionais
A escolha de um modelo computacional, que consiste em especificar as operações essenciais que são executadas em uma unidade de tempo, é crucial na determinação da complexidade. Isso às vezes é chamado de máquina de Turing multifita quando o paradigma de computação não é especificamente descrito.
Um modelo de computação determinístico é aquele em que os estados subsequentes da máquina e as operações a serem executadas são inteiramente definidas pelo estado anterior. Funções recursivas, cálculo lambda e máquinas de Turing foram os primeiros modelos determinísticos. Máquinas de acesso aleatório (também conhecidas como máquinas RAM) são um paradigma popular para simular computadores do mundo real.
Quando o modelo de computação não está definido, geralmente é assumida uma máquina de Turing multitape. Em máquinas de Turing multitape, a complexidade de tempo é a mesma que em máquinas de RAM para a maioria dos algoritmos, embora uma atenção considerável em como os dados são armazenados na memória pode ser necessária para alcançar essa equivalência.
Várias escolhas podem ser feitas em algumas etapas da computação em um modelo de computação não determinístico, como máquinas de Turing não determinísticas. Na teoria da complexidade, todas as opções viáveis são consideradas ao mesmo tempo, e a complexidade de tempo não determinística é a quantidade de tempo necessária quando as melhores escolhas são sempre feitas. Em outras palavras, a computação é feita concorrentemente em tantos processadores (idênticos) quantos forem necessários, e o tempo de computação não determinístico é o tempo gasto pelo primeiro processador para completar a computação. Esse paralelismo pode ser usado na computação quântica usando estados emaranhados superpostos ao executar algoritmos quânticos especializados, como a fatoração de números inteiros minúsculos de Shor, por exemplo.
Mesmo que tal modelo de computação não seja praticável atualmente, ele tem significado teórico, particularmente em relação ao problema P = NP, que pergunta se as classes de complexidade produzidas usando “tempo polinomial” e “tempo polinomial não determinístico” como limites são os mesmos. Em um computador determinístico, simular um algoritmo NP requer “tempo exponencial”. Se uma tarefa pode ser resolvida em tempo polinomial em um sistema não determinístico, ela pertence à classe de dificuldade NP. Se um problema está em NP e não é mais fácil do que qualquer outro problema NP, diz-se que é NP-completo. O problema da mochila, o problema do caixeiro viajante e o problema da satisfatibilidade booleana são todos problemas combinatórios NP-completos. O algoritmo mais conhecido tem complexidade exponencial para todos esses problemas. Se qualquer um desses problemas pudesse ser resolvido em tempo polinomial em uma máquina determinística, então todos os problemas NP também poderiam ser resolvidos em tempo polinomial, e P = NP seria estabelecido. A partir de 2017, é amplamente assumido que P NP, o que implica que as piores situações de problemas NP são fundamentalmente difíceis de resolver, ou seja, levam muito mais tempo do que qualquer intervalo de tempo viável (décadas) dados comprimentos de entrada interessantes.
Computação paralela e distribuída
A computação paralela e distribuída envolve a divisão do processamento entre vários processadores que operam todos ao mesmo tempo. A distinção fundamental entre os vários modelos é o método de envio de dados entre processadores. A transmissão de dados entre processadores é normalmente muito rápida em computação paralela, enquanto a transferência de dados entre processadores em computação distribuída é feita através de uma rede e, portanto, é substancialmente mais lenta.
Uma computação em N processadores leva pelo menos o quociente por N do tempo que leva em um único processador. Na realidade, como algumas subtarefas não podem ser paralelizadas e alguns processadores podem precisar esperar por um resultado de outro processador, esse limite teoricamente ideal nunca será alcançado.
A principal questão de complexidade é, portanto, desenvolver algoritmos para que o produto do tempo de computação pelo número de processadores seja o mais próximo possível do tempo necessário para realizar a mesma computação em um único processador.
Computação quântica
Um computador quântico é um computador com um modelo de computação baseado em mecânica quântica. A tese de Church-Turing é válida para computadores quânticos, implicando que qualquer problema que um computador quântico possa resolver também pode ser resolvido por uma máquina de Turing. No entanto, algumas tarefas podem teoricamente ser resolvidas usando um computador quântico em vez de um computador clássico com uma complexidade temporal significativamente menor. Por enquanto, isso é estritamente teórico, pois ninguém sabe como desenvolver um computador quântico prático.
A teoria da complexidade quântica foi criada para investigar os diferentes tipos de problemas que podem ser resolvidos por computadores quânticos. É utilizado na criptografia pós-quântica, que é o processo de criação de protocolos criptográficos resistentes a ataques de computadores quânticos.
Complexidade do problema (limites inferiores)
O ínfimo das complexidades dos algoritmos que podem resolver o problema, incluindo técnicas não descobertas, é a complexidade do problema. Como resultado, a complexidade de um problema é igual à complexidade de qualquer algoritmo que o resolva.
Como resultado, qualquer complexidade dada em notação O grande representa uma complexidade tanto do algoritmo quanto do problema que o acompanha.
Por outro lado, obter limites inferiores não triviais na complexidade do problema é muitas vezes difícil e existem poucas estratégias para fazê-lo.
Para resolver a maioria dos problemas, todos os dados de entrada devem ser lidos, o que leva um tempo proporcional à magnitude dos dados. Como resultado, tais problemas têm pelo menos uma complexidade linear, ou, em notação ômega grande, uma complexidade de Ω(n).
Alguns problemas, como os de álgebra computacional e geometria algébrica computacional, têm soluções muito grandes. Como a saída deve ser escrita, a complexidade é limitada pelo tamanho máximo da saída.
O número de comparações necessárias para um algoritmo de ordenação tem um limite inferior não linear de Ω(nlogn). Como resultado, os melhores algoritmos de ordenação são os mais eficientes, pois sua complexidade é O(nlogn). O fato de haver n! maneiras de organizar n coisas leva a esse limite inferior. Porque cada comparação divide esta coleção de n! ordens em duas partes, o número de N comparações necessárias para distinguir todas as ordens deve ser 2N > n!, implicando O(nlogn) pela fórmula de Stirling.
Reduzir um problema a outro problema é uma estratégia comum para obter restrições de complexidade reduzida.
Desenvolvimento de algoritmo
Avaliar a complexidade de um algoritmo é um elemento importante do processo de design, pois fornece informações úteis sobre o desempenho que pode ser esperado.
É um equívoco frequente que, como resultado da lei de Moore, que prevê o crescimento exponencial do poder dos computadores modernos, a avaliação da complexidade dos algoritmos se tornará menos relevante. Isso é incorreto porque o aumento da potência permite o processamento de grandes quantidades de dados (big data). Por exemplo, qualquer algoritmo deve funcionar bem em menos de um segundo ao classificar alfabeticamente uma lista de algumas centenas de entradas, como a bibliografia de um livro. Por outro lado, para um milhão de entradas (por exemplo, os números de telefone de uma grande cidade), os algoritmos básicos que exigem comparações O(n2) teriam que realizar um trilhão de comparações, o que levaria três horas a uma velocidade de 10 milhões de comparações por segundo. Quicksort e merge sort, por outro lado, requerem apenas comparações nlogn (como complexidade de caso médio para o primeiro, como complexidade de pior caso para o último). Isso produz cerca de 30,000,000 comparações para n = 1,000,000, o que levaria apenas 3 segundos a 10 milhões de comparações por segundo.
Como resultado, avaliar a complexidade pode permitir a eliminação de muitos algoritmos ineficientes antes da implementação. Isso também pode ser usado para ajustar algoritmos complexos sem precisar testar todas as variantes possíveis. O estudo da complexidade permite focar o esforço para aumentar a eficiência de uma implementação determinando as etapas mais caras de um algoritmo complexo.
Para se familiarizar em detalhes com o currículo de certificação, você pode expandir e analisar a tabela abaixo.
O Currículo de Certificação de Fundamentos da Teoria da Complexidade Computacional EITC/IS/CCTF faz referência a materiais didáticos de acesso aberto em formato de vídeo. O processo de aprendizagem é dividido em uma estrutura passo a passo (programas -> aulas -> tópicos) que cobre partes curriculares relevantes. Consultoria ilimitada com especialistas de domínio também são fornecidos.
Para obter detalhes sobre o procedimento de Certificação, verifique Como funciona.
Materiais de leitura do currículo de apoio primário
S. Arora, B. Barak, Complexidade Computacional: Uma Abordagem Moderna
https://theory.cs.princeton.edu/complexity/book.pdf
Materiais de leitura do currículo de apoio secundário
O. Goldreich, Introdução à Teoria da Complexidade:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Materiais de leitura curricular de apoio sobre matemática discreta
J. Aspnes, Notas sobre Matemática Discreta:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
Materiais de leitura curricular de apoio sobre teoria dos grafos
R. Diestel, Teoria dos Grafos:
https://diestel-graph-theory.com/
Baixe os materiais preparatórios de autoaprendizagem off-line completos para o programa EITC/IS/CCTF Computational Complexity Theory Fundamentals em um arquivo PDF
Materiais preparatórios EITC/IS/CCTF – versão padrão
Materiais preparatórios EITC/IS/CCTF – versão estendida com perguntas de revisão