Ciência da Computação Disciplina: Estruturas de Dados

Curso: Ciência da Computação Disciplina: Estruturas de Dados Profª Luciana Ap. Oliveira Betetto

Aula 01 1. Algoritmos e a Solução de Problemas Algoritmo: Qualquer procedimento computacional bem definido que toma algum valor ou conjunto de valores como entrada e produz algum valor ou conjunto de valores como saída (Cormen, 2002). Todos os problemas a serem resolvidos por algoritmos possuem dados. Estes são armazenados em estruturas, escolhidas de acordo com as operações que podem ser realizadas sobre elas e com o custo de cada uma dessas operações.

O que é análise de algoritmos? Segundo Cormen (2002), é a previsão dos recursos de que o algoritmo necessitará. - Memória. - Largura de banda de comunicação. - Hardware de computação. - Tempo de computação. Envolve dois tipos de problemas distintos: - análise de um algoritmo particular: calcular o custo de um determinado algoritmo na resolução de um problema. - análise de uma classe de algoritmos: determinar o algoritmo de menor custo possível para resolver um problema.

Modelo RAM: - Instruções executadas uma após a outra, sem operações concorrentes. - Instruções encontradas em computadores reais, tais como instruções aritméticas, de movimentação de dados e de controle. Tempo de execução de um algoritmo: função de custo T, onde T(n) é a medida do tempo necessário para executar um algoritmo para um problema de tamanho n. Um algoritmo nem sempre se comporta de modo uniforme, podendo identificar três casos: Pior caso = maior tempo de execução sobre todas as entradas de tamanho n. Melhor caso = menor tempo de execução sobre todas as entradas de tamanho n. Caso médio = média dos tempos de execução sobre todas as entradas de tamanho n. O tempo de execução de um algoritmo aumenta proporcionalmente ao tamanho da entrada n do problema. A escolha do algoritmo ocorre pelo desempenho em entradas grandes e pelo estudo da eficiência. 2. Estruturas de Dados Um computador é uma máquina que manipula dados. O estudo da ciência da computação inclui o exame da organização, manipulação e utilização destes dados num computador. Conseqüentemente, é muito importante entender os conceitos de organização e manipulação de dados.

...