01. Apresentação da Disciplina de Algoritmos

Prévia do material em texto

Apresentação da Disciplina de Lógica 
de Programação Algorítmica 
Prof. Me. Moisés Mota 
Roteiro 
• Ementa; 
• Competências; 
• Teoria e Prática; 
• Conteúdo Programático; 
• Plano de Ensino; 
• Conteúdo Extra; 
• Avaliações; 
• Exercícios; 
• Algoritmos. 
 
Ementa 
• Elementos essenciais de processamento de 
dados. Sistemas algébricos e relacionais. 
Álbebra Booleana. Conceitos de algoritmo, 
dado, variável, vetor, matriz, instrução e 
programa. Hierarquia lógica de informação 
(campos, registros, arquivos, organização, 
etc.). Algorítmo de Pesquisa e Ordenação. 
Estudos de caso. 
Competências 
• Possibilitar ao aluno o desenvolvimento de 
formas de representações computacionais de 
problemas reais, através de algoritmos 
simples; 
• Capacitar o aluno para a construção de 
programas de computador em formato 
algorítmico. 
Teoria e Prática 
• Esta disciplina possui uma carga horária de 80 
horas. Sendo 40 horas de teoria e 40 horas de 
prática. 
Conteúdo programático 
• I UNIDADE 
• APRESENTAÇÃO E INTRODUÇÃO A ALGORITMOS 
• ALGORITMOS: VARIÁVEIS, OPERADORES E CONSTANTES 
• ALGORITMOS: ESTRUTURAS DE SELEÇÃO 
• VISUALG: AULA PRÁTICA – FUNDAMENTOS 
• ESTRUTURAS DE REPETIÇÃO 
• VETORES 
• VISUALG: AULA PRÁTICA – ESTRUTURAS DE REPETIÇÃO 
• II UNIDADE 
• VETORES 
• AULA PRÁTICA: VETORES 
• MODULARIZAÇÃO DE ALGORITMOS 
• VISUALG: AULA PRÁTICA – MODULARIZAÇÃO 
• VISUALG: AULA PRÁTICA – GERAL 
• PROCESSO DE PROGRAMAÇÃO 
• LINGUAGENS DE PROGRAMAÇÃO 
Plano de Ensino 
• http://www.mauriciodenassau.edu.br/ 
Conteúdo Extra 
• Conceitos Básicos 
• Crescimento de Funções 
• Recorrências 
• Heapsort e Quicksort 
• Ordenação Linear 
• Tabelas Hash 
• Árvores de Busca Binária 
• Árvores Vermelho-Preto 
• Árvores B 
• Programação Dinâmica 
• Algoritmos Gulosos 
• Algoritmos Elementares de Grafos 
• Árvores Geradoras Mínimas 
• Caminhos Mínimos 
• Problemas NP-completos 
 
Avaliações 
• 1ªProva – Peso 8; 
• Trabalhos, Exercícios, Projeto, etc. – 2; 
• 2ª Prova (Prova Colegiada) – Peso 10. 
 
• Obs.: Ainda não foi decidido como serão 
trabalhados estes 3 pontos para compor a 
nota da primeira unidade. Aceito sugestões. 
Exercícios 
• Poderão ser divididos em: 
– Exercícios para nota; 
– Exercícios de fixação; 
– Exercícios para treinamento (ENADE, Concursos, 
etc.); 
Algoritmo 
• O que é? 
• Para que serve? 
• Por que é importante estudar? 
 
