Professor responsável

Paulo Fonseca

Horário & sala

• Segunda-feira 17h00 - 18h40 (Sala D002)
• Quarta-feira 18h50 - 20h30 (Sala D002)

Monitores

• José Hugo Gomes (jfg@cin.ufpe.br)
• Kaio Oliveira (kcpo@cin.ufpe.br)
• Linaldo Ferreira Junior (llfj@cin.ufpe.br)
• Wanderley Alves Filho (wcaf@cin.ufpe.br)

Ementa

• Conceitos básicos de algoritmos e estruturas de dados (ED)
• Pseudo-linguagem
• Classificação das estruturas de dados
• ED estáticas lineares/unidimensionais (1-D): vetores
• ED estáticas multidimensionais (N-D): matrizes e hiper-cubos
• Apontadores e alocação dinâmica de memória
• ED dinâmicas 1-D
  • Listas encadeadas, filas e pilhas
• Noções de complexidade computacional - complexidade assintótica
• Busca em ED lineares
  • busca linear vs. busca binária
• Ordenação em ED lineares
  • In place (bubble sort, shell sort)
  • (Revisão de recursão e procedimentos recorrentes)
  • mergesort (Dividir para conquistar - D&Q)
  • quicksort
• Hashing
• ED dinâmicas N-D
  • Árvores, percurso em árvores
• Busca/ordenação em ED N-D
  • Árvores binárias de busca
  • Árvores balanceadas (AVL)
  • Heaps e Heapsort
• ED dinâmicas N-D
  • Grafos dirigidos vs. não-dirigidos
  • Percurso em grafos
  • Grafos ponderados
• Otimização em grafos:
  • Caminho mais curto com origem comum ( algoritmos gulosos - AG)
  • árvores geradoras de custo mínimo (AG)
• Indução finita e programação dinâmica
  • Otimização em ED lineares: knapsack (PD)
  • caminho mais curto (PD)
• Complexidade computacional e Problemas NP-Completos
• Heurísticas para problemas NP-C: backtracking, branch&bound

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 escrito - 30% da nota da unidade
• Prova escrita - 40% 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.3 + P1 * 0.4,

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.

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.

Notas

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 2013
   • 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 2012