Programação
-
Estruturas de Dados
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 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, 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++ e como ambiente de implementação a plataforma Linux/Unix, sendo a ferramenta de desenvolvimento preferencial o ambiente Eclipse para C++. Haverá uma breve introdução à ferramentas de produtividade nessas plataformas, à medida que se tornarem necessárias, mas fica a cargo do aluno a responsabilidade de adquirir proficiência nas mesmas. Vale lembrar que a entrega dos trabalhos de programação serão feitos através de uma unica plataforma homologada. Desta forma é obrigatório que o aluno entregue os trabalhos e verifique sua correta execução na plataforma homologada.
O ensino dos conteúdos se dará através da utilização progressiva do paradigma de programação orientado a objetos sempre de acordo com a adequação à melhor compreensão do conteúdo. Os trabalhos de programação sempre primarão pelo correto uso da linguagem e do paradigma, sendo avaliados todos os quesito de boas práticas e de precisão do uso do paradigma.
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, conforme descrito abaixo. O fórum do Moodle da disciplina será utilizado 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.
Estratégia de Ensino
A disciplina será mediada através da ferramenta de EAD Moodle, o que significa que a organização da disciplina, marcação de provas e exames, datas de entrega de trabalhos e outras orientações será sempre realizada através deste curso no Moodle.
O Moodle gera um log do uso do ambiente para cada aluno, o que ajuda o professor no acompanhamento das atividades. Para resolução de questões de freqüência suficiente ou insuficiente do aluno e questões sobre plágio de exercícios, as estatísticas geradas pelo Moodle sobre uso e consulta de material didático e enunciados de exercícios poderão ser utilizadas.
As questões envolvendo plágio são infrações gravíssimas da conduta ética do estudante da UFSC. Todas as ocorrências detectadas pelos sistemas automáticos de detecção serão avaliadas pelos professores e serão reportadas as instâncias competentes da universidade para providências.
Organização do Ensino
O ensino da disciplina será realizado pelos Profres. Jean Everson Martina, Aldo v. Wangenheim e Alexandre Gonçalves Silva. Além disso, o ensino da disciplina será assistido pelo trabalho de um Estagiário de Docência - ED. O ED será sempre um aluno regularmente matriculado em um curso de pós-graduação da UFSC, preferencialmente mas não necessariamente, o PPGCC. Este estagiário poderá ministrar aulas, acompanhar aulas do professor, participar na avaliação dos alunos e oferecer horários de monitoria para atendimento dos alunos. A atuação do ED é regulada pelo ¶15° do Regimento do PPGCC. Os estagiários de Docência deste semestre serão a Munyque Mittelmann e o Douglas Marcelino Beppler Martins.
Horário das Aulas
Sistemas de Informação:
Conforme acordado em sala de aula, faremos as aulas na forma de 100 minutos + 100 minutos, com a pausa de 10 minutos prevista no espelho de matrícula. As aulas sempre iniciar-se-ão às 18:30 conforme previsto. Atrasos superiores a 20 minutos incidirão em meia presença no período de 100 minutos correspondentes. Saídas antecipadas e ausências não justificadas e acertada com o professor durante o período implicarão em falta. Por questões de facilidade no calculo da frequência mínima obrigatório a presença nas aulas de quarta feira será verificada uma vez em cada período.
Dessa forma, os horários regulares de aulas ficam assim:
4ª - 18:30 - 22:00 h INE 101
6ª - 18:30 - 20:10 h INE 101
Ciências da Computação:
Faremos as aulas de quarta-feira na forma de 150 minutos corridos, sem a pausa de 20 minutos prevista no espelho de matrícula. Além disso, as aulas de 3ª feira iniciar-se-ão às 15:10 h e não às 15:30 h conforme previsto. Terminaremos a aula 20 minutos antes ( pelo uso dos 20 minutos de pausa), o que facilita o deslocamento de todos e evita o horário de rush em volta da universidade.
Dessa forma, os horários regulares de aulas ficam assim:
3ª - 15:10 - 17:40 h ENS 216
5ª - 15:10 - 17:40 h INE 101 (PCT)
Organização do Atendimento a Alunos
Para o melhor atendimento aos alunos o ED oferecerá um horário de monitoria que será divulgado no fórum da disciplina. Este horário será único e fixo, devendo os alunos da disciplina se dirigirem primariamente ao ED neste horário para a solução de problemas referentes ao conteúdo da disciplina. O horário de monitoria será escolhido de tal forma que se situe em um ponto da semana onde o aproveitamento para os alunos seja máximo, possibilitando-lhes ter tempo de tentar resolver exercícios e trabalhos antes de procurar a monitoria. Fica a critério do ED atender a alunos fora deste horário quando solicitado, cabendo esta decisão ao julgamento do ED.
Observe-se que o INE não possui mais recursos para pagamento de bolsa de monitoria para esta disciplina, sendo o horário de monitoria um serviço adicional oferecido aos alunos no sentido de promover melhores condições de aprendizado. Quem carrega o ônus do financiamento do horário de monitoria é o laboratório da UFSC ao qual o ED pertence, que aloca horas do tempo de trabalho em laboratório do ED para que este esteja à disposição dos alunos para atendimento.
É importante que o aluno tenha consciência disso e procure utilizar o horário de monitoria de forma objetiva e parcimoniosa. Sugerimos sempre comparecer à monitoria com dúvidas concretas e objetivas, somente depois de ter tentado resolver os exercícios e trabalhos, de forma a tornar mais eficiente e direcionado o trabalho do monitor que poderá direcionar seu suporte à resolução de dúvidas concretas.
Para todos os assuntos organizacionais da disciplina e todas as dúvidas sobre conteúdo que a monitoria não tenha sido capaz de sanar, o prof. da disciplina estará à disposição dos alunos. Para tanto deve ser encaminhado um e-mail solicitando horário ou marcando um horário pelo telefone 3721 9516 (Aldo), 3721 7546 (Jean) ou 3721 2736 (Alexandre), citando-se a disciplina e o assunto da consulta. Infelizmente, em função da quantidade bastante grande de compromissos do professor, não há atendimento a alunos sem horário previamente marcado.
Avaliação
Critérios de Avaliação
- 7 Notas :
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 18, 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 duplas e poderá ser defendido pela dupla em casos onde não fique claro a participação de todos os membros, 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 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, 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 dupla e poderá ser defendido pela dupla em casos onde não fique claro a participação de todos os membros, 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 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, onde serão avaliados aspectos do conhecimento teórico.
Durante a defesa dos projetos de implementação o professor se reserva o direito de questionar os alunos da dupla sobre aspectos teóricos da disciplina contemplados no trabalho, sendo o resultado desses questionamentos levado em consideração na atribuição do conceito.
Para efeitos de defesa, os trabalhos práticos dos alunos deverão constar no VPL correspondente ao trabalho. Deverão compilar e executar neste ambiente.
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 estagiário de docência mas poderá ser algum aluno de pós-graduação ou professor do INE.Resumindo: Avaliação dos Projetos de Implementação:
- Avaliação do Código e Documentação exigidos.
- Entrevista
- Aspectos de Implementação e Teóricos
- Avaliação em Grupo/Nota Individual
Recuperação (de e acordo com parágrafo 2º do artigo 70 da Resolução 17/CUn/97)
-
Conceito "menção I" somente será cogitado para casos com justificativa médica ou ocorrência de força maior embasada em boletim de ocorrência policial ou similar, de acordo com a legislação da UFSC.
- Pelo cunho prático da disciplina a recuperação é opcional e será decidida pelo professor no decorrer da disciplina.
-
Caso a recuperação ocorra, ela será realizada através de um trabalho de implementação seguido de entrevista.
-
O trabalho de recuperação será individual
- O trabalho de recuperação terá peso igual ao da média do semestre, de acordo com a legislação da UFSC
Filosofia da Disciplina:
Playlist de todas as Video Aulas no Youtube
Custo Atualizado por Reprovação em ED para 2017.2: R$ 3.620.55
(Fonte: A EVOLUÇÃO DOS INDICADORES DE CUSTO POR ALUNO NA UNIVERSIDADE FEDERAL DE SANTA CATARINA DE 2002 A 2012 CONFORME METODOLOGIA DO TCU. Mariana Campagnoni, Orion Augusto Platt Neto + https://www3.bcb.gov.br/CALCIDADAO/publico/corrigirPorIndice.do?method=corrigirPorIndice )
(Resultado da divisão da média de 20 créditos por semestre e multiplicados pelos 6 da disciplina)
-
Assunto: Introdução à Programação C++ e ao ambiente de desenvolvimento.
- Programação Orientada a Objeto;
- Revisão / introdução à linguagem C++;
- arquivos de definição / arquivos de implementação;
- estruturas de decisão / repetição;
- modelo de projeto no NetBeans;
- entendendo o ambiente de edição;
- entendendo o ambiente de debug.
Material de Consulta Adicional
Nesta seção haverá material de consulta adicional para você que estará sendo constantemente atualizado. Consulte regularmente este material.
- Programação Orientada a Objeto;
-
Modelagem e Programação das Classes Pilha e Fila com Vetores(arrays).
- Estruturas de Dados - Definição;
- Pilhas usando Vetores;
- Modelagem da Pilha em Programação Orientada a Objeto;
- Pilha - Implementação.
Material da Aula e Links para Trabalhos e Exercícios
-
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.
- Entendendo estruturas com vetores.
- Exercício: implementação de uma Pilha em "C++".
- Teoria Adicional: Fila utilizando Vetores.
- Entendendo estruturas com vetores.
-
Assunto: Modelagem e Programação da Classe Lista utilizando vetores (arrays) como caso geral de Pilha e Fila.
- Estrutura de Dados Lista - Definição
; - Listas usando Vetores: Modelagem da Classe Lista;
- exercícios de implementação.
- Estrutura de Dados Lista - Definição
-
Assunto: Aula Prática de Implementação de Listas com Vetores
-
Assunto: Gerência e alocação dinâmica de memória. Diferenças entre ambientes utilizando máquina virtual e linguagens compiladas.
- Alocação e liberação de memória.
- Classes de armazenamento.
- Conceitos de stack, heap e tipos de passagem de parâmetros por nome, referência e valor.
Material Adicional e Enunciados de Trabalhos
-
Atividade em Laboratório: Implementação de alocação e liberação dinâmicas de memória em C++.
- Alocação de variáveis.
- Classes de Armazenamento.
- Endereçamento de variáveis usando ponteiros.
- Técnicas de gerência de memória.
- Exercício em Sala: programa com número variável de listas e pilhas com vetores alocadas dinamicamente usando TAD list/pilha com vetor.
-
Assunto: Classe Lista Encadeada.
- a Classe elemento de lista
- a Classe informação de lista
- técnicas de encadeamento: lista ordenada e lista cronológica
- algoritmos de inserção, pesquisa, substituição e deleção
Material da Aula para Baixar e Enunciados de Trabalhos e Exercícios
-
Aula sobre 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. Diferenças entre ambientes utilizando máquina virtual e linguagens compiladas.
Atividade em Laboratório: Exercícios de fixação sobre debuging e criação de testes unitários com gtest.
- revisão do uso das ferramentas.
- Debuging em Eclipse.
- Criação de testes unitários para os trabalhos ja entregues.
- Alocação e liberação de memória.
- Classes de armazenamento.
- Conceitos de stack, heap e tipos de passagem de parâmetros por nome, referência e valor.
Material Adicional e Enunciados de Trabalhos
-
57.8 Kb application/vnd.oasis.opendocument.presentation
-
-
-
-
-
Assunto: As Classes Fila Encadeada e Pilha Encadeada como casos especiais de Listas Encadeadas.
-
Assunto: As Classes Lista Circular. Estudo de aplicações.
- Aspectos especiais na implementação;
- cuidados especiais na inserção e deleção: indireção e derreferência múltipla de ponteiros.
-
Apresentação do Enunciado do Trabalho de Implementação I
-
Material Adicional
-
Assunto: Árvores Binárias de Busca
- Capítulo: Árvores Binárias
- Métodos e algoritmos de percurso em árvores binárias
- Métodos e algoritmos de balanceamento
- A Árvore Binária de Busca e seus algoritmos
- Características
- Algoritmos (inserção, deleção e pesquisa)
Material Adicional
-
-
Prova Teórica I Questionário
-
-
-
Prova Prática I Laboratório Virtual de Programação
-
-
Assunto: Árvores Binárias de Busca Semibalanceadas e Exercícios com Árvores de Busca Balanceadas
- A Árvore AVL
- Inserção, pesquisa e deleção
- Balanceamento
Material Adicional
- Página de Árvores AVL da Disciplina
- Animação de Árvore AVL com inserção e deleção (versão INE)
- Explicação detalhada de como se faz a deleção
- Página na Wikipedia
Exercícios com Árvores de Busca Balanceadas
-
1.2 Mb Apresentação Powerpoint 2007
-
-
-
-
Árvores Red-Black
- Página na Wikipedia (muito boa e com links para fontes em C++ e Java)
- Simulador de Árvores RB com inserção e deleção (versão INE)
-
1.4 Mb Apresentação Powerpoint 2007
-
-
Árvores de Busca Semibalanceadas Multivias
A Árvore B
- Árvores monochave de grau 3 ou superior
- Estrutura e peculariedades da Árvore B para uso na Memória do Computador
- Algoritmos de inserção, pesquisa e deleção
Material Adicional
-
1003.6 Kb Apresentação Powerpoint 2007
-
-
Assunto: Gerência de Arquivos
- Introdução
- Características: Memória Secundária x RAM
- Noção Intuitiva
- Disco
- Tipos de Arquivos
- Acesso a Registros
- Escolha da Organização de Arquivos
- Tipos de Consulta
- Indexação
- Métodos de Gerência/Organização
- Arquivos Seqüenciais
- Arquivos Indexados Seqüenciais
Material Adicional
- Página sobre primeiros discos rígidos na Wikipedia
- Página sobre História da Fita Magnética na Wikipedia
- Página sobre Discos de Estado Solido na Wikipedia
-
Gerência de Arquivos: Listas e Árvores
-
Técnicas de Gerência de Arquivos utilizando Listas
- Atualização de Arquivos com Índices em Lista
- Página de organização de Arquivos de C.J. "Keith" van Rijsbergen (Univ. Glasgow)
- Multilista
- Lista Invertida (Wikipedia)
-
Técnicas de Gerência de Arquivos utilizando Árvores
- Aspectos Gerais: Árvore como Arquivo-Índice
- Árvore Binária Paginada
- Árvore B
- Árvore B+
- Árvore K-D
-
-
Trabalho de Implementação II
-
Assunto: Hashing
- Introdução
- Hashing Aberto
- Hashing Fechado
- Conceito de colisão
- Estratégias de redução de colisão
- Funções de Hashing
Técnicas de Implementação de Hashing na Memória
- Modelagem de funções de Hashing
- Folding ou Desdobramento
- Gerência de memória para tabelas de Hashing
- Manipulação de colisões
- Aplicações de Hashing utilizando armazenamento secundário
Material Adicional e Enunciados de Trabalhos
- Página com Simulador de Hashing Aberto (USFCA)
- Página com Simulador de Hashing Fechado Simples (USFCA)
- Página com Simulador de Hashing Fechado com Repositórios (USFCA)
-
Métodos de Ordenação - Parte 1 - Quicksort
- Conceitos básicos
- Algoritmos
- Material original sobre Bubbesort
Material do Professor
Material Adicional
- Animação de Quicksort com narraçao em inglês (desenvolvida por B.Jacobs em CS Animated)
- Animação com diferentes algoritmos de ordenação (1)
- Animação com diferentes algoritmos de ordenação (2)
- Mais uma animação comparando algoritmos de ordenação.
-
Prova prática de Programação
- Implemente a estrtura de dados abaixo usando as melhores teçnicas de progrmação, respeitando o enunciado e as restrições de tempo e espaço impostas pelo ambiente.
-
Métodos de Ordenação - Parte II - Heapsort
Simulação do HeapSort 
Material Adiconal sobre HeapsortA idéia do HeapSort, ordenação por monte, vem de um fenômeno físico conhecido por Brazil Nut Effect, ou Efeito da Noz-do-Pará. É simples: se você tem um conjunto de partículas de tamanho diferente em um recipiente e aplicar uma leve agitação, as partícular maiores (a Noz-do-Pará na mistura de amendoim, nozes e cereais no seu Müsli - vai entender o que os físicos pensam quando dão nome a um efeito) vão, contrainuitivamente,se movendo para cima, "boiando inversamente" na sopa de partículas, enquanto que as mais finas se depositam cada vez mais no findo, "difundindo" para o fundo por entre as partículas maiores. Você pode experimentar isso em casa com uma tijela e grãos de areia de diferentes tamanhos. Isto é muito utilizado na Engenharia, principalmente em mineração, para separação de minérios e tipos de areias. Neste caso o processo é chamado de Segregação de Partículas.
Abaixo algumas simulações e artigos sobre o Efeito da Noz-do-Pará:
Simulações do Heap Sort
Existe uma infinidade de simulações e animações do algoritmo HeapSort. Muitas são bem ruins. Aqui algum material:
- Jogo de Simulação de HeapSort GQS/INCoD
- http://csunplugged.org/sorting-algorithms
- Verbete na Wikipedia
- Site com Animações de TODOS os algoritmos com diferentes tipos de dados. Legal para comparar, mas menos didático.
- Animação da Universidade do Havaí (Boa). Esta animação é acompanhada por um trace do código, assim você tira dúvidas sobre o que faz o quê e quando.
- . Aproveite para ver as simulações de outros algoritmos associadas.
- Jogo de Simulação de HeapSort GQS/INCoD
-
Treino para prova teórica: 12 questões aleatórias - 60 minutos
-
Projeto Implementação II - DEFESA dos Projetos de Implementação
Importante: Defesa é prova oral e o comparecimento de toda a equipe é obrigatório.
- Cada grupo terá 10min para apresentar.
- As defesas acontecerão em laboratória a ser indicado no fórum da disciplina
- É recomendável que vocês tragam seus computadores com o código e o programa funcionando.
- Caso optem por trazer apenas o código para ser compilado na hora, haverão 2 computadores disponíveis. No entanto vocês deverão chegar com 10min de antecedência para preparação e o código deve compilar na instalação padrão Linux utilizada na Disciplina.