Algoritmos - Poli-Elétrica - 1- Apresentação da disciplina

Prévia do material em texto

Escola Politécnica da Universidade de São Paulo 
Algoritmos e Estruturas de Dados 
para Engenharia Elétrica 
Apresentação da Disciplina 
PCS3110 
Agenda 
  Introdução 
  Algoritmos 
  Estruturas de dados 
  Conteúdo da disciplina 
  Critérios de avaliação 
  Referência básica e complementar 
  Monitoria 
2 
Introdução 
  Esta é uma disciplina sobre Algoritmos... 
•  O que são e porque você deve se importar com 
algoritmos? 
•  No dia a dia 
  Um algoritmo é um “conjunto de etapas para executar uma 
tarefa” 
  ... hoje você tem que estudar muito e está meio estressado... 
Para acalmar os ânimos, uma boa tigela de brigadeiro ao 
lado pode ajudar  
3 
Introdução 
  Receita de brigadeiro de microondas 
Ingredientes 
•  1 lata de leite condensado 
•  4 colheres (sopa) de 
chocolate em pó ou 
achocolatado 
•  1 colher (sopa) de margarina 
•  chocolate granulado ou 
granulado colorido (opcional, 
para cobertura). 
http://www.tudogostoso.com.br/receita/456-brigadeiro-de-microondas.html 4 
Introdução 
  Receita de brigadeiro de microondas 
Modo de preparo 
1.  Em um recipiente próprio para microondas, 
de preferência redondo e de borda alta, 
misture todos os ingredientes 
2.  Leve ao microondas por 6 minutos em 
potência alta ou na tecla brigadeiro do próprio 
microondas 
3.  Mexa a mistura na metade do tempo 
4.  Depois de pronto, retire do forno e mexa até 
ficar uma massa lisa e brilhante 
5.  Leve à geladeira para esfriar, depois enrole 
os docinhos, passe no granulado e coloque 
nas forminhas 
http://www.tudogostoso.com.br/receita/456-brigadeiro-de-microondas.html 5 
Ingredientes 
•  1 lata de leite condensado 
•  4 colheres (sopa) de 
chocolate em pó ou 
achocolatado 
•  1 colher (sopa) de margarina 
•  chocolate granulado ou 
granulado colorido (opcional, 
para cobertura). 
Introdução 
  Receita de brigadeiro de microondas 
Modo de preparo 
1.  Em um recipiente próprio para microondas, 
de preferência redondo e de borda alta, 
misture todos os ingredientes 
2.  Leve ao microondas por 6 minutos em 
potência alta ou na tecla brigadeiro do próprio 
microondas 
3.  Mexa a mistura na metade do tempo 
4.  Depois de pronto, retire do forno e mexa até 
ficar uma massa lisa e brilhante 
5.  Leve à geladeira para esfriar, depois enrole 
os docinhos, passe no granulado e coloque 
nas forminhas 
http://www.tudogostoso.com.br/receita/456-brigadeiro-de-microondas.html 6 
Ingredientes 
•  1 lata de leite condensado 
•  4 colheres (sopa) de 
chocolate em pó ou 
achocolatado 
•  1 colher (sopa) de margarina 
•  chocolate granulado ou 
granulado colorido (opcional, 
para cobertura). 
Introdução 
  Receita de brigadeiro de microondas 
Ingredientes 
•  1 lata de leite condensado 
•  4 colheres (sopa) de 
chocolate em pó ou 
achocolatado 
•  1 colher (sopa) de margarina 
•  chocolate granulado ou 
granulado colorido 
Modo de preparo 
1.  Em um recipiente próprio para microondas, 
de preferência redondo e de borda alta, 
misture todos os ingredientes 
2.  Leve ao microondas por 6 minutos em 
potência alta ou na tecla brigadeiro do próprio 
microondas 
3.  Mexa a mistura na metade do tempo 
4.  Depois de pronto, retire do forno e mexa até 
ficar uma massa lisa e brilhante 
5.  Leve à geladeira para esfriar, depois enrole 
os docinhos, passe no granulado e coloque 
nas forminhas 
http://www.tudogostoso.com.br/receita/456-brigadeiro-de-microondas.html 
Algoritmo para 
Entrada 
Saída 
7 
Algoritmo 
  Algoritmo computacional 
