ALGORITMOS AULA 01

Prévia do material em texto

Protocolos de Redes e de Computadores
AULA 02
ALGORITMOS AVANÇADOS – AULA 01
Prof. Msc. Alexandre José Braga da Silva
alex.professor@gmail.com
CCT0312 – Algoritmos Avançados
Objetivos da Aula:
• Apresentação do professor e da disciplina;
• Informações gerais sobre a parte prática da disciplina;
• Informações sobre atividades para nota e avaliações;
• Ementa da disciplina e referências bibliográficas;
• Relembrar conceitos de Estruturas de Dados;
• Relembrar a Sintaxe da Linguagem C++.
CCT0312 – Algoritmos Avançados
Ementa da Disciplina
1 – Análise de Algoritmos.
1.1 - Algoritmos
1.2 – Estruturas de Dados
1.3 – Revisão de Programas em C++ incluindo vetores, matrizes, 
 ponteiros, structs e funções
2 – Análise de Algoritmo Notação O
2.1 – O que é a análise de algoritmos
2.2 – Análise assintótica em notação O
2.3 – Função em notação O 
2.4 – Operações com a notação O
CCT0312 – Algoritmos Avançados
Ementa da Disciplina
3 – Recursividade e Grau de Complexidade
3.1 – Definições recursivas
3.2 – Quando não usar recursividade
3.3 – Desenvolvendo algoritmos recursivos
4 – Algoritmo de Ordenação Rápida (QuickSort)
4.1 - Definição
4.2 – Ordenação rápida
4.3 – Análise da complexidade do algoritmo quicksort
CCT0312 – Algoritmos Avançados
Ementa da Disciplina
5 – Algoritmo de Ordenação por Intercalação (MergeSort)
5.1 - Definição
5.2 – Dividir para conquistar
5.3 – Problema da intercalação
5.4 – Análise da complexidade do algoritmo mergesort
6 – Estrutura de Árvore Binária e Árvore AVL
6.1 – Árvore binária e árvore de busca
6.2 – Percorrendo uma árvore binária de busca
6.3 – Percurso em árvore, inserção e remoção 
6.4 – Balanceando uma árvore
6.5 – Algoritmo DSW e árvore AVL 
CCT0312 – Algoritmos Avançados
Ementa da Disciplina
7 – Grafos 
7.1 – Conceito de grafos
7.2 – Algoritmos de busca em grafos
7.3 – Algoritmo do menor caminho
7.4 – Encontrar o melhor caminho do vértice origem ao vértice destino
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Algoritmos é uma sequência lógica de procedimentos em face de 
objetivos pré definidos. É o conceito central da programação, ou seja, 
programar é basicamente construir algoritmos.
"Estruturas de Dados são construções de uma linguagem de 
programação que agregam um ou mais elementos de dados para 
formar um tipo de dado que armazena uma quantidade maior de 
informações".(OLIVEIRA, R., TAVEIRA, G., BOTTINI, J., 2003, p.11)
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
O tipo de dado que representa variáveis compostas unidimensionais 
HOMOGÊNEAS é o Vetor (uma dimensão). 
Um vetor é uma estrutura capaz de armazenar informações de um 
mesmo tipo de dado, correspondendo a posições de memória, 
identificadas por um único nome e endereçadas por um único índice.
Todo vetor em C++ começa na posição 0, assim se um vetor tem 
tamanho N, as posições que dão acesso aos dados ficam no intervalo 
[0 ... N-1].
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Declaração de vetores:
double nota[9];
double peso[5];
int idade[4];
char faculdade[8];
Inicialização de vetores:
nota [0] = 7.6;
nota [1] = 8;
double peso[] = { 75, 85.2, 21.5, 90.5, 55.3 };
double peso[5] = { 75, 85.2, 21.5, 90.5, 55.3 };
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Exemplo de código para manipular vetores:
#include <iostream>
using namespace std;
Int main() {
const int TAM_MAX_NOME = 7;
char nome[TAM_MAX_NOME];
int i;
for( i = 0; i < TAM_MAX_NOME; i ++) {
cout << "Digite uma letra: ";
cin >> nome[i];
}
}
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
O tipo de dado que representa variáveis compostas multidimensionais 
HOMOGÊNEAS é a Matriz (várias dimensões). 
Uma matriz é uma estrutura capaz de armazenar informações de um 
mesmo tipo de dado, correspondendo a posições de memória, 
identificadas por um único nome e endereçadas por múltiplos índices.
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Declaração de matrizes:
double posicao[5][4];
int coordenada[6][4]={ 
{ 3, 1, 1, 1 }, 
{ 1, 0, 1, 1 }, 
{ 1, 4, 1, 1 },
{ 1, 1, 1, 1 },
{ 1, 6, 7, 1 },
{ 1, 1, 1, 8 }
};
int Matriz[3][4][5]={ 
{ 
{1, 2, 3, 4, 1}, 
{8, 2, 5, 4, 1}, 
{1, 2, 5, 4, 1},
{1, 0, 2, 1, 1}
}, { 
{1, 2, 3, 4, 1},
{8, 2, 5, 4, 1},
{1, 2, 5, 4, 1},
{1, 0, 2, 1, 1}
}, { 
{1, 2, 3, 4, 1},
{8, 2, 5, 4, 1},
{1, 2, 5, 4, 1},
{1, 0, 2, 1, 1}
}
};
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Exemplo de código para manipular uma matriz 4x4:
#include <iostream>
using namespace std;
Int main() {
int Matriz [4][4], i, j;
for (i=0; i<4; i++) {
for (j=0; j<4; j++) {
cout << "\nDigite o elemento (" << i << " - " << j << ") da matriz: ";
cin > Matriz[i][j];
}
}
}
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Variáveis compostas heterogêneas é uma coleção de uma ou mais 
variáveis, possivelmente de tipos diferentes, colocadas juntas sob um 
único nome. Em algumas linguagens são chamadas de Registros 
(Structs).
Variáveis compostas heterogêneas são utilizadas para representar um 
conjunto de informações que estão logicamente relacionadas.
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Por exemplo:
 Uma ficha de cadastro de uma empresa tem todo tipo de informações 
