BCC402 Algoritmos e Programação AvançadaProf. Marco Antonio M. CarvalhoProf. Túlio Ângelo M. Tóffolo2011/1

2

Introdução aoCurso

3

Carga horária semanal

2 aulas teóricas e 2 aulas práticas (ambas em laboratório)

• Terças às 17:10, lab 22 do DECOM– Prof. Túlio

• Quintas às 17:10, lab 22 do DECOM– Prof. Marco

• A alocação dos professores não é fixa.

4

Objetivos

• Aprofundar conteúdos de programação básica como estruturas de dados e paradigmas de projeto de algoritmos e técnicas para a codificação rápida de códigos eficientes.

• Todos os conteúdos serão praticados na resolução de pequenos desafios computacionais avançados.

5

Metodologia

• Aulas teóricas– Exposição de algoritmos, técnicas e recursos de

programação.

• Aulas práticas– Aplicação do conteúdo teórico na solução de

problemas práticos e teóricos.

• Trabalhos extra-classe– Consolidação da experiência com os temas

tratados em aula

6

Metodologia

• Dois professores– Aula teórica e prática sobre um mesmo tema com

um mesmo professor.

• Terças-feiras– Túlio Tóffolo.

• Quintas-Feiras– Marco Antonio.

7

Recursos

• Ambiente computacional de compilação, desenvolvimento e execução de programas;

• Software de apoio à aprendizagem, executado em um ambiente virtual– Moodle.

• Lista de discussão na internet;• BOCA (Online Contest Administrator)• Maratona Linux• PC Square.• Testes online

– Banco enorme de problemas;

8

UVa

• Site da Universidad de Valladolid (Espanha) com vários problemas e correção automática;

• Problemas semelhantes aos encontrados namaratona– Correção automática;– Em inglês

• Forneceremos versões traduzidas.

8

9 9

Os problemas

• Os problemas são enunciados de forma bem humorada, em contextos fictícios, porém, de aplicação prática;

• Envolvem, dentre outros:– Aritmética e Álgebra;– Geometria computacional;– Manipulação de strings;– Grafos;– Problemas Combinatórios.

10

Atividades dos alunos

• Participação em sessões de discussão sobre estratégias de resolução de problemas utilizando os conceitos abordados;

• Trabalhos de implementação em classe e extra-classe.

• Ao final da disciplina, o aluno deverá estar apto a identificar as estruturas e os paradigmas adequados para resolução de problemas.

• Esta disciplina não se restringe a alunos envolvidos com a Maratona de Programação.

11

Bibliografia

• Skiena, S. S., Revilla, M. A.Programming challenges: the

programming contest training

manual. Birkhäuser, 2003.

12

Bibliografia

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C.Algoritmos: Teoria e Prática. Segunda edição. Editora Campus, 2002.

13

Bibliografia

• Manber, U. Introduction to Algorithms: A Creative

Approach. Addison-Wesley, 1989.

14

Bibliografia

• Sedgewick, R. Algorithms in C Parts 1-5. 3rd Edition. Addison Wesley Longman, 1998.

15

Bibliografia

• Knuth, D. E. The Art of

Computer Programming, Volume 1: Fundamental

Algorithms. 3rd edition. Addison-Wesley, 1997.

16

Bibliografia

• Preparata, F. P., Shamos, M.L. Computational geometry:

An introduction. Springer-Verlag, 1985.

17

Avaliação

• 3 provas práticas, realizadas com auxílio do computador – (50% da nota);– Individuais.

• Listas de exercícios e laboratórios– (50% da nota);– Individuais.

• A frequência também é considerada.

18

Avaliação

• Não será cobrado a memorização de algoritmose estruturas– Ao invés disso, serão cobrados quando e como

utilizá-los.

• O objetivo reside em aprender a utilizar as ferramentas disponíveis, e não em fabricar as ferramentas.

19

Aulas Teóricas

• As aulas teóricas serão realizadas emlaboratório também– Aula expositiva;– Contextualização de problemas computacionais e

práticos do dia-a-dia;– Relação entre descrição textual de problemas e

aspectos computacionais• Algoritmos e estruturas de dados.

20

Laboratórios

• Em cada aula prática, o conteúdo teórico serábrevemente revisto, e exercícios sobre cadatema serão resolvidos e enviados pelo Moodle

até o final do dia– Dificuldade baixa a média;– Contam para a avaliação.

• Só serão considerados exercícios identificadose corretos.

21

Listas de Exercícios

• A cada aula prática, uma série de exercícios serádisponibilizada– Dificuldade baixa a alta;– Correção eletrônica pelo site da Uva;– Entrega pelo Moodle em uma semana;– Contam para avaliação.

• Todos os exercícios são corrigidos– Cópias ou tentativas de trapaça invalidam toda a lista de

exercícios• Acarretam em perda do direito a pontos extras.

• Não haverá gabarito– Dúvidas devem ser sanadas junto ao professor ou colegas

antes do prazo de entrega.

22

Provas