•  “É qualquer procedimento computacional bem 
definido que toma algum valor ou conjunto de valores 
como entrada e produz algum valor ou conjunto de 
valores de saída” 
•  Procedimento (computacional) que soluciona um 
problema de computação 
8 
Algoritmo 
  Em que diferem algoritmos executados por 
humanos dos executados por computador? 
9 
Algoritmo 
  Em que diferem algoritmos executados por 
humanos dos executados por computador? 
•  Precisão: algoritmo é descrito numa linguagem que o 
computador possa processar 
•  Correção: para uma entrada o algoritmo deve 
sempre parar produzindo uma saída correta para o 
problema computacional que ele resolve 
10 
Algoritmo 
  Que problemas podem ser resolvidos? 
•  Identificar os 100.000 genes do DNA humano (projeto 
Genoma) 
•  Garantir o acesso rápido a grandes quantidades de 
informações distribuídas na internet 
•  Manter privadas informações sensíveis durante 
transações eletrônicas 
•  Alocar recursos escassos da melhor forma 
•  Encontrar o melhor caminho entre duas localizações 
•  ... 
11 
Algoritmo 
  O que se espera de um algoritmo? 
•  Que ele resolva o problema computacional corretamente 
•  Que faça uso eficiente dos recursos computacionais 
disponíveis 
12 
Algoritmo 
  Um problema comum nas grandes cidades é 
encontrar uma rota entre duas localizações 
•  Aparelhos de GPS 
•  Google maps 
•  Waze 
  O que seria uma solução 
correta para este problema? 
13 
Algoritmo 
  Um problema comum nas grandes cidades é 
encontrar a melhor rota entre duas localizações 
•  Aparelhos de GPS 
•  Google maps 
•  Waze 
  O que seria uma solução 
correta para este problema? 
14 
Algoritmo 
  Pode ser difícil (ou impossível) dizer que um 
algoritmo produz uma solução correta 
•  Considere o reconhecimento de caracteres ópticos 
  A imagem com 11 X 6 pixels representa um 5 ou um S? 
•  Como podemos dizer que a decisão de um 
computador é correta ou incorreta neste caso? 
15 
Algoritmo 
  O que se espera de um algoritmo? 
•  Que ele resolva o problema computacional corretamente 
•  Que faça uso eficiente dos recursos computacionais 
disponíveis 
16 
Algoritmo 
  O que significa uso eficiente dos recursos? 
•  TEMPO: medida comum para avaliar 
 uso eficiente dos recursos computacionais 
•  Quantidade de memória exigida para o 
processamento do algoritmo 
  Algoritmos que resolvem o mesmo problema 
podem ter desempenho muito diferentes!!!! 
17 
Algoritmo 
  Como avaliar a eficiência de um algoritmo? 
•  Estimando o tempo de execução ou o espaço de 
armazenamento exigidos por um algoritmo correto 
  ANÁLISE DO ALGORITMO 
•  O resultado desta análise nos dá a COMPLEXIDADE 
do algoritmo 
  Resultados da análise de algoritmos ajudam na 
escolha do algoritmo para resolver um problema 
18 
Estrutura de dados 
  A estrutura de dados usada afeta diretamente o 
algoritmo 
  Estrutura de dados 
•  Modo específico de organizar, armazenar, acessar e 
modificar dados em um computador 
  Organizar e armazenar 
•  Estrutura 
  Acessar e modificar 
•  Operações para manipular dados armazenados 
19 
Estrutura de dados 
  Vetor V 
•  V é um vetor de nomes com tamanho 4 
•  Dados armazenados em V: Anna, Fábio, Romero e 
Anarosa (nesta ordem) 
•  Operações de manipulação dos dados de V 
  Inserção e recuperação 
  Nenhuma estrutura de dados é perfeita 
•  É preciso conhecer seus pontos fortes e fracos 
•  Ao projetar um algoritmo é preciso analisar qual a 
estrutura de dados é mais adequada 
Anna Fabio Romero Anarosa 
20 
Estrutura de dados 
  Exemplo 
•  Processamento de pedidos de um armazém de uma 
loja virtual 
  Quantos pedidos podem existir? 
