Estruturas de Dados e Algoritmos
Áreas Científicas |
Classificação |
Área Científica |
OFICIAL |
Ciências de Base |
Ocorrência: 2010/2011 - 1S
Ciclos de Estudo/Cursos
Sigla |
Nº de Estudantes |
Plano de Estudos |
Anos Curriculares |
Créditos UCN |
Créditos ECTS |
Horas de Contacto |
Horas Totais |
MIB |
37 |
Plano de estudos oficial |
3 |
- |
6 |
56 |
162 |
Língua de trabalho
Português
Objetivos
Esta unidade curricular tem os seguintes objectivos principais: 1) complementar os conhecimentos de programação adquiridos numa unidade curricular anterior, usando a linguagem C como ferramenta; 2) transmitir conceitos fundamentais sobre estruturas de dados, concepção e análise de algoritmos.
Os estudantes que concluam com sucesso esta unidade curricular deverão ser capazes de: descrever algumas aplicações típicas das estruturas de dados estudadas; criar/seleccionar estruturas de dados e algoritmos para resolver problemas de complexidade simples/média; comparar implementações alternativas de estruturas de dados e de algoritmos; aplicar os conhecimentos adquiridos no desenvolvimento de programas em C, de acordo com a especificação de um projecto, recorrendo às estruturas de dados e aos algoritmos mais adequados.
Programa
Introdução à programação em linguagem C
- estrutura de um programa em C;
- tipos de dados simples e sua representação; operadores e expressões;
- entrada e saída de dados;
- controlo do fluxo de execução: instruções condicionais e ciclos;
- arrays, strings e struct's e sua representação;
- apontadores e alocação dinâmica de memória;
- funções; passagem de parâmetros e retorno de resultados; funções recursivas;
- ficheiros;
- alguns tópicos avançados.
Estruturas de dados e Algoritmos
– Estruturas de dados fundamentais:
-- estruturas lineares: listas, filas e pilhas;
-- árvores;
-- grafos.
– Conceitos fundamentais de algoritmia
-- análise de algoritmos (eficiência e correcção).
- Técnicas de concepção de algoritmos:
-- divisão-e-conquista;
-- algoritmos gananciosos ("greedy");
-- programação dinâmica;
-- algoritmos de retrocesso ("backtracking").
- Exemplos de aplicação:
-- algoritmos de ordenação e pesquisa;
-- pesquisa de "strings";
-- árvores de decisão;
-- e outros.
Bibliografia Obrigatória
Paul J. Deitel, Harvey M. Deitel; C: How to Program, 6/E, Prentice-Hall, 2009. ISBN: 0136123562
Anany Levitin;
Introduction to the design & analysis of algorithms. ISBN: 0-321-36413-9
Bibliografia Complementar
Brian W. Kernighan, Dennis M. Ritchie;
C. ISBN: 85-7001-327-2
Luís Damas;
Linguagem C. ISBN: 972-722-156-4
Marque de Sá;
Fundamentos de programação usando C. ISBN: 972-722-475-X
Métodos de ensino e atividades de aprendizagem
Aulas teórico-práticas:
Exposição das matérias, acompanhada da resolução de problemas no quadro e sua discussão.
Aulas práticas:
Resolução de problemas de aplicação das matérias; desenvolvimento de soluções em linguagem C, em computador.
Trabalho práticos, a realizar fora das aulas:
Desenvolvimento de pequenos projectos de programação, envolvendo a aplicação das matérias estudadas.
Software
Microsoft Visual Studio
Tipo de avaliação
Avaliação distribuída com exame final
Componentes de Avaliação
Descrição |
Tipo |
Tempo (Horas) |
Peso (%) |
Data Conclusão |
Participação presencial (estimativa) |
Participação presencial |
36,00 |
|
|
Resolução de problemas |
Teste |
36,00 |
|
2010-12-17 |
Projectos de programação |
Trabalho escrito |
36,00 |
|
2010-12-17 |
Exame |
Exame |
2,00 |
|
2011-02-11 |
|
Total: |
- |
0,00 |
|
Componentes de Ocupação
Descrição |
Tipo |
Tempo (Horas) |
Data Conclusão |
Teoria |
Estudo autónomo |
36 |
2010-12-17 |
Preparação para exame |
Estudo autónomo |
16 |
2011-02-11 |
|
Total: |
52,00 |
|
Obtenção de frequência
Não exceder o limite de faltas estabelecido nas Normas e obter uma classificação mínima de 40% na classificação distribuída.
A classificação distribuída (cDist) é dada pela seguinte fórmula:
cDist = 0,4*cMT + 0,2*cTP1 + 0,4*cTP2
onde
cMT = classificação obtida no mini-teste a realizar próximo do meio do semestre, sobre programação em linguagem C
cTP1 e cTP2 = classificação de dois trabalhos práticos a realizar durante o semestre.
Fórmula de cálculo da classificação final
A classificação final é dada pela fórmula:
cFINAL = 0,5 * cDIST + 0.5 * cEXAME
onde cDIST e cEXAME representam, respectivamente, a classificação distribuída e a classificação do exame escrito.
É condição necessária para aprovação a obtenção de uma classificação mínima de 40% em qualquer uma das componentes.
Avaliação especial (TE, DA, ...)
Os alunos com estatuto especial, embora possam estar dispensados da frequência das aulas práticas, estão sujeitos às mesmas condições de avaliação dos alunos regulares, isto é, devem realizar o mini-teste e os trabalhos práticos nas datas e períodos estabelecidos para os restantes alunos.
É condição necessária para aprovação a obtenção de uma classificação mínima de 40% em qualquer uma das componentes.
Melhoria de classificação
A classificação distribuída só pode ser melhorada frequentando de novo a disciplina num ano lectivo posterior.
A classificação do exame escrito pode ser melhorada nas épocas legalmente previstas.