2021 1 APS para a AV2 Teoria em Grafos

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

CENTRO UNIVERSITÁRIO CARIOCA – UNICARIOCA 
TEORIA EM GRAFOS – PROF.: JÚLIO SILVEIRA – 2021/1 
ATIVIDADE SUPERVISIONADA PARA A AV2 
 
 TRABALHO EM GRUPO: entre QUATRO ou SEIS ALUNOS: SOMENTE aceitarei os trabalhos com esta configuração. 
 FORMA DE ENTREGA: postagem de arquivo EXCLUSIVAMENTE no formato PDF, no link disponível no AVA. 
 DATA DA ENTREGA: informada no próprio link para a postagem do arquivo. 
 FORMATO DO TRABALHO: 
O arquivo PDF gerado a partir de um editor eletrônico de textos e gráficos (para desenho dos grafos/árvores). 
NÃO SERÃO CONSIDERADAS postagens com FOTOS ou com TEXTO MANUSCRITO. 
 LEIA ATENTAMENTE AS INSTRUÇÕES: o DESENVOLVIMENTO DA QUESTÃO É OBRIGATÓRIO, quando solicitado! 
 MUITO IMPORTANTE: trabalho com indícios de similaridade, todos serão avaliados com grau ZERO. 
 ATENÇÃO: o cabeçalho do arquivo deve conter a turma e o nome completo dos integrantes. 
INSERÇÃO EM ÁRVORES AVL 
O grupo deverá demonstrar o passo a passo da criação de uma ÁRVORE AVL. Os nós desta árvore serão rotulados 
COM TODAS AS LETRAS QUE COMPÕEM OS NOMES COMPLETOS dos integrantes do grupo. Cada nó é rotulado com uma 
letra, e as letras serão inseridas, uma a uma, segundo instruções descritas abaixo. 
 Considere os nomes completos de todos os integrantes, ordenados alfabeticamente (em ordem crescente), 
SEM ABREVIATURAS, com TODAS AS LETRAS MAIÚSCULAS, e SEM ACENTUAÇÃO (INSERIR A LETRA SEM O ACENTO). 
 As letras serão inseridas uma a uma, de acordo com a ordem alfabética. Uma letra repetida será considerada 
apenas na primeira vez que ocorrer. Como exemplo, considere um grupo hipotético com os integrantes: 
 
 Aléx dos Santos; Bruna César Paiva; Chyntia Ferraz Mendes; Geraldo José Queiroz 
 O grupo do exemplo acima irá inserir as seguintes letras, considerando maiúsculas e sem os acentos, ignorando 
as repetições, e listados os nomes completos em ordem alfabética. Serão então inseridas, nesta ordem: 
 
 A L E X D O S N T B R U C P I V H Y F Z M G J Q 
 Incialmente a árvore está vazia. As letras são inseridas uma a uma. No exemplo acima, serão 24 inserções. 
 A cada inserção de uma letra, o grupo deverá: 
a. Indicar qual será a letra inserida; 
b. Exibir a árvore IMEDIATAMENTE APÓS a inserção. 
c. Caso a árvore do item b fique desbalanceada, além da própria figura da letra b, deve-se também: 
i. indicar qual será o nó v a sofrer rotação, qual o valor do balanço de v, e qual é o tipo da rotação a ser 
aplicada ao nó v: ESQUERDA, DIREITA, DUPLA ESQUERDA ou DUPLA DIREITA; e 
ii. exibir a árvore APÓS A ROTAÇÃO DO NÓ v. 
 Desta forma, alguns nós irão gerar apenas uma figura, e alguns nós irão gerar duas figuras. 
 ATENÇÃO nas figuras: indicar nitidamente o nó a sofrer rotação, qual é o seu balanço, e qual o tipo de rotação. 
 NÃO ESQUECER!!!! No cabeçalho do trabalho, listar os nomes COMPLETOS de TODOS os integrantes (entre 4 e 6 
nomes), e EM ORDEM ALFABÉTICA. ISTO TAMBÉM SERÁ CONSIDERADO NA AVALIAÇÃO!!! 
REFERÊNCIAS: 
• CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L.; STEIN, C. Algoritmos – Teoria e Prática. 
Tradução da 3ª edição americana. Rio de Janeiro: Elsevier, 2012. 
• SZWARCFITER, J. L.; MARKENZON, L. Estrutura de Dados e seus Algoritmos. Rio de Janeiro: LTC, 1997 
• http://videoaula.rnp.br/v.php?f=/cederj/sistemas_comp/ead05007/Aula_023/Aula_023.xml 
• http://videoaula.rnp.br/v.php?f=/cederj/sistemas_comp/ead05007/Aula_024/Aula_024.xml 
• http://wiki.icmc.usp.br/images/f/f0/AVL.pdf 
BONS ESTUDOS! 
http://videoaula.rnp.br/v.php?f=/cederj/sistemas_comp/ead05007/Aula_023/Aula_023.xml
http://videoaula.rnp.br/v.php?f=/cederj/sistemas_comp/ead05007/Aula_024/Aula_024.xml
http://wiki.icmc.usp.br/images/f/f0/AVL.pdf