sobre um funcionário, necessárias para a empresa.
 Um cartão de ponto de uma empresa possui informações sobre um 
funcionário e seus horários de entrada e saída.
 Uma ficha de um consultório médico possui alguns dados e 
características do estado de saúde dos pacientes.
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Suponha que a empresa possui uma ficha de cadastro dos funcionários 
que ingressam na empresa conforme formato abaixo:
FICHA CADASTRAL
Matrícula: Nome:
Data de Nascimento: Quantidade de Dependentes:
Escolaridade: Profissão:
Data de Ingresso: Salário:
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Algumas informações da ficha possuem o mesmo tipo de dado, por 
exemplo:
- nome, escolaridade e profissão são do tipo conjunto de caracteres.
- Quantidade de dependentes e matrícula são valores do tipo inteiro.
- Salário é uma informação do tipo real (Ex.: R$ 1.000,00).
Para representar esse tipo de estrutura utilizamos o conceito de 
variáveis compostas heterogêneas ou registro. Registros são um 
conjunto de informações (campos) relacionadas, onde cada campo pode 
ser de um tipo de dado diferente (inteiro, real, caracter, lógico, ...).
CCT0312 – Algoritmos Avançados
Revisão dos conceitos básicos:
Para criar a ficha cadastral do exemplo anterior:
struct fichaCadastral {
int matricula, qtdeDependentes;
char nome[50], profissao[50], escolaridade[20];
char dataNascimento[10], dataIngresso[10];
double salario;
};
CCT0312 – Algoritmos Avançados
Exercícios Práticos:
1. Construir um programa em C++ que leia as notas para os alunos de 
um curso de extensão fornecido pela ESTACIO. Sabe-se que para este 
curso são fornecidas 100 vagas anualmente, mas o usuário do programa 
irá digitar a quantidade de alunos matriculados.
Calcular a média das notas dos alunos matriculados, mostrar a média e 
escrever a quantidade de notas maiores ou iguais a média e a 
quantidade de notas inferiores a média.
CCT0312 – Algoritmos Avançados
Exercícios Práticos:
2. Desenvolva em C++ um programa que carregue todos os dados dos 
100 funcionários de uma empresa, calcula a média salarial e escrever o 
nome dos funcionários com salário superiores ou iguais a média. 
Observação: os dados dos funcionários serão carregados em um registro 
de funcionários (Struct).
CCT0312– Algoritmos Avançados
Exercícios Práticos:
#include <iostream>
using namespace std;
int main(){
 float notasCurso[100], mediaCurso, somaNotas;
 int qtdAlunos, qtdIgualMedia, qtdInferiorMedia, contaAlunos;
 cout<<"Quantidade de alunos ingressantes: ";
 cin>>qtdAlunos;
 somaNotas = 0;
 for(contaAlunos=0; contaAlunos<qtdAlunos; contaAlunos++){
 cout<<"Digite a "<<contaAlunos+1<<"a. nota: ";
 cin>>notasCurso[contaAlunos];
 somaNotas=somaNotas+notasCurso[contaAlunos];
 }
 mediaCurso = somaNotas / qtdAlunos;
 qtdIgualMedia = 0;
 qtdInferiorMedia = 0;
 for(contaAlunos=0; contaAlunos<qtdAlunos; contaAlunos++){
 if(notasCurso[contaAlunos]>mediaCurso)
 qtdIgualMedia++;
 else
 qtdInferiorMedia++;
 }
cout<<"Media do curso: "<<mediaCurso<<endl;
cout<<"Alunos com media igual ou superior a do curso: "<<qtdIgualMedia<<endl;
cout<<"Alunos com media igual ou inferior a do curso: "<<qtdInferiorMedia<<endl;
}
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21