Algoritmo - Definição 
• Informalmente, um 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. 
Algoritmo - Definição 
• Mais informalmente ainda: um algoritmo é 
qualquer procedimento que descreve 
explicitamente como resolver um 
determinado problema. 
Algoritmo - Exemplos 
• Receita de Bolo; 
• Instruções sobre como pegar um copo d’água; 
• Manual sobre como ligar/montar algum tipo 
de equipamento; 
Algoritmo - Exemplos 
• Receita: 
– 2 xícaras de farinha de trigo; 
– 2 xícaras de açúcar; 
– 1 xícara de leite; 
– 6 colheres de sopa cheias de chocolate em pó; 
– 1 colher de sopa de fermento em pó; 
– 6 ovos; 
• Obs.: Só a receita não é um algoritmo. Essas 
seriam as entradas apenas. 
Algoritmo - Exemplos 
• Receita: 
– 2 xícaras de farinha de trigo; 
– 2 xícaras de açúcar; 
– 1 xícara de leite; 
– 6 colheres de sopa cheias de chocolate em pó; 
– 1 colher de sopa de fermento em pó; 
– 6 ovos; 
• Modo de Preparo: 
– Bata as claras em neve, acrescente as gemas e bate novamente, coloque o açúcar e bata outra 
vez 
– Coloque a farinha, o chocolate em pó, o fermento, o leite e bata novamente 
– Untar um tabuleiro e colocar para assar por aproximadamente 40 minutos em forno médio 
– Enquanto o bolo assa faça a cobertura com 2 colheres de chocolate em pó, 1 colher de 
margarina, meio copo de leite e leve ao fogo até começar a ferver 
– Jogue quente sobre o bolo já assado 
– É só saborear 
• Obs.: Ingredientes são as entradas, Modo de preparo é o procedimento, a saída é 
o bolo. 
Algoritmos - Tipos 
• Existem diversos tipos de algoritmos para 
resolver problemas específicos: 
– Ordenação; 
– Tabelas; 
– Busca; 
– Programação Dinâmica; 
– Gulosos; 
– Percorrer Grafos; 
Algoritmos – Exemplos de Uso 
• Problemas de Ordenação: 
– Ordenar cadastro de clientes e funcionário; 
• Problemas de Busca: 
– Pesquisa em estruturas do tipo árvore; 
• Problemas de caminho em grafos: 
– Traças melhor rota entre dois pontos geográficos; 
 
Algoritmos - Importância 
• Por que estudar algoritmos? 
– Ensina a resolver problemas computacionalmente 
tratáveis de maneira eficiente; 
 
• Por que é importante? 
– Resolver problemas de maneira eficiente significa 
economia de recursos. Como memória, espaço, 
tempo, etc. 
 
Algoritmos – Caso Real 
• Companhia de Energia da Paraíba: 
– Problema: 
• Aterramento causado por queimadas; 
• Queda de energia de uma região; 
• O algoritmo comumente utilizado leva horas para 
encontrar o local; 
– Solução: 
• Procurar de maneira rápida e eficiente o local do 
aterramento para tratar o problema; 
Algoritmos – Caso Real 
• Primeiro passo: Estudar o problema; 
– Investigar qual o tipo de problema, ordenação, 
caminho mínimo, etc.; 
– Verificar se há uma solução definitiva para o 
problema; 
– Verificar qual o custo de memória e tempo para 
implementar a solução; 
– Se não houver solução definitiva, buscar pela 
melhor solução. 
 
Algoritmos – Caso Real 
• Investigação 
– Foi verificado que o problema era NP – Completo. 
Ou seja, não há uma solução definitiva para o 
problema; 
– Existem várias soluções, portanto é preciso 
selecionar a melhor; 
– A melhor solução geralmente é a que custa 
menos (memória e tempo). 
Algoritmos – Caso Real 
• Solução: 
– Foi encontrada uma solução que custava menos 
tempo e memória; 
– A nova solução consegue identificar a linha de 
energia com problema entre 10 e 20 minutos; 
• Resultado: 
– Cliente Satisfeito; 
– Problema resolvido. 
Algoritmos – Um pequeno comentário 
sobre Complexidade 
Figura 1 – Complexidade de Algoritmos 
Algoritmos – Um pequeno comentário 
sobre Complexidade 
• Resumindo: 
– Problemas NP-Completo, ou NP-Difícil, são 
problemas que não possuem uma única solução; 
– Não podem ser resolvidos num tempo ótimo; 
– Problemas do tipo “P” possuem ótimas soluções, 
ou seja, com consumo mínimo de memória e/ou 
de tempo; 
 
 
Algoritmos – Um pequeno comentário 
sobre Complexidade 
• Observações: 
– Complexidade de Algoritmos não é um assunto da 
ementa desta disciplina; 
– Conhecer este assunto é importante mas talvez 
não haja tempo hábil; 
– Ao fim da disciplina discutiremos mais sobre este 
conteúdo extra. 
Algoritmos – Exemplo de problema 
sem solução definitiva 
Figura 2 – Problema do Caixeiro-Viajante 
Algoritmos – Custos 
• Quando falamos de custos estamos falando de: 
– Tempo que o algoritmo leva para dar uma resposta; 
– Quanto de memória ele consome; 
 
