MCTA002-13 - Algoritmos e Estruturas de Dados II - Bac. Ciência da Computação (3º quad./2016)

Horários e Local

3^a-feira, das 8h às 10h: Sala ~~A110-0~~ S302-1 (nova sala a partir de 11/out) (Aula teórica).
6^a-feira, das 10h às 12h: Lab. 407-2 (Aula prática).

Critério de avaliação

prova escrita valendo 40% da nota da disciplina;
projeto valendo 60% da nota da disciplina;
~~conceito F na prova ou no projeto implica automaticamente F na disciplina;~~
haverá entrega de exercícios que servirão de bônus.

Classificação de conceitos

A: ≥ 9,0

B: ≥ 8,0

C: ≥ 7,0

D: ≥ 5,5

F: < 5,5

O: ≤ 75% de presença em aula.

Recomendação

Algoritmos e Estruturas de Dados I

Ementa

Técnica de busca hashing, union-find, árvores AVL e rubro-negras, árvores B, ordenação mergesort e keysort, compressão de dados: códigos de Huffman.

Programa

Representação, organização e gerenciamento de dados em memória primária; técnicas de pesquisa; noções de complexidade: hashing; union-find; árvores AVL e árvores rubro-negras. Representação, organização e gerenciamento de dados em memória secundária; técnicas de pesquisa; noções de complexidade: árvores B; algoritmos de ordenação mergesort e keysort; arquivos indexados. Algoritmos de codificação e decodificação de dados; Compressão de dados; noções de complexidade: algoritmo de Huffman.

Bibliografia

1. FOLK, M.; ZOELLICK, B.; RICCARDI, G. File Structures: an Object-Oriented Approach Using C++, 3a edição, Addison-Wesley, 1998.

2. CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L. e STEIN, C. Algoritmos: teoria e prática. 2a edição, Rio de Janeiro, RJ: Campus, 2002.

3. SEDGEWICK, R. Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching, 3a edição. Addison-Wesley, 1997.

Bibliografia Complementar

1. ZIVIANI, N. Projeto de Algoritmos: com implementações em Pascal e C, 2a edição, Cengage Learning, 2009.

2. SZWARCFITER, J. L.; MARKEZON, L. Estruturas de Dados e seus Algoritmos, 2a edição, LTC, 1994.

3. RODRIGUES, P.; PEREIRA, P.; SOUSA, M. Programação em C++: conceitos básicos e algoritmos. Lisboa, PRT: FCA Editora de Informática, 2000.

4. TENENBAUM, A. M.; LANGSAM Y.; AUGENSTEIN M. J. Estruturas de dados usando C. São Paulo, SP: Pearson Makron Books, 1995.

5. DROZDEK, A. Estruturas de dados e algoritmos em C++. São Paulo, SP: Thomson Learning, 2002.

Datas Importantes

22/11: Prova

25/11 e 29/11: Apresentação de projetos

02/12: Avaliação substitutiva (normatizada pela Resolução Consepe 181).

06/12: Avaliação de recuperação (normatizada pela Resolução Consepe 182)

09/12: Vista de prova e pedido de revisão (mediante agendamento por email)

Observações importantes

Prova Substitutiva (SUB): somente para quem faltou uma prova por motivo justificado (conforme Resolução Consepe 181).
É necessário a apresentação de algum documento que comprove o motivo. Motivos aceitos: a) doença ou acidente incapacitante (apresentar atestado médico); b) falecimento de familiar (apresentar atestado de óbito); c) viagem de trabalho ou necessidade de permanecer no emprego por motivo urgente (apresentar declaração do chefe ou superior equivalente); d) acidente de trânsito (apenas se você for o condutor do veículo, devendo apresentar Boletim de Registro de Acidente de Trânsito); e) greve nos transportes, alagamento, acidente de grandes proporções ou eventos similares que impeçam a circulação de pessoas por período prolongado (apresentar notícia veiculada em algum jornal/site de conhecimento geral e comprovante de que você mora ou trabalha na região onde o evento ocorreu).
Prova de recuperação (REC): abrange todo o conteúdo do quadrimestre e é destinada a alunos que tenham obtido conceito D ou F (conforme Resolução Consepe 182). Essa avaliação abrangerá todo o conteúdo da disciplina e a nota dessa prova substituirá a nota final na disciplina, restrito a que o conceito máximo obtido seja um conceito acima (de F para D ou de D para C).
Faltas: haverá controle de presença.
Sobre "abono de faltas": na UFABC, os docentes são orientados a não infringir as regras estabelecidas por lei brasileira ou regimento interno (resoluções, etc). O único caso previsto em lei sobre abono de faltas é para militares em exercício. Fora isso, não existe uma regra para "abono de faltas". Nesses termos, documentos que comprovem a necessidade de ausência em aula servem apenas para requisitar prova substitutiva, não para diminuir o número de faltas computada durante a disciplina.

