Galeria de mapas mentais Introdução aos Algoritmos
Resumo do conhecimento introdutório sobre algoritmos, que introduz o conceito de algoritmos, expressões de algoritmos, análise de complexidade de algoritmos, etapas de design de algoritmos, etc. É a base para o design e análise de algoritmos de computador e estabelece as bases para que os alunos dominem vários algoritmos específicos no futuro. É um conteúdo importante que deve ser aprendido no processo de aprendizagem de algoritmos.
Editado em 2024-03-02 22:28:38Microbiologia medica, Infezioni batteriche e immunità riassume e organizza i punti di conoscenza per aiutare gli studenti a comprendere e ricordare. Studia in modo più efficiente!
La teoria cinetica dei gas rivela la natura microscopica dei fenomeni termici macroscopici e le leggi dei gas trovando la relazione tra quantità macroscopiche e quantità microscopiche. Dal punto di vista del movimento molecolare, vengono utilizzati metodi statistici per studiare le proprietà macroscopiche e modificare i modelli di movimento termico delle molecole di gas.
Este é um mapa mental sobre uma breve história do tempo. "Uma Breve História do Tempo" é um trabalho científico popular com influência de longo alcance. Ele não apenas introduz os conceitos básicos da cosmologia e da relatividade, mas também discute os buracos negros e a expansão. Do universo. questões científicas de ponta, como inflação e teoria das cordas.
Microbiologia medica, Infezioni batteriche e immunità riassume e organizza i punti di conoscenza per aiutare gli studenti a comprendere e ricordare. Studia in modo più efficiente!
La teoria cinetica dei gas rivela la natura microscopica dei fenomeni termici macroscopici e le leggi dei gas trovando la relazione tra quantità macroscopiche e quantità microscopiche. Dal punto di vista del movimento molecolare, vengono utilizzati metodi statistici per studiare le proprietà macroscopiche e modificare i modelli di movimento termico delle molecole di gas.
Este é um mapa mental sobre uma breve história do tempo. "Uma Breve História do Tempo" é um trabalho científico popular com influência de longo alcance. Ele não apenas introduz os conceitos básicos da cosmologia e da relatividade, mas também discute os buracos negros e a expansão. Do universo. questões científicas de ponta, como inflação e teoria das cordas.
Introdução aos Algoritmos
Conceito de algoritmo
O significado básico do algoritmo
um método para resolver um determinado problema
Definição de algoritmo
descrição informal
Um algoritmo é um conjunto finito de regras bem formadas. Ele especifica uma série de operações para resolver um tipo específico de problema. É um método ou processo para resolver um problema. É uma sequência de instruções que satisfazem a entrada, a saída e a certeza. e finitude.
Entrada: Existem zero ou mais quantidades externas que servem como entrada para o algoritmo.
Saída: O algoritmo produz pelo menos uma quantidade como saída.
Determinístico: Cada instrução que compõe o algoritmo é clara e inequívoca.
Finitude: Cada instrução no algoritmo tem um número limitado de execuções e o tempo para executar cada instrução é limitado.
Algoritmos e Programas
Um programa é a implementação específica de um algoritmo em uma determinada linguagem de programação.
O programa não precisa satisfazer a propriedade do algoritmo (4), ou seja, finitude, como um sistema operacional.
Programa = estrutura de dados do algoritmo da linguagem de programação
O escopo da pesquisa de algoritmos
Cálculos Numéricos
Equações lineares não lineares, interpolação, diferencial integral
cálculos não numéricos
Classificação, otimização, coloração, caminho, travessia, aprendizado de máquina, mineração de dados
propriedades de algoritmos
correção
Se, para qualquer entrada válida, o algoritmo sempre der a resposta correta ao problema dentro de um tempo limitado, então o algoritmo para resolver o problema é considerado correto.
Isso se refere principalmente à correção matemática do algoritmo. Porque a correção matemática é a base para a correção do programa. Ao formular um algoritmo, forneça uma prova matemática de sua correção.
carga de trabalho
Medido pelo tempo de execução
Depende da máquina de execução específica, não é bom
Medido pelo número de operações básicas
Independente do computador em que é executado
Uso de espaço
O espaço necessário, exceto o espaço de armazenamento para programas e dados de entrada
Funciona no local: o uso de espaço extra é uma função constante do tamanho da entrada
simplicidade
O algoritmo deve ser intuitivo, claro e fácil de ler. Um algoritmo simples deve ser fácil de provar sua correção e fácil de analisar a carga de trabalho.
otimalidade
Um mecanismo abstrato para expressar algoritmos
Abstração de nível de linguagem
linguagem de programação de alto nível
1. Perto da linguagem algorítmica, fácil de aprender e dominar
2. Fornece aos programadores um ambiente e ferramentas de programação estruturados. O programa tem boa legibilidade, facilidade de manutenção e alta confiabilidade.
3. Não depende de linguagem de máquina, tem boa portabilidade de programa e alta capacidade de reutilização
4. O compilador lida com questões triviais, portanto, o grau de automação é alto, o ciclo de desenvolvimento é curto e a qualidade do programa é alta.
abstração de nível de dados
tipo de dados abstrato
Um tipo de dados abstrato é um modelo de dados de um algoritmo junto com um conjunto de operações definidas no modelo que são os blocos de construção do algoritmo.
vantagem
(1) O design de nível superior do algoritmo é separado da implementação de nível inferior;
(2) O projeto do algoritmo é separado do projeto da estrutura de dados, permitindo a livre escolha da estrutura de dados;
(3) O modelo de dados e as operações no modelo são unificados no ADT, o que facilita o equilíbrio entre o consumo de espaço e tempo;
(4) Algoritmos expressos em tipos de dados abstratos têm boa manutenção;
(5) O algoritmo é naturalmente modular;
(6) Fornecer formas e ferramentas eficazes para o refinamento e a modularização graduais de cima para baixo;
(7) O algoritmo possui uma estrutura clara e camadas distintas, o que facilita a prova da correção do algoritmo e a análise da complexidade.
Descrever algoritmo
Java
Estrutura do programa
tipo de dados
método
anormal
Aulas Java
método geral
coleta de lixo
recursão
Etapas do projeto de algoritmo
Etapas básicas de design de algoritmo
1. declaração do problema
2. Modelagem
3. projeto de algoritmo
4. Prova de correção do algoritmo
5. Implementação de algoritmo
6. Análise de complexidade de algoritmo
7. Teste experimental
8. Documentação
Análise de complexidade de algoritmo
Razões de análise
Para que um algoritmo processe com sucesso uma entrada específica, o espaço de memória e o tempo de execução exigidos pelo algoritmo precisam ser estimados ou limitados.
Pode comparar quantitativamente a eficiência de diferentes algoritmos para o mesmo problema
Classificação de Complexidade
Algoritmo de complexidade de tempo polinomial
Algoritmo de complexidade de tempo exponencial
Testes e análises experimentais
razão
Experimente para verificar a exatidão do algoritmo
Determinando a qualidade experimental de um algoritmo
Determinar os limites computacionais de um algoritmo
método
Pergunta de escolha: O que testar, propósito do teste
Estime o tempo médio de execução assintótica de um algoritmo
Compare o desempenho de algoritmos semelhantes para uma determinada entrada
Experimente para determinar parâmetros no algoritmo
Para algoritmos de aproximação, quão próximos os resultados do teste estão do valor ideal
Determinar métricas
Tempo real de execução
fatores de interferência
Outros programas em execução no computador
impacto no cache
utilização de memória
Gerar dados de teste
quantidade suficiente
escalas diferentes
Distribuição diferente
Programar e executar
programação
Garanta a consistência do nível de programação
correr
Garanta um ambiente de computação limpo e reduza o ruído dos dados
análise de dados
teste de razão
Teste de potência
Documentação
Descrição e análise do problema
Modelagem e Resolução
Projeto de algoritmo e processo de prova de correção
Análise de complexidade de algoritmo
Registro de resultados de teste e relatório de análise
Requisitos de entrada/saída e descrição do formato
Análise de complexidade de algoritmo
Use T(N,I) para representar a complexidade de tempo do algoritmo A em um computador abstrato.
N: o tamanho do problema a ser resolvido
DN: o conjunto de todas as entradas possíveis de tamanho N
P(DN): Distribuição de probabilidade de DN
I: entrada para o algoritmo, I∈DN
medida de complexidade de tempo
Descrição do símbolo
Ó
definição
definição formal matemática
O(g(n)) são todas funções com g(n) como limite superior
compreensão simbólica
Regras aritméticas
Prova para (1)
Ah
definição
definição formal matemática
θ
definição
definição formal matemática
ó
definição