ALGORITMOS E ESTRUTURAS DE DADOS I

Prévia do material em texto

Pontifícia Universidade Católica do Rio Grande do Sul
ESCOLA POLITÉCNICA
VIGÊNCIA: 1998/1 - 2020/2
PROGRAMA DA DISCIPLINA
DISCIPLINA:
ALGORITMOS E ESTRUTURAS DE DADOS I
CODCRED CARGA HORÁRIA MÓDULO
46171-04 60 60
EMENTA:
Análise e construção de algoritmos. Programação imperativa: algoritmos e estruturas de dados
convencionais (atribuições, seleção e repetição, entrada e saída, matrizes, registros, ponteiros).
Subprogramação. Recursividade.
OBJETIVOS:
O cumprimento da disciplina busca dar ao aluno, ao final do semestre, condições de:
1. Conhecer as estruturas de dados primitivas e estruturas do tipo arranjos.
2. Indicar as estruturas de dados que melhor se adaptam para a solução de um determinado
problema.
3. Construir algoritmos estruturados que sejam soluções de um dado problema, no paradigma de
programação imperativa, utilizando os conceitos de subprogramação e recursividade.
4. Analisar e verificar a correção de um algoritmo, utilizando a técnica de execução simbólica.
5. Selecionar o algoritmo mais eficiente para a solução de um determinado problema.
6. Familiarizar-se com o emprego da notação assintótica para análise de algoritmos.
CONTEÚDO:
Nº DA UNIDADE: 01
CONTEÚDO: Conceitos Fundamentais de Algoritmos
1.1. Conceito e características de um algoritmo
1.2. Tipos de dados 
1.3. Objetos de um algoritmo: variável e constante
1.4. Estrutura de um algoritmo 
1.4.1. Algoritmo principal e subalgoritmos
1.4.2. Área de declarações
Nº DA UNIDADE: 02
Campus Central
Av. Ipiranga, 6681 - Prédio 30 - Sala 101 - CEP: 90619-900
Telefone: (51) 3320.3558
www.pucrs.br/politecnica
Pontifícia Universidade Católica do Rio Grande do Sul
ESCOLA POLITÉCNICA
CONTEÚDO: Tipos de Algoritmos
2.1. Puramente seqüenciais
2.1.1. Expressões aritméticas
2.1.2. Operadores aritméticos
2.1.3. Prioridades
2.1.4. Instruções primitivas
2.1.4.1. Atribuição
2.1.4.2. Saída de dados
2.1.4.3. Entrada de dados
2.2. Com seleção
2.2.1. Expressões relacionais
2.2.2. Operadores relacionais
2.2.3. Expressões lógicas
2.2.3.1. Operadores lógicos
2.2.3.2. Tabela verdade
2.2.3.3. Prioridades
2.2.4. Tipos de instruções 
2.2.4.1. Seleção simples
2.2.4.2. Seleção composta
2.2.4.3. Seleção aninhada
2.3. Com repetição
2.3.1. Tipos de instruções
2.3.1.1. Estrutura Enquanto
2.3.1.2. Estrutura Repita
2.3.1.3. Estrutura Para
2.3.2. Conceitos relacionados: inicialização, contadores e acumuladores
2.3.3. Consistência de dados de entrada
Nº DA UNIDADE: 03
CONTEÚDO: Subalgoritmos
3.1. Conceitos e vantagens da utilização
3.2. Escopo de variáveis: globais X locais
3.3. Tipos de subalgoritmos
3.3.1. Função
3.3.2. Procedimento
3.4. Parâmetros
3.4.1. Passagem por valor
3.4.2. Passagem por referência
3.5. Formas de desenvolvimento de algoritmos
3.5.1. Top Down
3.5.2. Botton Up
Nº DA UNIDADE: 04
Campus Central
Av. Ipiranga, 6681 - Prédio 30 - Sala 101 - CEP: 90619-900
Telefone: (51) 3320.3558
www.pucrs.br/politecnica
Pontifícia Universidade Católica do Rio Grande do Sul
ESCOLA POLITÉCNICA
CONTEÚDO: Estruturas Homogêneas
4.1. Unidimensionais: Vetores
4.1.1. Formalização e manipulação
4.1.2. Operações mais comuns
4.1.3. Pesquisas em vetores
4.1.4. Métodos simples de ordenação de vetores
4.2. Multidimensionais: Matrizes
4.2.1. Formalização e manipulação
4.2.2. Operações mais comuns
4.2.3. Pesquisas em matrizes
4.2.4. Matrizes especiais
4.2.4.1. Matrizes triangulares
4.2.4.2. Matrizes esparsas
Nº DA UNIDADE: 05
CONTEÚDO: Introdução à Análise de Algoritmos
5.1. Importância 
5.2. Contagem de passos
5.3. Ordem de crescimento 
5.3.1. Notação O(n)
5.3.2. Operando com ordens de crescimento
Nº DA UNIDADE: 06
CONTEÚDO: Estruturas Heterogêneas
6.1. Registros
6.2. Formalização e manipulação
6.3. Combinando com variáveis homogêneas
6.3.1. Vetores de registros
6.3.2. Registros com vetores
Nº DA UNIDADE: 07
CONTEÚDO: Desenvolvimento de Algoritmos Recursivos
7.1. Conceito e exemplos de utilização
7.2. Algoritmos recursivos X iterativos
7.3. Recursividade utilizando estruturas de dados
PROCEDIMENTOS E CRITÉRIOS DE AVALIAÇÃO:
Avaliação da disciplina será feita mediante trabalhos, exercícios, projetos, ou/e provas.
BIBLIOGRAFIA BÁSICA:
Campus Central
Av. Ipiranga, 6681 - Prédio 30 - Sala 101 - CEP: 90619-900
Telefone: (51) 3320.3558
www.pucrs.br/politecnica
Pontifícia Universidade Católica do Rio Grande do Sul
ESCOLA POLITÉCNICA
1.FORBELLONE, A. L. V.; EBERSPACHER, H. F. Lógica de Programação. São Paulo, Makron Books,
2000.
2.ORTH, A. I. Algoritmos e Programação. Porto Alegre: AIO, 2001. 175 p.
3. VELOSO, Paulo et alli. Estruturas de Dados. Rio de Janeiro, Editora Campus, 1996.
BIBLIOGRAFIA COMPLEMENTAR:
1.AHO, A. V.; HOPCROFT, J. E.; ULLMAN, J. D. Data structures and algoritmos. Massachusetts,
Addison-Wesley, 1987.
2.CORMEN, T.; LEISERSON, C.; RIVEST, R. Introduction to Algorithms. MIT Press, 2001.
3.FARRER, H. et alli. Algoritmos Estruturados. Rio de Janeiro, Guanabara, 1999. 
4.SALVETTI, D.; et al. Algoritmos. São Paulo : Makron, 1998 .273 p.
5.VILLAS, Marcos V.; VILLAS BOAS, L. Programação: Conceitos, Técnicas e Linguagens. Rio de
Janeiro, Editora Campus, 1988.
6.WIRTH, N. Algoritmos e Estruturas de Dados. Rio de Janeiro, Prentice-Hall, 1999.
7.GUIMARÃES, A. M.; LAGES, N.A.C. Algoritmos e Estruturas de Dados. Rio de Janeiro , LTC, 1994.
Campus Central
Av. Ipiranga, 6681 - Prédio 30 - Sala 101 - CEP: 90619-900
Telefone: (51) 3320.3558
www.pucrs.br/politecnica