455365337

Processamento, Consumo de Memória, Eficiência de Algoritmos, Notação Assintótica. Algorítmo - Método para resolução de Problemas Estrutura de Dados - Método para Armazenar Dados Algoritmos + Estrutura de Dados = Programa de Computador (Software) Algoritmos + Estrutura de Dados Otimizados Tempo de Processamento Menor Otimizadas Menor Consumo de Memória Algoritmos + Estrutura de Dados Otimizados Tempo de Processamento Menor Otimizadas Menor Consumo de Memória Problema resolvido de forma mais Eficiente Tempo de Processamento Dependia da velocidade que se girava esta Manivela Engenho Analítico - Charles Babbage 1864 Quantas Instruções são executadas para uma Variável de Entrada N ? int contador= 0; for (int i = 0; i < N; i++) contador++; Operação Frequência Declaração de Variáveis 2 Atribuição 2 Comparação (Menor que) N+1 Soma N Incremento (Soma) N Equação de Custo de Processamento T(N) Neste caso a equação que representa o processamento em função da Variável de Entrada N é : T(N) = N + N + N + 1 + 2 + 2 = 3N + 5 O Custo de Processamento T(N) tenta prever o Custo de Processamento a partir das Variáveis de Entrada. * se o algoritmo for uma multiplicação N será o tamanho dos números; se for uma ordenação será o no. de elementos a serem ordenados, se for um Grafo será o no. de Nós e Vértices etc. Notação Assintótica Algo 1 Eficiência 1 …

dois primeiros termos podem ser desprezados Notação Assintótica  Notação matemática usada para analisar o comportamento das funções    Utilizada para descrever o uso de recursos computacionais Notação: Grade-O ou Big-O Permite  Prever o comportamento do algoritmo  Determinar qual algoritmo utilizar Notação Assintótica  Dominância Assintótica  Uma função f(n) domina assintoticamente outra função g(n) se existem duas constantes…

Defina complexidade computacional e assintótica. Como uma difere da outra? A complexidade computacional indica quanto esforço é necessário para se aplicar um algoritmo, ou quão custoso ele é. Esta complexidade está ligada às dificuldades e transtornos que ocorrerão durante o decorrer de um projeto (como tempo de processamento, espaço utilizado no disco, entre outros) e a complexidade assintótica está ligado a funções complexas contidas dentro de um programa, como uma função que fornece…

b ∈ ℤ, (b ≠ 0) tal que bx=a} ℝ = conjunto dos números reais ℕ*= conjunto dos naturais positivos = {1, 2, ...} + ℝ = conjunto dos números reais não-negativos = { x ∈ ℝ : x ≥ 0} Funções: Pisos e Tetos Seja x ∈ ℝ. Denotamos o maior inteiro menor que ou igual a x por ⌊x⌋ (piso) e o menor inteiro maior que ou igual a x por ⌈x⌉ (teto). x-1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x+1 Funções: Pisos e Tetos Propriedades Seja n ∈ ℤ. ⌊n/2⌋ + ⌈n/2⌉ = n Sejam x ∈ ℝ , a, b ∈ ℕ*. + ⌈⌈n/a⌉/b⌉ = ⌈n/ab⌉ ⌊⌊n/a⌋/b⌋…

págs. 11 até 19 Cormen – págs. 32 até 49 Comportamento assintótico de funções • • • • • • O parâmetro n fornece uma medida da dificuldade para se resolver o problema Para valores suficientemente pequenos de n, qualquer algoritmo custa pouco para ser executado, mesmo os ineficientes A escolha do algoritmo não é um problema crítico para problemas de tamanho pequeno Logo, a análise de algoritmos é realizada para valores grandes de n Estuda-se o comportamento assintótico…

bom desempenho no pior caso garante que ele tem bom desempenho em todos os casos. 4 NOTAÇÃO ASSINTÓTICA Na análise de algoritmos, é importante concentra-se na taxa de crescimento do tempo de execução como uma função do tamanho da entrada n, obtendo-se um quadro geral do comportamento, em vez de concentra-se em detalhes menores. Frequentemente, basta saber que o tempo de execução de um algoritmo como maxVetor cresce proporcionalmente a n. Para simplificar a análise, somente o…

UNIVERSIDADE FEDERAL RURAL DE PERNAMBUCO UNIDADE ACADÊMICA DE SERRA TALHADA (UAST) Fazenda Saco, Serra Talhada, Pernambuco, Caixa Postal 063 CEP 56900-000 Fone/Fax: (87) 3831-1927 PROGRAMA DE DISCIPLINA IDENTIFICAÇÃO DISCIPLINA: Algoritmos e Estruturas de Dados CÓDIGO: CCMP5011 DEPARTAMENTO: Unid. Acadêmica de Serra Talhada ÁREA: Informática CARGA HORÁRIA TOTAL : 60 NÚMERO DE CRÉDITOS: 03 CARGA HORÁRIA SEMANAL: 4 TEÓRICAS: 2 PRÁTICAS: 2 PRÉ-REQUISITOS: Introdução a Programação e…

(long int) iii. Média Final (float) b) Tenha um menu que permita realizar as seguintes operações i. Entrar com dados dos alunos; ii. Mostrar dados de todos alunos ordenados de acordo com o valor das médias finais; iii. Sair. OBSERVAÇÕES: Procurar dados do aluno através de seu número USP Entrar com os dados de 5 alunos para teste 4. Faça análise por operações primitivas e a análise assintótica (notação “O”) dos seguintes fragmentos de programas: 5. Faça a análise…

Comando de Greve e a todos da comunidade acadêmica do Campus IV- UFPB, que tanto me orgulham de ter feito parte dessa história. Meu muitíssimo Obrigado. 4 Resumo Duas características de um algoritmo têm importância fundamental no seu projeto ou uso: se ele permite chegar à resposta desejada (eficácia) e quão eficiente ele é no uso dos recursos computacionais (eficiência). Portanto, é necessário que esses dois aspectos sejam enfatizados durante o ensino e desenvolvimento de…

assintoticamente f(n) Notação O denota um limite superior e a notação Ω denota um limite inferior  f(n) = 3n3 + 2n2 + n = Ω(n3)  Basta mostrar que n3 ≤ 3n3 + 2n2 + n, para n ≥ m = 0  Podemos dizer que f(n) = 3n3 + 2n2 + n = Ω(n2), mas essa afirmação é mais fraca que f(n) = Ω(n3)  Uma função g(n) é Θ(f(n)) se g(n) e f(n) dominam assintoticamente uma à outra  Definição equivalente: g(n) = Θ(f(n)) se g(n) = O(n) e g(n) = Ω(f(n))   Notação O é um limite assintótico firme…