•  Desperdício criar um vetor muito grande 
  Pedidos são adicionados e removidos em ordem 
21 
Estrutura de dados 
  Exemplo 
•  Processamento de pedidos de um armazém de uma 
loja virtual 
  Quantos pedidos podem existir? 
•  Desperdício criar um vetor muito grande 
  Pedidos são adicionados e removidosem ordem 
•  Mais adequado usar uma lista ligada 
22 
Descrição de algoritmos 
  Usaremos um pseudocódigo 
•  Sintaxe similar a do C e C++ 
•  Permite apresentar o algoritmo de forma sucinta e 
clara 
•  Evita que detalhes da linguagem de programação 
afetem o entendimento do algoritmo 
•  Pode ser facilmente traduzido para uma linguagem 
de programação 
  Alguns exercícios na lista de exercícios 
23 
Convenção 
  Indentação indica estrutura de bloco 
  while, for, repeat-­‐until e if-­‐else	
  
  // indica comentário 
  i	
  =	
  j	
  indica atribuição de valor de j em i 
  A[1,..,n]	
  	
  
•  vetor com n elementos (1º elemento tem índice 1) 
•  A[i]	
  indica o i-ésimo elemento 
•  A.tamanho indica número de elementos do vetor A	
  
  O comando return transfere o controle para o 
ponto em que o procedimento foi chamado 
24 
Convenção 
  Não é necessário definir o tipo da variável ou o 
tipo de retorno 
  Exemplo 
  Mais detalhes da convenção de código no site 
da disciplina 
25 
Soma-­‐Vetor(V)	
  
1  total	
  =	
  0	
  
2  for	
  i	
  =	
  1	
  to	
  V.tamanho	
  
3  	
  	
  total	
  =	
  total	
  +	
  V[i]	
  
4  return	
  total	
  
Conteúdo da disciplina 
  Introdução 
  Métodos de projeto e análise de algoritmos 
  Estruturas de dados básicas 
  Grafos, conceitos, problemas clássicos e 
algoritmos associados 
  Árvores, conceitos, problemas clássicos e 
algoritmos associados 
  Algoritmos gulosos 
  Algoritmos de ordenação e análise de 
algoritmos 
  Programação dinâmica 
26 
Critérios de avaliação 
  Cálculo da média 
•  ME: média de exercícios de avaliação 
  Realização semanal 
•  Pi: Prova i, onde i =1, 2 e 3 
  Matéria cumulativa 
27 
Princípios éticos e morais 
  Esta escola NÃO é um local onde a maioria age 
contrariamente aos princípios éticos e morais 
esperados numa sociedade civilizada. 
  Vocês estão convidados a mostrar que aqui 
agimos de forma ética tanto no ensino como no 
aprendizado! 
28 
Tolerância Zero 
  Nesta disciplina entendemos a cola e a 
assinatura fraudulenta em lista de presença 
como faltas grave, sujeitas a sanções previstas 
no regimento da USP. 
  Consultem o regimento da USP para se informar 
sobre sanções disciplinares. 
•  http://www.leginf.usp.br/?historica=decreto-
no-52-906-de-27-de-marco-de-1972 
•  Título XI – Do Regime Disciplinar 
29 
Bibliografia 
  Livro texto 
•  Cormen, T.; Leiserson, C.; Rivest, R.; Stein, C. 
Algoritmos: Teoria e Prática, tradução da 3ª. Edição, 
Elsevier - Campus Ed., 2013 
  Livros de apoio 
•  Feofiloff, P. Algoritmos em linguagem C, 1ª. Edição, 
Elsevier – Campus, 2009 
•  Cormen, T. Desmistificando Algoritmos, tradução da 
1ª. Edição, Elsevier – Campus Ed., 2013 
•  Sedgewick, R. and Wayne, K. Algorithms, 4th. Edition, 
Pearson, 2011 
30 
Monitores 
  Álvaro Ricieri Castro e Souza 
  Contato 
•  pcs3110.monitoria@gmail.com 
  Verificar no site o horário de atendimento 
31 
Site da disciplina 
  Stoa 
•  http://disciplinas.stoa.usp.br/user/index.php?id=19481 
•  Apresentações, listas de exercício, notas, etc. 
32