Professor responsável

Paulo Fonseca

Horário & sala

• Terça-feira 10h00 - 12h00 (Sala D003)
• Quinta-feira 08h00 - 10h00 (Sala D003)

Monitores

• Duhan Caraciolo
• Gustavo Oliveira
• Lucas Lima
• Mateus Borges

Ementa

• Conceitos básicos de algoritmos e estruturas de dados (ED)
• Revisão de ED básicas:
  • ED estáticas (arrays)
  • ED dinâmicas 1-D (listas encadeadas, filas e pilhas)
• Introdução à análise de algoritmos e complexidade assintótica
• Busca e ordenação em ED lineares
  • busca linear vs. busca binária
  • Mergesort (Dividir para conquistar - D&Q)
  • Quicksort
• Tabelas de dispersão (Hash tables)
• ED dinâmicas N-D: Árvores binárias
• Busca/ordenação em ED N-D
  • árvores binárias de busca
  • Heaps e Heapsort
• ED para relações de equivalência: union-find
• Grafos
  • Grafos dirigidos vs. não-dirigidos
  • Percursos em grafos e aplicações (ordenação topológica, caminhos mais curtos)
  • Grafos ponderados
  • Algoritmos gulosos para problemas de otimização em grafos:
    • Caminhos mínimos com origem comum: Algoritmo de Bellman-Ford, Algoritmo de Dijkstra
    • Árvores geradoras mínimas: Algoritmo de Prim, Algoritmo de Kruskal
• NP-completude
  • P vs. NP
  • Redução polinomial e NP-completude
  • Heurísticas para problemas NP-C
    • Backtracking
    • Branch&bound
    • Programação dinâmica

Bibliografia de referência

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms. MIT Press, 2009. (Também disponível em versão traduzida ) - CLRS

Links para material suplementar serão fornecidos ao longo do curso.

Avaliação

A avaliação será feita em duas unidades. A média do curso (MC) será calculada como

MC = (M1+M2) / 2

onde:

• M1 = Média da 1a. Unidade
• M2 = Média da 2a. Unidade

Em cada unidade a média será constituída por:

• Listas de exercícios - 30% da nota da unidade
• Teste prático - 20% da nota da unidade
• Prova escrita - 50% da nota da unidade.

Por exemplo, se 2 listas de exercícios na 1a. unidade, então

M1 = ((L1 + L2)/2) * 0.3 + T1 * 0.2 + P1 * 0.5,

onde:

• L1,2 = Nota da Lista 1, 2
• T1 = Nota do teste da unidade 1
• P1 = Nota da prova da unidade 1

Cada teste de unidade versará sobre o assunto da unidade até a aula imediatamente anterior.

Cada prova de unidade versará sobre o assunto de toda a unidade.

Segunda chamada

A prova de segunda chamada só poderá ser realizada mediante solicitação formal junto a secretaria e só será deferida se a falta for devidamente justificada com documentação apropriada, conforme a Resolução n° 04/1994 .

A prova de segunda chamada versará sobre o assunto de todo o curso.

Prova final

Se MC >= 7, o aluno está aprovado por média.

Se MC < 3, o aluno está reprovado por média.

Se 3 <= MC < 7, o aluno deverá fazer uma prova final (PF).

A prova final versará sobre o assunto de todo o curso.

A média final será calculada como

MF = (MC + PF) / 2.

Se MF >= 5, o aluno está aprovado.

Se MF < 5, o aluno está reprovado.

IMPORTANTE: As provas serão discutidas posteriormente (em horário a ser definido) e os alunos poderão solicitar revisão. Entretanto, não há margem "extra" de tolerância quanto às médias.

Ética acadêmica

Os alunos devem fazer seus próprios trabalhos individualmente, compreender o que fizeram e ser capazes de explicar os seus raciocínios sem ajuda externa. é permitido discutir com os colegas sobre os problemas das listas de exercícios mas cada aluno deve escrever seus resultados nas suas próprias palavras indivudualmente.

é também permitido estudar código de terceiros, mas não é permitido copiar partes significativas destes e apresentar como se fosse trabalho pessoal. O plágio e a fraude acadêmica não contribuem para o processo educacional e não serão tolerados.

Frequência obrigatória

A frequência às atividades escolares é obrigatória, respeitados o turno e o horário previstos para a disciplina (conforme a Resolução n° 04/1994 ). Considera-se reprovado por falta, independentemente do aproveitamento escolar, o estudante que não tiver comprovado sua participação em pelo menos 75% (setenta e cinco por cento) das aulas, ou ao mesmo percentual de avaliações parciais de aproveitamento escolar.

Monitoria

Serão oferecidas, no contexto da discplina, aulas práticas e atividades de monitoria fora do horário de aula mencionado acima. Essas atividades têm caráter complementar e de reforço e a participação dos alunos é altamente recomendada. Entretanto, a participação nessas aulas é opcional e não contam para efeito de contabilização de frequência.

Observações importantes

1. Esta página tem objetivo de facilitar a comunicação e a organização do curso e será feito esforço para manter a informação aqui contida correta e atualizada. Entretanto, o conteúdo desta página tem caráter fudamentalmente informativo e não-vinculativo, podendo ser modificado a qualquer altura à discrição do professor responsável no melhor interesse dos objetivos didáticos e acadêmicos, bem como da observância às regras instituicionais.
2. Sobrepõem-se às informações aqui contidas qualquer comunicado em contrário emitido publicamente em sala de aula pelo professor responsável.
3. Quaisquer dúvidas e/ou divergências deverão ser esclarecidas o mais brevemente possível com o professor responsável.
4. Documentos de referência:
   • Regimento da UFPE
   • Calendário acadêmico UFPE 2014
   • Resolução n° 04/1994 - Estabelece normas complementares de avaliação de aprendizagem e controle da frequência nos Cursos de Graduação
   • Manual acadêmico UFPE 2014

Inscreva-se já no canal oficial de comunicação entre alunos, professores e monitores da disciplina (apenas para alunos matriculados com e-mail do CIn)

• 17 Mai: Página do curso no ar.