INE 5408 – Estruturas de Dados

• Alocação dinâmica de memória [6 horas-aula]
  • Variáveis estáticas e dinâmicas
  • Ponteiros
  • Passagem de parâmetros por referência, valor e nome
• Estruturas lineares [24 horas-aula]
  • Listas
  • Pilhas
  • Filas
• Complexidade de algoritmos [6 horas-aula]
  • Conceitos de Complexidade de Algoritmos
  • Métodos práticos para Análise da Complexidade de Estruturas e Algoritmos
• Árvores [24 horas-aula]
  • Árvore binária
  • Árvores binárias semibalancedas como Árvore AVL e Árvore Red-Black
  • Árvore semibalanceadas n-árias como Árvore B e B+
  • Árvores multichaves como Árvore k-d
• Tabela de espalhamento (hash) [15 horas-aula]
  • Tratamento de colisões
  • Funções de espalhamento
• Métodos de ordenação [12 horas-aula]
  • Conceitos básicos, implicações e premissas
  • Métodos de Complexidade Quadrática
    • Método por inserção
    • Método por seleção
    • Método da bolha
  • Métodos Avançados e de Complexidade n log n
    • Método Quicksort
    • Método Heapsort
• Estruturas de dados em arquivo [21 horas-aula]
  • Acesso direto e Acesso sequencial
  • Organização de Arquvos por Índices
    • Métodos indexados sequenciais, ISAM e VSAM
    • Indexação por Árvore
    • Multilistas e Lista Invertida

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 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, sempre com auxílio de um Estagiário de Docência, 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.

Como linguagem de programação para o ensino do conteúdo fica determinada a Linguagem \”C\”/C++ e como ambiente de implementação obrigatoriamente a Plataforma Linux/Unix, sendo a ferramenta de desenvolvimento preferencial o ambientre NetBeans para C++, podendo outras ferramentas serem utilizadas. Haverá uma breve introdução a ferramentas de produtividade nessas plataformas, à medida que tornarem necessárias, 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 dos Paradigmas de Programação Estruturado e Orientado a Objetos, de acordo com a adequação de cada paradigma à melhor compreensão do conteúdo. Cada paradigma será brevemente introduzido, sendo seu histórico e seus princípios descritos.

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. 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. A lista de email da disciplina será utilizada para intermediar a comunicação entre professor, estagiário de docência 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.

A avaliação regular dos alunos se dará através de um conjunto de 5 notas de peso igual:

• A média de todos os pequenos trabalhos de fixação passados ao longo do semestre, os quais serão em número entre 8 e 12, de acordo com o perfil da turma e suas dificuldades.
• Um Projeto de Implementação, denominado Projeto#1, 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 deverá ser defendido pela equipe, sendo atribuída nota individual a cada aluno.
• Um Teste Parcial realizado em laboratório, eventualmente através do uso da ferramenta Moodle, onde serão avaliados aspectos do conhecimento teórico e onde poderá ser exigida a resolução de um problema de implementação.
• Um Projeto de Implementação, denominado Projeto#2, 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 deverá ser defendido pela equipe, sendo atribuída nota individual a cada aluno.
• Um Teste Final, englobando todo o assunto do semestre, realizado em laboratório, eventualmente através do uso da ferramenta Moodle, onde serão avaliados aspectos do conhecimento teórico e onde poderá ser exigida a resolução de um problema de implementação.

Todos os trabalhos deverão se 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 em em arquivo .zip ou .rar contendo todos os arquivos. É de responsabilidade do aluno entregar o trabalho na forma correta, arquivos corrompidos ou ilegíveis não serão considerados.

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, um ou mais dentre os itens de avaliação de números 3 e 5 poderão ser considerados desnecessários e omitidos. Em função do caráter prático da disciplina, os itens 1,2 e 4 sempre serão avaliados.

Se o desempenho dos alunos durante o semestre for considerado extraordinário, o professor pode optar por não exigir a defesa dos Projetos de Implementação, considerando apenas código e documentação 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 para os quais não for exigida 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 como indicado no início do semestre (comentários 1 ponto, dicionário de dados 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)

A Prova de Recuperação terá peso de acordo com a legislação da UFSC e será constituída de um trabalho de implementação individual que deverá ser defendido pelo aluno. O enunciado deste trabalho será publicado até a data do Teste Final. Como a disciplina possui carga prática pelo menos igual a 50% da carga horária, a prova de recuperação é opcional e o professor se reserva ao direito de não oferecer prova de recuperação, caso considere adequado. Se necessário, a prova de recuperação será marcada em data no intervalo entre o término do período letivo e a data de entrega das notas.

