Como chegar
|
Contactos

Algoritmia Aplicada 2017/2018

  • 6 ECTS
  • Lecionada em Português
  • Avaliação Contínua

Objetivos

i. Avaliar a eficiência e desempenho de um algoritmo, determinando a sua complexidade e tempo de execução
ii. Compreender os métodos de resolução de problemas associados a cada domínio (matemática, processamento de texto, ordenação e pesquisa), saber esquematizá-los e apresentar as estruturas de dados adequadas a utilizar
iii. Saber desenvolver algoritmos para resolver problemas avançados em diferentes domínios (matemática, processamento de texto, ordenação e pesquisa)
iv. Comparar e avaliar os vários métodos e algoritmos apresentados em cada domínio, de forma a avaliar o respetivo desempenho.

Esta UC contribui para os seguintes objetivos de ensino do curso: Capacidade de abstração e saber expressar o raciocínio lógico necessário à resolução de problemas; Programar em diferentes ambientes.

Pré-Requisitos Recomendados

Conhecimentos básicos de algoritmia e programação em C ou Java.

Código da UC no Moodle: DEGI-254-1746

Método de Ensino

Nas aulas TP utiliza-se o método expositivo-ativo para a leccionação dos conteúdos programáticos, complementado com a discussão na sala de aula, visando fomentar o sentido crítico dos alunos sobre as matérias leccionadas.
Nas aulas práticas, utiliza-se uma metodologia de ensino-aprendizagem tutorial, assente em dois pilares: a) treino com exercícios práticos comuns; b) aplicação a trabalhos próprios.

Conteúdos Programáticos

1. Análise de Algoritmos
• Determinação de T(n)
• Complexidade de um algoritmo
• Classificação de algoritmos
2. Algoritmos Matemáticos
• Polinómios: cálculo e operações com polinómios
• Integração
• Ajuste de curvas
• Matrizes: representação computacional e operações com matrizes
• Resolução de sistemas de equações
3. Processamento de Cadeias de Caracteres
• Compressão
• Encriptação
4. Ordenação
• Métodos elementares de ordenação: Selecção, Inserção, Shell-Sort
• Método Quick-Sort
• Método Heap-Sort
• Operação de selecção: Métodos fundamentais
• Operação de fusão; Ordenação por fusão
5. Pesquisa
• Operações associadas à pesquisa
• Métodos fundamentais
o Pesquisa sequencial
o Pesquisa sequencial em listas
o Pesquisa binária
o Pesquisa binária interpolada
o Pesquisa em árvore binária
• Hashing
o Funções de Hash
o Encadeamento separado
o Endereçamento aberto

Bibliografia e Webgrafia Recomendada

• Cormen T H, Leiserson C E, Rivest R L and Stein C (2009) Introduction to Algorithms, 3rd Edition, MIT Press.
• Neto J (2014) Programação, Algoritmos e Estruturas de Dados, 3ª. Edição, Escolar Editora.
• Sedgewick R and Wayne K (2011) Algorithms, 4th Edition, Addison-Wesley.

Bibliografia Complementar

• Cormen T H (2013) Algorithms Unlocked, MIT Press.

Planificação Semanal

Semana 1 – Apresentação da UC. Revisões
Semana 2 – Análise de Algoritmos: Determinação de T(n); Complexidade de um algoritmo; Classificação de algoritmos
Semana 3 – Análise de Algoritmos (cont.)
Semana 4 - Processamento de Cadeias de Caracteres: Compressão
Semana 5 – Processamento de Cadeias de Caracteres: Criptação
Semana 6 - Processamento de Cadeias de Caracteres: Criptação (cont.)
Semana 7 – Algoritmos Matemáticos: Polinómios;
cálculo e operações com polinómios
Semana 8 – Algoritmos Matemáticos: Polinómios (cont.); Teste nº1
Semana 9 – Algoritmos Matemáticos: Integração; Ajuste de Curvas
Semana 10 – Algoritmos Matemáticos: Matrizes; representação computacional e operações com matrizes
Semana 11 – Algoritmos Matemáticos: Resolução de sistemas de equações
Semana 12 – Ordenação; Métodos elementares de ordenação
Semana 13 – Ordenação; Métodos avançados de ordenação
Semana 14 – Pesquisa; Operações associadas à pesquisa; Métodos fundamentais; Hashing
Semana 15 – Teste nº 2; Apresentação dos trabalhos práticos

Coerência do programa para com os objetivos

Para os objetivos (i) e (iv) da unidade curricular contribui directamente o ponto (1) do programa, uma vez que permite que o aluno adquira os conceitos essenciais para efetuar a análise de um algoritmo e saiba determinar a sua complexidade e tempo de execução.
Os pontos (2) a (6) do programa contribuirão para os objetivos (ii) e (iii) da unidade curricular, uma vez que permitem que o aluno conheça uma panorâmica geral de métodos de resolução de problemas avançados nos domínios da matemática, processamento de texto, ordenação e pesquisa, sabendo esquematizar os métodos e estruturas de dados utilizadas e desenvolver os algoritmos correspondentes. É valorizado essencialmente o aspeto lógico do pensamento associado à resolução dos problemas tratados, e o sentido crítico na avaliação da eficiência dos algoritmos associados, como previsto no objetivo (iv).

Coerência dos métodos de ensino para com os objetivos

Nas aulas TP o método expositivo-ativo servirá para apresentar os principais conceitos. A utilização de questões-resposta nessas apresentações e a discussão em sala de aula serão utilizados para a interacção frequente com os alunos, com vista a estimular o seu pensamento crítico, a capacidade de emitir opiniões sustentadas e de interiorizar os conceitos essenciais.
Nas aulas práticas, a resolução de exercícios práticos será utilizada para verificar a capacidade dos alunos de aplicarem os conhecimentos obtidos nas aulas TP em situações reais de resolução de problemas e no desenvolvimento de algoritmos e implementação dos programas associados. O desenvolvimento do trabalho prático servirá para reforçar estas capacidades, visando a análise, desenho, desenvolvimento, implementação e testes de um programa para endereçar um problema num dos domínios abordados na unidade curricular.

competência genérica relevantedesenvolvida?avaliada?
Análise e sínteseSimSim
Aptidão para aplicação na prática dos conhecimentos teóricosSimSim
Capacidade crítica e de avaliaçãoSimSim
Capacidade de adaptação a novas situaçõesSim 
Capacidade de auto-critica e de auto-avaliaçãoSim 
Capacidade de investigaçãoSimSim
Competência em informática e uso de novas tecnologiasSimSim
Competência em língua estrangeiraSim 
Comportamento ético e responsávelSim 
Comunicação oral e escritaSimSim
CriatividadeSimSim
Gestão da informação e da aprendizagemSimSim
Preocupação com a eficáciaSimSim
Preocupação com a qualidadeSimSim
Relacionamento interpessoalSim 
Resolução de problemasSimSim
Saber organizar, planear e gerirSimSim
Trabalho em equipaSimSim
Este website usa cookies para funcionar melhor e medir a performance (Diretiva da União Europeia 2009/136/EC)
Por favor dispense alguns minutos para responder a umas perguntas rápidas sobre o nosso website.