• Obs.: Antigamente falava-se em complexidade de 
espaço, mas hoje considera-se que o espaço é 
infinito por questões práticas; 
• Obs.2.: Existem métodos para calcular esses 
custo mas veremos isso posteriormente. 
Algoritmos – Linguagens de 
Programação 
• Não é preciso saber linguagem de 
programação para aprender algoritmos; 
• Geralmente aprende-se primeiro a disciplina 
de algoritmos; 
• Mas vamos utilizar linguagens de 
programação para ajudar a fixar o conteúdo 
da disciplina; 
 
Algoritmos – Linguagens deProgramação 
• Linguagens existentes: 
– C/ C++; 
– Java; 
– Python; 
– Pascal; 
– Ruby; 
– Fortran; 
– E muitas outras. 
Algoritmos – Linguagens de 
Programação 
• Linguagem C: 
– Paradigma estrutural; 
– Eficiente (consome menos memória); 
– É bastante utilizada na indústria eletrônica; 
– Também é conhecida por ocupar pouco espaço; 
 
 
 
Algoritmos – Linguagens de 
Programação 
• Metodologia: 
– Teremos aulas de teoria e em seguida 
colocaremos em prática nos laboratórios; 
– Também teremos exercícios para casa, 
principalmente utilizando bases de problemas 
prontos como o SPOJ; 
– Problemas de Olimpíadas de Informática poderão 
ser utilizados. 
Algoritmos – Linguagens de 
Programação 
• SP.O.J. – Sphere Online Judge; 
• Uma base de problemas online com mais de 
10000 problemas de diversos tipos; 
• Há uma comunidade ativa de usuários que 
ajudam na resolução destes problemas; 
• É ótimo para praticar o que se aprende em 
sala de aula. 
• Endereço: http://br.spoj.com/ 
Algoritmos – Linguagens de 
Programação 
• Exemplo de problema do SPOJ: 
– Escreva um programa que computa o número de diferentes fatores primos de 
um inteiro positivo. 
• Entrada 
– A entrada consistirá de uma série de inteiros positivos. Cada linha possui 
somente um número. O valor máximo de um número é 1000000. O fim da 
entrada é indicado por um número igual a 0. Esse número não deve ser 
considerado como parte do conjunto de teste. 
• Saída 
– O programa deve imprimir cada resultado em uma linha diferente, seguindo o 
formado dado no exemplo de saída. 
• Exemplo 
• Entrada: 289384 930887 692778 636916 747794 238336 885387 760493 
516650 641422 0 
• Saída: 289384 : 3 930887 : 2 692778 : 5 636916 : 4 747794 : 3 238336 : 3 
885387 : 2 760493 : 2 516650 : 3 641422 : 3 
Algoritmos – Linguagens de 
Programação 
• Restrições do SP.O.J.: 
– Tempo limite:1s 
– Tamanho do fonte:50000B 
– Memory limit:256MB 
– Cluster:Pyramid (Intel Pentium III 733 MHz) 
– Linguagem permitida:Todas exceto: AWK CLOJ ERL 
F# GO JS NODEJS PERL 6 PYTH 3.2.3 n SCALA SED 
TCL 
– Origem:Segunda Seletiva para Maratona de 
Programacao UFRN - 2004 
Algoritmos – Linguagens de 
Programação 
• Restrições do SP.O.J.: 
– Não se preocupem com as restrições. Ao utilizar 
linguagens como C, ou C++, as restrições de 
memória e tempo de execução são atendidas 
quase que automaticamente. 
Algoritmos – Literatura Básica 
• T. H. CORMEN, C. E. LEISERSON, R. L. RIVEST e 
C. STEIN. Algoritmos: Teoria e Prática. Editora 
Campus, 1ª Edição, 2002. 
• T. H. CORMEN, C. E. LEISERSON, R. L. RIVEST e 
C. STEIN. Algoritmos: Teoria e Prática. Editora 
Campus, 3ª Edição, 2012. 
 
 
Algoritmos – Literatura complementar 
sobre C 
• N. ZIVIANI. Projeto de Algoritmos Com 
Implementações em Pascal e C. Editora 
Pioneira, 2004; 
• Qualquer outro livro ou apostila que ensine a 
programar em C. 
 
Dúvidas 
Referências 
• T. H. CORMEN, C. E. LEISERSON, R. L. RIVEST e 
C. STEIN. Algoritmos: Teoria e Prática. Editora 
Campus, 1ª Edição, 2002.