Os critérios de avaliação para defesa do Trabalho de Recuperação serão os mesmos utilizados para defesa de Projetos de Implementação.

Para efeitos de defesa, os trabalhos práticos dos alunos deverão estar disponíveis nas contas dos alunos no repositório SVN do INE. Todas as defesas serão realizadas na presença de uma Testemunha e as perguntas e suas respostas protocoladas por esta testemunha. Esta testemunha será preferencialmente o estatiário de docência mas poderá ser algum aluno de pós-graduação ou professor do INE.

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.

Aula 1 Assunto: Apresentação da disciplina, introdução e aspectos gerais da disciplina e explicitação das estratégias e métodos de ensino e avaliação.
Aula 2 Atividade em Laboratório: Introdução à Programação C++, às funções básicas de C e suas manpages e ao ambiente de desenvolvimento. Explicitação da filosofia de desenvolvimento a ser seguida na disciplina.
Aula 3 Assunto: Modelagem e Programação das Classes Pilha e Fila com Vetores (arrays)
Aula 4 Atividade em Laboratório: Exercício de programação orientada a objetos usando C++: modelagem de uma classe a ser utilizada como componente de estruturas posteriores; implementação da Pilha e da Fila modeladas na aula anterior.
Aula 5 Assunto: Modelagem e Programação da Classe Lista utilizando vetores (arrays) como caso geral de Pilha e Fila.
Aula 6 Atividade em Laboratório: Exercícios de fixação da implementação da Classe Lista utilizando vetores. Estudo de aplicações.
Aula 7 Assunto: Gerência e alocação dinâmica de memória. Diferenças entre ambientes utilizando máquina virtual e linguagens compiladas.
Aula 8 Atividade em Laboratório: implementação de alocação e liberação dinâmicas de memória em C++.
Aula 9 Assunto: Classe Lista Encadeada
Aula 10 Atividade em Laboratório: Auxílio à Implementação da Classe Lista Encadeada. Estudo de aplicações.
Aula 11 Assunto: As Classes Fila Encadeada se Pilha Encadeada em como caso especiais de Listas Encadeadas
Aula 12 Atividade de Fixação em Laboratório sobre Variantes de Listas Encadeadas. Apresentação do Projeto de Implementação nº 1
Aula 13 Assunto: As Classes Lista Circular e Lista Duplamente Encadeada. Estudo de aplicações.
Aula 14 Atividade de Fixação em Laboratório sobre Variantes de Listas Duplamente Encadeadas.
Aula 15 Assuntro: Introdução à Complexidade de Algoritmos
Aula 16 Atividade em Laboratório: Auxílio na modelageme implementação do Projeto de Implementação nº 1
Aula 17 Assunto: Introdução a Árvores
Aula 18 Aula Prático: Implementação do Objeto Árvore
Aula 19 Assunto: Árvores Binárias de Busca
Aula 20 Aula em laboratório para implementação de Árvores Binárias em C++
Aula 21 Assunto: Árvores Binárias de Busca Semibalanceadas
Aula 22 Árvores de Busca Semibalanceadas Multivias: A Árvore B
Aula 23 Atividade prática: Implementação dos exercícios / trabalhos pendentes.
Aula 24 Assunto: Hashing
Aula 25 Técnicas de Implementação de Hashing na Memória e Funções de Hashing
Aula 26 Assunto: Gerência de Arquivos
Aula 27 Aula em laboratório para implementação de Conceitos Básicos de Manipulação de Arquivos em C++
Aula 28 Técnicas de Gerência de Arquivos utilizando Listas e Árvores: Árvore B+ e k-d, Multilista e Arquivo Invertido
Aula 29 Aula Prática de Gerância de Arquivos e Divulgação do Enunciado do Projeto de Implementação II (Avaliação nº 4)
Aula 30 Assunto: Introdução à Ordenação
Aula 31 Assunto: Métodos de Ordenação n log n
Aula 32 Aula prática sobre Ordenação
Aula 33 Aula em laboratório para auxílio à implementação do Projeto de Implementação II.
Aula 34 Defesas dos Trabalhos e divulgação do tema do Trabalho de recuperação
Aula 35 Aula em laboratório para auxílio à implementação do trabalho de recuperação.
Aula 36 Defesa dos trabalhos de recuperação.