Departamento de Informática e Estatística

Planos de Ensino
Visitante (Entrar)

Plano de Ensino

Aprovado pelo Departamento em: 1-8-2018

  1. Identificação: Visualizar em PDF
    • Disciplina: INE5609 - Estruturas de Dados
    • Turma(s): 03238B
    • Carga horária: 108 horas-aula      Teóricas: 54      Práticas: 54
    • Período: 2º semestre de 2018
  2. Curso(s):
    • Sistemas de Informação (238)
  3. Requisito(s):
    • INE5605 - Desenvolvimento de Sistemas Orientados a Objetos I
  4. Ementa:
    • Listas lineares, Árvores, Hashing, Grafos; Algoritmos de pesquisa e ordenação; Análise de complexidade de algoritmos.
  5. Objetivo(s):
    • Geral: Capacitar o estudante a compreender, do ponto de vista da utilização e da representação computacional, e a construir as estruturas de dados e algoritmos de busca e ordenação clássicos a partir da perspectiva orientada a objetos.
    • Capacitar o estudante a compreender, do ponto de vista da utilização e da representação computacional, e a construir as estruturas de dados e algoritmos de busca e ordenação clássicos a partir da perspectiva orientada a objetos.
    • Específicos:
      1. Identificar o papel das estruturas de dados no desenvolvimento de software.
      2. Criar uma biblioteca de estruturas de dados reutilizáveis.
      3. Identificar as estruturas de dados pertinentes a um problema dado.
  6. Conteúdo Programático:
    • Conceitos de estruturas de dados [4 horas-aula]
      • Encapsulamento da representação
      • Atualização (inserção e remoção), pesquisa e ordenação
    • Estruturas lineares [20 horas-aula]
      • Pilhas
      • Filas
      • Listas
    • Tabelas de espalhamento (hashing) [22 horas-aula]
      • Conceitos e funcionamento
      • Funções de espalhamento
      • Tratamento de colisões
      • Problemas envolvendo hashing
    • Árvores [24 horas-aula]
      • Árvores binárias de busca
      • Árvores balanceadas
      • Árvores B e B+
    • Grafos [8 horas-aula]
      • Noções básicas de grafos
      • Representações computacionais
      • Problemas e soluções envolvendo grafos
    • Métodos clássicos de pesquisa nas estruturas trabalhadas [14 horas-aula]
      • Análise da complexidade dos métodos
    • Métodos clássicos de ordenação [8 horas-aula]
      • Análise da complexidade dos métodos
    • Organização de arquivos [8 horas-aula]
      • Arquivos de acesso sequencial
      • Arquivos de acesso direto
      • Arquivos de acesso indexado
  7. Metodologia:

    A disciplina terá um enfoque eminentemente prático. A metodologia de ensino será baseada no contraponto entre Aulas Teóricas e Aulas Práticas. Para tanto todo novo assunto será introduzido em uma aula teórica que terá a duração de 2 a 3 horas, acompanhada ou não pelo Estagiário de Docência/Monitor designado para a disciplina. Este conteúdo teórico será fixado através de uma aula de caráter prático, com duração de 3 a 4 horas que contará com a proposição de um exercício que exige, além do horário em sala, mais de 3 a 4 horas extras classe para ser completado. As atividades práticas poderão ser executadas com auxílio de um Estagiário de Docência ou Monitor quando necessário, onde serão realizadas em laboratório atividades de modelagem e implementação com o objetivo de fixar o conteúdo, além da discussão em grupo de problemas de compreensão e implementação encontrados pela turma. O ponto de contato para a solução de questões práticas dos problemas será preferencialmente o estagiário de docência ou monitor.

    Como linguagem de programação para o ensino do conteúdo fica determinada a Linguagem C++ e como ambiente de implementação obrigatoriamente a Plataforma Linux/Unix, sendo a ferramenta de desenvolvimento preferencial o ambiente VPL do moodle ou o Eclipse para C++, podendo outras ferramentas serem utilizadas. Haverá uma breve introdução a ferramentas de produtividade nessas plataformas, à medida que tornarem necessárias, principalmente as de teste unitário, mas fica a cargo do aluno a responsabilidade de adquirir proficiência nas mesmas. O ensino dos conteúdos se dará através da utilização progressiva do Paradigma Orientado a Objetos, de acordo com a adequação à melhor compreensão do conteúdo.

    A ferramenta de EAD Moodle disponível em moodle.ufsc.br será utilizada para guiar e organizar o ensino, sendo o repositório oficial de material de aula, devendo os alunos constantemente consultá-la para saber de novos exercícios e trabalhos requeridos. A disciplina no Moodle também detalhará o cronograma deste plano de ensino, servindo para marcar as datas exatas das avaliações e documentar alterações de cronograma advindas de necessidades identificadas no semestre. O fórum de discussão no ambiente do Moodle será utilizado para intermediar a comunicação entre professor, estagiário de docência, monitor e alunos. Para efeitos da avaliação da participação do aluno na disciplina, as suas estatísticas de utilização da ferramenta de EAD poderão ser levadas em consideração.

    Como recurso didático auxiliar o professor poderá empregar vivências na forma de jogos de aprendizado (serious games), a serem jogados em equipe em sala de aula ou na forma de objetos de aprendizado digitais, disponibilizados via Moodle, para uso em casa ou na sala. A ferramenta Moodle ainda poderá ser utilizada para a entrega e avaliação automatizada, baseada em testes programáticos dos trabalhos de programação e de tarefa assinaladas pelo professor.

    Em caráter experimental e limitado a 20% da carga horária total, parte do conteúdo será ministrado na modalidade semi-presencial, na forma de vídeo-aulas, a serem assistidas fora de sala de aula, com base no art. 81 da Lei n. 9.394, de 20 de dezembro de 1.996 (Lei de Diretrizes e Bases da Educação), e no disposto na Portaria No 4.059, de 10 de dezembro de 2004. Para tanto o professor poderá fazer uso de videoaulas incluindo animações e exercícios de acompanhamento via Moodle para substituir aulas presenciais.

    Ainda em caráter experimental, o professor pode optar por ministrar a aula na sala virtual da disciplina disponível no ambiente EAD moodle. Estas aulas serão aulas presenciais em ambiente virtual, dessa forma todo o processo didático pedagógico será síncrono. Os alunos são recomendados a participar usando webcam para facilitar a comunicação. A verificação de presença se dará de forma tradicional através de chamada nominal em qualquer período da aula e quantas vezes for necessário para o aferimento preciso da frequência.

    Pressupostos da metodologia de ensino

    A metodologia adotada nesta disciplina pressupõe que os alunos do curso não se limitem a comparecer às aulas, mas que utilizem para as atividades extra-classe associadas a esta disciplina (leituras, resolução de exercícios teóricos e exercícios com o uso da ferramenta de EAD empregada) um número de horas igual ou superior ao número de horas-aula em sala de aula. Pressupõe-se que os alunos tenham estudado o conteúdo utilizando a bibliografia indicada e tenham resolvido, como atividade extra-classe, todos os exercícios propostos pelo professor.

  8. Avaliação:

    A avaliação regular dos alunos se dará através de um conjunto de 7 notas, sendo três destas notas referentes a trabalhos práticos, duas notas referente a provas teóricas e duas notas referentes a provas práticas de programação. A média final será composta pela média ponderada destas 7 notas conforme explanado abaixo:


      Nota 1 (peso 2)- Calculada a partir da média simples das notas atribuídas a todos os pequenos trabalhos de fixação passados ao longo do semestre. Estes trabalhos estarão agendados no Moodle e serão em número entre 10 e 20, de acordo com a avaliação do professor do perfil de aprendizado da turma e suas dificuldades.
      Nota 2 (peso 1) - Um Projeto de Implementação, denominado Projeto I, envolvendo um problema prático do mundo real solúvel com a aplicação de pilhas, listas ou filas e ponteiros e alocação dinâmica de memória. Este trabalho poderá ser realizado em equipe e poderá ser defendido pela equipe em casos onde não fique claro a participação de todos os membros da equipe, sendo atribuída nota individual a cada aluno.
      Nota 3 (peso 1) – Uma prova de prática de programação individual denominada Prova Prática I, cobrindo os assuntos de estruturas lineares. A prova prática será feita utilizando a ferramenta Moodle na qual uma estrutura de dados deverá ser implementada e deverá passar por testes unitários automatizados de acordo com o preceitos utilizados em competições de olimpíadas de programação. A prova pode incluir restrições de tempo para implementação, tempo para execução e quantidade e técnicas de gerência de memória para execução.
      Nota 4 (peso 1) - Um prova teórica individual denominada Prova Teórica I, cobrindo os assuntos de estruturas lineares e complexidade de algorítimos, realizado em laboratório, eventualmente através do uso da ferramenta Moodle Provas, onde serão avaliados aspectos do conhecimento teórico.
      Nota 5 (peso 2)- Um Projeto de Implementação, denominado Projeto II, envolvendo um problema prático do mundo real solúvel com a aplicação de Técnicas de Gerência de Arquivos Indexados. Este trabalho poderá ser realizado em equipe e poderá ser defendido pela equipe em casos onde não fique claro a participação de todos os membros da equipe, sendo atribuída nota individual a cada aluno.
      Nota 6 (peso 1) – Uma prova de prática de programação individual denominada Prova Prática II. A prova prática será feita utilizando a ferramenta Moodle na qual uma estrutura de dados deverá ser implementada e deverá passar por testes unitários automatizados de acordo com o preceitos utilizados em competições de olimpíadas de programação. A prova pode incluir restrições de tempo para implementação, tempo para execução e quantidade e técnicas de gerência de memória para execução.
      Nota 7 (peso 2) - Um prova teórica individual denominada prova teórica II, cobrindo todo o conteúdo da disciplina, realizado em laboratório, eventualmente através do uso da ferramenta Moodle Provas, onde serão avaliados aspectos do conhecimento teórico.

    Todos os trabalhos deverão ser entregues juntamente com a documentação exigida pelo professor, sendo a avaliação realizada sobre código e documentação. A forma de entrega é até a data determinada e através do Moodle de acordo com os critérios estabelecidos para cada trabalho, podendo ser em arquivos compactados ou através da ferramenta de avaliação automática VPL, dependendo da indicação no enunciado do trabalho. É de responsabilidade do aluno entregar o trabalho na forma correta, arquivos corrompidos ou ilegíveis não serão considerados. Trabalhos entregues após o prazo sofrerão penalizações de 50% da nota independente do atraso.

    A critério do Professor, sendo o desempenho parcial dos alunos considerado adequado e suficiente, o que será mensurado pela qualidade da maioria dos trabalhos entregues (condição mínima: média da turma >= 7.0), o item de avaliação número quatro poderá ser considerado desnecessário e omitido. Também a critério do professor, sendo o desempenho parcial dos alunos considerado adequado e suficiente, o que será mensurado pela qualidade da maioria dos trabalhos entregues (condição mínima: média da turma >= 7.0), o item de avaliação número sete poderá ser considerado desnecessário e omitido. Em função do caráter prático da disciplina, os itens 1, 2, 3, 5 e 6 sempre serão avaliados. Nesse caso, a média final transferirá o peso das provas teóricas para as provas práticas correspondentes.

    Se o desempenho médio dos alunos durante o semestre for considerado extraordinário (condições mínimas: média geral da turma >= 7.0 ou média da turma no item de avaliação número três >= 7.0)), o professor pode optar por não exigir a defesa dos Projetos de Implementação, considerando, daquelas equipes que demonstraram bom aproveitamento em todos os aspectos, apenas código e documentação entregues para fins de avaliação.

    Durante a defesa dos projetos de implementação o professor se reserva o direito de questionar individualmente os alunos da equipe sobre aspectos teóricos da disciplina contemplados no trabalho, sendo o resultado desses questionamentos levado em consideração de forma individual na atribuição do conceito.

    Para avaliação dos trabalhos práticos o professor poderá trabalhar com dois modelos de correção: um manual e um automático, sendo dada preferência a este último sempre que possível.

    Para os casos de de correção automática dos trabalhos de programação, estes serão avaliados através da plataforma Moodle. Os testes estarão disponíveis no momento da entrega do trabalho pelos alunos. Os testes serão aplicados e uma nota final do trabalho será sugerida pela ferramenta de correção, podendo o aluno entregar o trabalho quantas vezes forem necessárias para a obtenção da nota desejada, tendo como limite a data de entrega final do trabalho em questão. Cabe ao professor a confirmação da notas em avaliação posterior. Neste caso a nota pode ser alterada levando em consideração a técnica, o estilo e a eficiência do código à critério do professor e previamente estabelecido no enunciado do trabalho.

    Os trabalhos corrigidos automaticamente devem passar na sua integralidade e sem quaisquer defeitos nos testes programados para aquela entrega. Para tal os alunos devem sempre testar seus trabalho na plataforma de avaliação, não sendo aceitas reclamações pela não execução no ambiente disponibilizado. Os testes aplicados no processo de avaliação automática podem incluir:


      Testes baseados na interface de usuários, onde dados são alimentados para o programa desenvolvido através da sua interface e o retorno é avaliado. Nestes casos a precisa implementação da interface é parte da avaliação.
      Testes unitários em classes, onde os alunos serão instruídos a implementar uma interface de classe para que as classes entregues possam ser testadas método a método quanto ao seu funcionamento.
      Avaliação estática de código buscando boas práticas de nomeação de atributos, de visibilidade dos métodos, de estruturação e documentação do código.
      Avaliação dinâmica de código buscando boas práticas de gerência de memória e consistência no uso de métodos e classes em tempo de execução.
      Avaliação de desempenho utilizando restrições de tempo e memória para a execução dos trabalhos no sistema de avaliação disponibilizado pela plataforma Moodle.

    Os pesos de cada item de avaliação nos trabalhos corrigidos automaticamente será divulgado junto com o enunciado de cada trabalho e podem variar de acordo com o objetivo didático de cada trabalho.

    No caso de correções manuais de trabalhos que não envolvam a defesa, serão utilizados 5 critérios objetivos, sendo que cada critério vale 2 pontos:


      Compreensão do Problema: entendeu o que era para fazer (1 ponto) e modelou corretamente a solução (1 ponto) ?
      Emprego dos Algoritmos e Estruturas: empregou os algoritmos e estruturas corretos (% dos algoritmos/estruturas necessários * 2 pontos) ?
      Implementação dos Algoritmos e Estruturas: os implementou corretamente (% dos algoritmos e estruturas necessários * 2 pontos) ?
      Código: compilou (1 ponto) e funcionou (1 ponto) ?
      Documentação: código está documentado e programado como indicado no início do semestre (comentários 1 ponto, estilo de codificação 1 ponto)?

    Havendo defesa dos Projetos de Implementação, a mesma é considerada Prova e o não comparecimento injustificado implica em conceito nulo nestes trabalhos, sendo os critérios de avaliação da defesa os abaixo:

      Compreensão do Problema: entendeu o que era para fazer ? (2 pontos)
      Solução: soube encontrar uma solução ? (2 pontos)
      Conhecimento teórico: compreendeu as implicações teóricas da solução escolhida ? (2 pontos)
      Algoritmos: possui compreensão dos algoritmos empregados e sabe descrevê-los ? (2 pontos)
      Código: compreende a implementação, sabendo detalhar aspectos de seu funcionamento ou de falhas que estão ocorrendo ? (2 pontos)

    Para efeitos de defesa, os trabalhos práticos dos alunos deverão estar disponíveis nos links de entrega disponibilizados no Moodle da disciplina, não podendo ser trocados ou atualizados quaisquer arquivos. Todas as defesas poderão ser realizadas na presença de uma Testemunha e as perguntas e suas respostas protocoladas por esta testemunha. Esta testemunha será preferencialmente o estagiário de docência mas poderá ser algum aluno de pós-graduação ou professor do INE.

    Plágio e Deslealdade Acadêmica

    Todos as atividades da disciplina seguirão um código ético severo, onde os trabalhos serão avaliados quanto a plágio de forma automatizada por uma ferramento que o professor dispõe. Caso esta ferramenta indique a possibilidade de plágio, o professor conferirá automaticamente a nota ZERO a todos os envolvidos e reportará ao órgão competente da universidade para a abertura de processo disciplinar e a aplicação das punições regimentais previstas.


    Quanto aos casos de deslealdade acadêmica em provas (vulgarmente conhecido como colar), o professor lavrará um termo que será entregue ao órgão competente da universidade para a abertura de processo disciplinar e a aplicação das punições regimentais previstas.

    Frequência na Disciplina

    Para a avaliação da frequência na Disciplina fica rigidamente expresso o entendimento disposto na resolução 017/Cun/97 que determina a necessidade de 75% de presença para os cursos presenciais da Universidade.

    Nesta disciplina, o controle de frequência se dará de forma tradicional e de forma automatizada. A forma tradicional implicará em o professor chamar o aluno a qualquer tempo durante a aula para que seja atestada a sua presença. Na forma automatizada, o registo de frequência será feito eletronicamente através da tecnologia NFC e das carteirinhas emitidas pelo Restaurante Universitário. Nesta modalidade o aluno pode ser requerido a registrar a sua entrada e saída da aula em um dispositivo fornecido pelo professor. Para efeito de cômputo de frequência na aula em questão o aluno deve estar presente em pelo menos 80% do tempo de aula lecionada pelo professor. Todos os registros de frequência serão feitos pela ferramenta Moodle e estarão disponíveis para consulta por parte do alunos.

    Dada as necessidade impostas pelo sistema de registro de frequência automatizada é requerido de todos os alunos que portem suas carteirinhas acadêmicas em todas as aulas. Os alunos que não possuem ainda a carteirinha do restaurante universitário deve emiti-la na secretaria do órgão antes do inicio das atividades do semestre. Em casos de eventual esquecimento da carteirinha pelo aluno, poderão ser registrados de forma tradicional a critério do professor.

    Conforme parágrafo 2º do artigo 70 da Resolução 17/CUn/97, o aluno com frequência suficiente (FS) e média final no período (MF) entre 3,0 e 5,5 terá direito a uma nova avaliação ao final do semestre (REC), sendo a nota final (NF) calculada conforme parágrafo 3º do artigo 71 desta resolução, ou seja: NF = (MF + REC) / 2.

  9. Cronograma:
    Aula 1 - Plano de Ensino
    Aula 2 - Introdução à Programação C++
    Aula 3 - Pilha e Fila com Vetores(arrays)
    Aula 4 - Programação orientada a objetos usando C++
    Aula 5 - Lista utilizando vetores (arrays)
    Aula 6 - Depuração de programas em ambientes de programação, criação de testes unitários, gerência e alocação dinâmica de memória
    Aula 7 - Lista Encadeada
    Aula 8 - Auxílio à Implementação
    Aula 9 - Fila Encadeada e Pilha Encadeada
    Aula 10 - Discussões sobre o trabalho de implementação I
    Aula 11 - Lista Circular
    Aula 12 - Auxílio na elaboração do Projeto de Implementação I
    Prova Teórica I
    Apresentação Trabalho I
    Aula 13 - Conceitos de Complexidade de Algoritmos
    Prova Prática I
    Aula 14 - Árvores Binárias de Busca
    Aula 15 - Auxilio com trabalhos pendentes
    Aula 16 - Árvore AVL
    Aula 17 - Auxilio com trabalhos pendentes
    Aula 18 - Árvores Red-Black
    Aula 19 - Árvores de Busca Semibalanceadas Multivias
    Aula 20 - Hashing
    Aula 21 - Gerência de Arquivos
    Aula 22 - Gerencia de Arquivos - Índices Avançados
    Aula 23 - Quicksort
    Aula 24 - Discussões Trabalho de Implementação II
    Aula 25 - Heapsort
    Prova Teórica II
    Apresentação Trabalho de Implementação II
    Prova Prática II
  10. Bibliografia Básica:
    • GOODRICH, Michael T; TAMASSIA, Roberto. Data structures and algorithms in Java. 2nd ed New York: John Wiley & Sons, c2001.- 641p. ISBN 0471383678
    • PREISS, Bruno R. Estruturas de dados e algoritmos: padrões de projetos orientados a objetos com Java. Rio de Janeiro: Campus, c2001. 566p. ISBN 8535206930
    • TENENBAUM, Aaron M; LANGSAM, Yedidyah; AUGENSTEIN, Moshe. Estruturas de dados usando C. São Paulo: Makron Books, 1995. 884p. ISBN 8534603480 : (broch.)
  11. Bibliografia Complementar:
    • PREISS, B. R., Data Structure and Algorithms With Object-Oriented Design Patterns. Editora John Wiley, 1999. Este livro está integralmente disponível em http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus5
    • Santos, Clésio e Azeredo, Roberto, Tabelas: Organização e Pesquisa, Série UFRGS, nº 10, Ed. SagraLuzzatto
    • ECKEL, Bruce. Thinking in Java, Prentice Hall PTR; 3a. ed., 2002, também disponível integral e gratuitamente na rede em http://www.mindview.net/Books/TIJ/ (para apoio no aprendizado/aprofundamento da linguagem Java)