Planejamento e Materiais

Calendário Acadêmico 2016

Página no TIDIA: AED2-2016-diurno

Data	Assunto	Slides
20/09: 3^a-feira	Aula teórica. Breve introdução à Complexidade Assintótica de Algoritmos Representação, organização e gerenciamento de dados em memória primária. Técnicas de pesquisa (algoritmos e complexidade): (1) pesquisa sequencial (SZWARCFITER p.22; ZIVIANI p.154); (2) pesquisa binária (SZWARCFITER p.26; ZIVIANI p.156); (3) árvores binárias de pesquisa sem balanceamento (ABB) (CORMEN p.204; SZWARCFITER p.91; ZIVIANI p.158);	Introdução à complexidade
23/09: 6^a-feira	Aula prática. Implementação da busca sequencial e da busca binária e comparação do tempo de execução no pior caso. Turma do Noturno: Roteiro da aula	Introdução à C/C++ Ponteiros Tutorial C++ Roteiro da aula
27/09: 3^a-feira	Aula teórica. (4) árvores binárias de pesquisa com balanceamento: (4.1) árvores AVL (SZWARCFITER p.130); Especificação do projeto da disciplina	Árvores AVL
30/09: 6^a-feira	Aula prática. Implementação de árvore binária de busca.	Roteiro da aula ABB
04/10: 3^a-feira	Aula teórica. (4) árvores binárias de pesquisa com balanceamento: (4.2) árvores rubro-negras (CORMEN p. 220; SZWARCFITER p.144). Entrega da formação da equipe e da escolha do tema do projeto (atividade no TIDIA)	Árvores RN
07/10: 6^a-feira	Aula prática. Implementação de árvore AVL.	Roteiro da aula
11/10: 3^a-feira	Aula teórica. Técnicas de pesquisa (algoritmos e complexidade): (5) pesquisa digital: (5.1) Trie (FOLK p.525; ZIVIANI p.172); (5.2) Patricia (SZWARCFITER p.268; ZIVIANI p.173);	Árvores Trie
14/10: 6^a-feira	Aula prática. Implementação de uma árvore trie Temas, Equipes e Datas de Apresentação	Roteiro da aula
18/10: 3^a-feira	Aula teórica. Técnicas de pesquisa (algoritmos e complexidade): (6) hashing (CORMEN p.179; FOLK p.463; SZWARCFITER p.227; ZIVIANI p.178);	Hashing
21/10: 6^a-feira	Aula prática. Implementação de um índice remissivo usando árvore trie e hashing	Roteiro da aula
25/10: 3^a-feira	Aula teórica. Técnicas de pesquisa (algoritmos e complexidade): (7) union-find (CORMEN p.398, ZIVIANI p.301);	Union-find
28/10: 6^a-feira	FERIADO
01/11: 3^a-feira	Aula teórica. Compressão de dados: algoritmo de Huffman (CORMEN p.310; SZWARCFITER p.294; ZIVIANI p.324);	Huffman
04/11: 6^a-feira	Aula prática. Implementação de um índice remissivo usando árvore trie e hashing (continuação)
08/11: 3^a-feira	Aula teórica. Representação, organização e gerenciamento de dados em memória secundária. Técnicas de pesquisa (algoritmos e complexidade): (1) acesso sequencial indexado (FOLK p.424; ZIVIANI p.219); (2) árvores B (CORMEN p.349; FOLK p.387; SZWARCFITER p.160; ZIVIANI p.225);	Acesso Seq. Ind. Árvores B Árvores B*
11/11: 6^a-feira	Aula prática. Técnicas de ordenação: ordenação externa (FOLK p.318; ZIVIANI p.126)	Ordenação Externa
15/11: 3^a-feira	FERIADO
18/11: 6^a-feira	Aula prática. Aula de exercícios.
22/11: 3^a-feira	Prova Notas Parciais (prova e atividades) Notas Finais (faltam 3 alunos para apresentar projeto) Notas Finais	Lista de exercícios
25/11: 6^a-feira	Apresentação de Projetos Prazo de entrega do artigo: 24/11 (Atividade no TIDIA) AS APRESENTAÇÕES SERÃO NA SALA S305-3 (não no lab)
29/11: 3^a-feira	Apresentação de Projetos Prazo de entrega do artigo: 24/11 (Atividade no TIDIA)
02/12: 6^a-feira	~~Avaliação Substitutiva~~ Técnicas de ordenação: ordenação externa (FOLK p.318; ZIVIANI p.126) Aula para tirar dúvidas para a REC	Ordenação Externa
06/12: 3^a-feira	Avaliação de Recuperação Notas Finais com REC
09/12: 6^a-feira	Vista de Prova e Pedido de Revisão Notas Finais resultantes
13/12: 3^a-feira	Lançamento de Notas

Letícia Rodrigues Bueno