Baixe o app para aproveitar ainda mais
Prévia do material em texto
dibio@unb.br Por que estamos aqui? dibio@unb.br Ensinar/aprender "Education is the acquisition of the art of the utilisation of knowledge" (Alfred North Whitehead [1861-1947], The Aims of Education, 1929: 16) dibio@unb.br Dados da disciplina ● Estruturas de Dados, Turma E, 2011/2 ● Créditos (04-00-00-04) ● 04 aulas (horas) ● 04 ESTUDOS (horas) ● semanalmente (= 8 horas) ● Linguagem de Programação utilizada: C dibio@unb.br Assuntos ● Computação e resolução de problemas algorítmicos. Conjuntos, dados compostos e abstração de dados. Estruturas básicas para representação de informações: listas, árvores, grafos, e suas generalizações. Ordenação e busca: Arquivos, Ordenação, Busca e Espalhamento (“Hashing”). Algoritmos para construção, consulta, e manipulação de tais estruturas. Desenvolvimento, implementação e testes de programas usando tais estruturas em aplicações específicas. (POR QUE?) dibio@unb.br Estruturas de Dados ● Formas/métodos conceituais e concretos de organizar dados para armazenamento e manipulação EFICIENTES ● Empregos dessas estruturas de dados no projeto de algoritmos eficientes dibio@unb.br Requisitos para um bom software/programa ● Projeto claro, objetivo ● Fácil manutenção (comentários, modular) ● Confiável (sem erros) ● Fácil para usar (mnemônicos) ● Algoritmos rápidos ● ESTRUTURAS DE DADOS EFICIENTES ● ALGORITMOS EFICIENTES dibio@unb.br O que vocês aprenderão? ● Quais são algumas das estruturas de dados comuns ● Quais são algumas maneiras de implementá-las ● Como avaliar a eficiência das mesmas ● Como usá-las para resolver problemas interessantes dibio@unb.br Material/método indispensável ● Bons livros para ler e entender (ver referências e ir a BCE – UnB, ou web) ● Laboratório de programação em C (LINF, linux, gcc), praticar e aplicar em projetos ● Aulas e resolução de tarefas dibio@unb.br Professor: Díbio ● CIC (sala ?, módulo 18 ICC) ● dibio at unb.br (correio eletrônico) dibio@unb.br Roteiro ● Apresentações e agenda do curso ● Como estudar? ● Papéis em nossa jornada de aprendizagem ● Horários de laboratório ● Afinal, o que é computação? ● O que seria computável? ● Métodos para resolução de problemas, computáveis... ● Dados simples, compostos dibio@unb.br Agenda do curso (onde? o quê? como? e agora?) ● Encontros: 2a. e 4a. Aula Expositiva/Provocações LINF (Definir horário com atendimento) ● Avaliação: Presença => 75% Trabalhos Práticos (Prog.C) = 6 Provas Escritas = 3 dibio@unb.br Agenda do curso (onde? o quê? quando? como? e agora?) ● Datas para lembrar: Provas escritas (28/09) (16/11) (14/12) Trabalhos práticos (04/09) (25/09) (23/10) (06/11) (27/11) (11/12) obs: domingos dibio@unb.br Algoritmo da nota final Exames={Emaior, Emeio, Emenor} Trabalhos={T1, T2, T3, T4, T5, T6} MEx = (1.25xEmaior + 1.0xEmeio + 0.75xEmenor)/3 Mtr = (T1+T2+T3+T4+T5+T6)/6 SE (MEx => 5.0 E Mtr => 5.0) ENTÃO Mfinal = 0.75xMex + 0.25xMtr SENÃO Mfinal = (Menor valor entre MEx e Mtr) dibio@unb.br Referências Bibliográficas ● CORMEN, T. H. et al. Introduction to algorithms. 2nd ed. Cambridge: MIT Press, 2001. ● SEDGEWICK, R. Algorithms in C (Parts 1-4, Part 5), 2nd ed., Addison Wesley, EUA, 1997. ● RANGEL, J.; CERQUEIRA, R.& CELES, W. Estruturas de dados: uma introdução com técnica de programação em C, Elsevier Brasil, RJ, 2004. ● TENENBAUM,A.; LANGSAM, Y. & AUGENSTEIN, M. Estruturas de dados usando C, Makron Books, SP, 1995. ● ZIVIANI, N. Projeto de Algoritmos: com implementações em Pascal e C, 2a. ed., Thompson, SP, 2007. dibio@unb.br Referências Bibliográficas ● DEITEL, Harvey M.; DEITEL, Paul J.. Como programar em C. 2. ed. Rio de Janeiro: LTC, c1994. ● KERNIGHAM, B. & RITCHIE,D. The C Programming Language, Prentice-Hall, EUA, 1988. ● SCHILDT, Herbert. C completo e total. São Paulo: Makron, 1991. dibio@unb.br Referências Bibliográficas ● + notas de aula; ● material disponível na internet (obs: “links” disponibilizados no ambiente do curso (moodle)); ● outros livros sobre o assunto disponíveis na BCE. dibio@unb.br Ferramentas para o laboratório ● Ambiente linux (ubuntu, redhat, slackware, ...) ● Editor de programas (gedit, kwrite, emacs, codeblocks) ● Compilador (gcc, versão 4.1 ou acima) ● Depurador (xgdb) ● Obs: todos os softwares são de domínio público, gratuitos, e cópias podem ser instaladas em computadores pessoais. dibio@unb.br Inscrição no ambiente “moodle” ● Todos os alunos devem se cadastrar no ambiente “moodle” do -aprender- para acesso e entrega dos trabalhos, bem como de acompanhamento das atividades do curso. ● Como? – 1) tenha um conta de correio eletrônico pessoal (e.g. www.hotmail.com, www.yahoo.com.br, www.gmail.com, e outros) – 2) Acesse http://aprender.unb.br/ dibio@unb.br Inscrição no ambiente “moodle” – 3) Após o preenchimento da inscrição, acesse http://aprender.unb.br/ e faça as opções: ● Depto. de Ciência da Computação ● 116319 Estruturas de Dados – Turma E ● O sistema pedirá um código de acesso à disciplina, que é: ed-20112 ● ● Fazer sua inscrição o quanto ANTES dibio@unb.br Como estudar? ● Problemas contextualizados; ● Objetivo é resolvê-los, estabelecendo um processo contínuo (com sucessivos refinamentos) de aprendizagem; ● Questionamentos e uso de ferramentas (leitura, exercícios) reforçam caminhos; ● 1) Problematizar ● 2) Questionar e Praticar ● 3) Refinamentos dibio@unb.br Como aprender? dibio@unb.br Como aprender? ● Necessário ter: MOTIVAÇÃO CURIOSIDADE ● RESOLVER PROBLEMAS (PENSAR ATIVAMENTE), transformando informação em conhecimento próprio ● FASES: Apreende, Conceitualiza, Aplica ● SEJA PRÓ-ATIVO(A) e CRIATIVO(A)! dibio@unb.br Ensinar/aprender "My intention is not, however, to [simply] impart information, but to throw the burden of study upon you. If I succeed in teaching you to observe, my aim will be attained." Louis Aggasiz [1807-1873], Swiss-American Scientist. dibio@unb.br Ao estudar... ● O importante é interpretação e análise, pois o objetivo é ficar apto a resolver problemas. ● Perguntem-se, estabeleçam conexões, leiam muito e tentem resolver exercícios frequentemente. ● Não deixem assuntos, dúvidas se acumularem. ● ORGANIZAÇÃO + CRIATIVIDADE dibio@unb.br Um processo de aprendizagem proposto Problematizar (Aulas) Questionar e Praticar (Leitura e Exercícios) Refinamentos (Realimentação e Avaliação) dibio@unb.br Papéis (funções) no processo de aprendizagem ● Professor = Orientador (Propõe problemas, indica caminhos, realimenta, avalia) ● Estudante = Ativo participante (não somente ouvinte), busca soluções, lê e pratica fora da sala de aula, dispõe-se a resolver problemas independentemente. dibio@unb.br Afinal, o que é computação? ● Máquinas para computar ● O imaginário e o computador ● Esquema e componentes típicos de um computadordibio@unb.br “Yes, I share your concern: how to program well —though a teachable topic— is hardly taught. The situation is similar to that in mathematics, where the explicit curriculum is confined to mathematical results; how to do mathematics is something the student must absorb by osmosis, so to speak. One reason for preferring symbol-manipulating, calculating arguments is that their design is much better teachable than the design of verbal/pictorial arguments. Large-scale introduction of courses on such calculational methodology, however, would encounter unsurmountable political problems.” Edsger Dijkstra (2000) dibio@unb.br O imaginário e o computador dibio@unb.br O imaginário e o computador dibio@unb.br Na verdade, sistema típico... dibio@unb.br Memória, endereços, instruções dibio@unb.br Exemplos ● Estão em toda parte (automóveis, celulares, aparelhos de tevê, eletrodomésticos, trânsito, telecomunicações, bancos, bolsas de valores, hospitais, fábricas, escolas, corpo humano(próteses eletrônicas), aviões, espaço, etc) dibio@unb.br Processo computacional Entrada Saída Algoritmo (sequência precisa de atividades a serem executadas, e que transformam o conjunto de entrada na saída desejada) dibio@unb.br O que seria computável? ● Processos com algoritmos conhecidos, os quais param (terminam) em tempo finito. ● Buscamos então descobrir, estudar, analisar ALGORITMOS, para resolver problemas, e depois transferir as soluções (algoritmos) para que o computador faça de maneira diligente e repetitiva dibio@unb.br Métodos para resolução de problemas, computáveis... ● ESTRUTURAR (expressões, instruções, procedimentos (funções) independentes) ● “Dividir e conquistar”, refinamentos sucessivos a partir do ciclo (entrada, solução, saída) buscando com que partes (procedimentos) repetitivas sejam identificadas e isoladas; ● O mesmo conjunto de instruções, na mesma ordem, deve produzir sempre a mesma saída a partir de entradas iguais. dibio@unb.br Dados simples ● Dados numéricos (e.g. inteiro, real) ● Dados simbólicos (e.g. caracteres) dibio@unb.br Dados Compostos ● Homogêneos (e.g. vetor, matriz, cadeia de caracteres (“string”)) ● Não necessariamente homogêneo (e.g. Estrutura) ● Conjuntos, formas de inclusão, acesso, organização, algoritmos eficientes para uso em conjuntos e organizações diversas. (e.g. Sequências, prioridade, hierárquicos, fluxos) dibio@unb.br Problemas a lidar ● Como compactar imagens? Dados heterogêneos ● Como acessar, processar esses dados? ● Como organizar prioridade em acesso, processos, fluxos? ● Como comparar grande quantidade de dados? ● Como representar e processar jogos, estratégias, processos em automação? dibio@unb.br Aprender "The important thing is not to stop questioning. Curiosity has its own reason for existing. One cannot help but be in awe when he [or she!] contemplates the mysteries of eternity, of life, of the marvelous structures of reality. It is enough if one tries merely to comprehend a little of this mystery every day. Never lose a holy curiosity." (Albert Einstein [1879-1955]) 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 Slide 22 Slide 23 Slide 24 Slide 25 Slide 26 Slide 27 Slide 28 Slide 29 Slide 30 Slide 31 Slide 32 Slide 33 Slide 34 Slide 35 Slide 36 Slide 37 Slide 38 Slide 39 Slide 40
Compartilhar