• As provas são realizadas com auxílio do computador– Individuais e sem consulta à internet;– Eventual consulta a livros e notas de aula

• Não quer dizer que será fácil.

• Correção rigorosa em contrapartida.

23

Discussões

• Haverá grande flexibilidade no ambiente da aula no que diz respeito ao compartilhamento de conhecimento– O que não inclui cópias.

• A idéia é que os alunos interajam fortemente, troquem experiências e se ajudem– A disciplina é avaliada individualmente, mas o

aprendizado deve ser coletivo• Pode ser utilizada a lista de e-mails para isso,

ou mesmo o contato pessoal.

24

Discussões

• Todas as dificuldades e dúvidas devem ser postas em discussão– Todos contribuem;– Todos aprendem.

• Por outro lado– Facilidades implicam em maiores

responsabilidades;– Cópias serão fortemente rejeitadas.

25

Linguagem de Programação

• O material da aula utilizará linguagem C– Porém, cada aluno pode escolher a linguagem de

preferência;– C, C++, Java, Pascal...– Shell script não será permitido.

• O ambiente computacional será Linux

– Integração com ambientes de programação;– Facilidade de compilação por linha de comando.

26

Programação

• Aula 01: Uva, Tipos de erros, CompilaçãoRepresentação de tiposFormas padrões de entrada e saída

• Aula 02: Estruturas de dados: Pilhas, Filas, Listas, Dicionários, Filas de prioridade

• Aula 03: Definições e estruturas de dados (grafos)Busca em Largura e Busca em Profundidade

• Aula 04: Ordenação• Aula 05: Manipulação de Cadeias de Caracteres

Busca de PadrõesBibliotecas C/C++ e Java

• Aula 06: Inteiros de alta precisãoBases numéricas e conversãoÁlgebra, manipulação de polinômios, radiciação, logaritmoBibliotecas de Números reais

27

Programação

• Aula 07: RecursividadeTentativa e erro

• Aula 08: Divisão e conquista• Aula 09: Programação Dinâmica• Aula 10: Algoritmos gulosos• Aula 11: Backtracking• Aula 12: Técnicas básicas de contagem• Aula 13: Problemas e métodos clássicos de análise

combinatória• Aula 14: Segmentos de linha e interseção

Computação de polígonos e ângulos• Aula 15: Ordenação Topológica

Árvores geradoras mínimas• Aula 16: Algoritmos de Menores caminhos e fluxo em

redes

28

Cronograma Inicial

• 10/Mar - Aula 01• 15-22/Mar - Aula 02• 17-24/Mar - Aula 03• 29/Mar-05/Abr - Aula 04• 31/Mar-07/Abr - Aula 05• 12-14/Abr - Aula 06• 19/Abr - Prova• 28/Abr-05/Mai - Aula 07• 03-10/Mai - Aula 08

• 12-19/Mai - Aula 09• 17-24/Mai - Aula 10• 26/Mai-02/Jun - Aula 11• 31/Mai - Aula 12• 07/Jun – Prova• 09-16/Jun - Aula 13• 14-21/Jun - Aula 14• 28/Jun-05/Jul - Aula 15• 30/Jun-07/Jul - Aula 16• 12/Jul - Prova• 19/Jul - Exame Especial

29

Cronograma Inicial

• Teremos 3 feriados, recessos ou inversões em dias de aula (21/04, 26/04 e 23/06);

• O calendário acadêmico prevê dias específicos para inversão de aulas– Por exemplo, dias de sábado com calendário de

terça;

• Não teremos uma aula em uma terça-feira (26/04).

30

Recomendações

31

O que se espera do aluno

• Pontualidade– Chamada uma vez por aula;– Perdeu a chamada, não tem choro.

• Dedicação exclusiva às atividades da disciplina durante a aula

• Proatividade;• Aplicação nas atividades extra-classe

– As listas de exercícios representam pontos valiosos.

32

Recomendações

33

Recomendações

34

Recomendações

Inglês• Pelo menos o mínimo é imprescindível para

programação. O aluno deve buscar sanar possíveis deficiências.

35

Recomendações

Proficiência em informática• É esperado que o aluno saiba usar o computador

– Editor de texto;– Navegar na internet;– E-mail;– Lidar com arquivos;– Sistema operacional.

36

Recomendações

Proficiência em programação

• É esperado que o aluno saiba programar em alguma das linguagens suportadas– C;– C++;– Java;– Pascal.

37

Atendimento

• Professores– Marco Antonio– marco.opt@gmail.com (não enviar programas)– 3559-1663– Sala 19 DECOM (Em frente ao laboratório)– Túlio– ??? (não enviar programas)– 3559-1663– Sala 19 DECOM (Em frente ao laboratório)

38

Lista de Discussão

maratonaufop@googlegroups.com

39

Competição

Competição InternacionalNível: a partir do terceiro grau até mestrado (1 ano)

40

Acompanhamento

• Além do material das aulas, outras informações estão disponíveis no curso BCC402 –Algoritmos e Programação Avançada do Moodle

www.decom.ufop.br/moodle

41

Perguntas?

42

FIM