EEX0030_Plano_de_ensino

Prévia do material em texto

COMPLEXIDADE DE ALGORITMOS ­ EEX0030
COMPLEXIDADE DE ALGORITMOS 22/09/2021
Contextualização
Ultimamente a linguagem Python tem crescido vertiginosamente devido a sua facilidade de programação
e uma grande biblioteca de funções. No âmbito do desenvolvimento a cada dia que passa são maiores as
pressões para um desenvolvimento rápido, surgindo modelos de desenvolvimento denominado de RAD
(Rapid Application Development ou desenvolvimento rápido de aplicações), que visam desenvolver
software de forma incremental, enfatizando um ciclo de desenvolvimento curto, visando um
desenvolvimento mais rápido e melhor. A disciplina Desenvolvimento Rápido de Aplicações em Python
tem como objetivo principal aproximar o mundo do real mundo virtual, através da computação, visando
ajudar ao aluno desenvolver projetos usando o modelo RAD, a linguagem Python e frameworks como
suporte.
Ementa
Algoritmos de ordenação. Árvores Binárias. Árvores AVL. Grafos. Analise de complexidade de
algoritmos. Recursividade.
Objetivos Gerais
Possibilitar ao aluno o conhecimento de algoritmos de ordenação, bem como conhecer estruturas de
dados como árvores e grafos, bem como análise da complexidade de algoritmos e algoritmos recursivos.
Objetivos Específicos
Conhecer diferentes algoritmos de ordenação Conhecer os conceitos e percurso de árvores binárias e
AVL. Identificar a complexidade de algoritmos com base na notação O. Identificar quando usar a
recursividade para algoritmos mais eficientes.
Conteúdos
Tema 1: Análise de algoritmos 1.1 ­ Conceitos de construção de algoritmos 1.2 ­ Estruturas de dados
manipuladas pelos algoritmos 1.3 ­ Notação O e suas aplicações práticas 1.4 ­ Análise da complexidade
dos algoritmos. Tema 2: Recursividade 2.1 ­ Definição de recursividade de software (RAD) 2.2 ­
Situações de uso da recursividade 2.3 ­ Exemplos de funções recursivas Tema 3: Algoritmos de
ordenação avançados 3.1 ­ Algoritmos de ordenação elementares 3.2 ­ Algoritmo de ordenação por
intercalação (merge sort) 3.3 ­ Algoritmo de ordenação rápida (quick sort) 3.4 ­ Algoritmo de ordenação
shell sort Tema 4: Algoritmos em árvores binárias e árvores AVL 4.1 ­ Tipos de percursos em árvores
binárias 4.2 ­ Árvores binárias de busca 4.3 ­ Árvore balanceada 4.4 ­ Árvore AVL Tema 5: Algoritmos
em grafos 5.1 ­ Conceitos de grafos 5.2 ­ Representações de grafos 5.3 ­ Algoritmos de busca em grafos
5.4 ­ Problema de custo mínimo usando grafo ponderado
Procedimentos de Avaliação
A avaliação da disciplina segue as normas regimentais da Instituição. Nesta disciplina o aluno será
avaliado por seu desempenho nas avaliações presenciais, bem como nos simulados que realizar. No que
se refere as avaliações presenciais , o aluno agendará a realização da AV e, se necessário ­ e
posteriormente ­ a AVS. As referidas avaliações, realizadas no polo de apoio EAD, envolvem questões
objetivas e/ou discursivas a partir do banco de questão da disciplina e consideram diferentes níveis de
complexidade e diferentes níveis cognitivos. Os simulados tomam como base o conteúdo de toda a
disciplina e permitem a obtenção de até 2,0 pontos na média, desde que o aluno obtenha, pelo menos,
nota 4,0 na AV e na AVS.
Bibliografia Básica
BORIN, V.P. Estrutura de dados. Curitiba: Contentus. 2020. Disponível em
https://plataforma.bvirtual.com.br/Leitor/Publicacao/184420/pdf/0?
code=2LPyyy96nttDOwx8nj/HwhsFAxCDWmikVl+ZqkvaIxqbeWvqB1IrYiSfZQf1ISwqkFk9TuzWW2
0AZZQ3JKvlOg== ASCENCIO, A.F.G.; ARAUJO, G.S. Estruturas de dados: Algoritmos, análise de
complexidade e implementações. São Paulo: Prentice Hall, 2010. Disponível em
https://plataforma.bvirtual.com.br/Leitor/Publicacao/1995/pdf/0?
code=SgQsjGBCCdeGt1AoC93i5F0mXlhn7NMcaT6V4ZzYF1oYWvOxnzapHPnJBQ4kO5+iFzNAHiA
UQrTQB/G+P93org== PUGA, S.; RISSETTI, G. Lógica de Programação e estruturas de dados, com
aplicações em JAVA. 2ª ed. São Paulo: Pearson Prentice Hall. 2009. Disponível em
https://plataforma.bvirtual.com.br/Leitor/Publicacao/447/pdf/0?
code=sz7Xfx92rkCi4q+FZPjWJUKOPI0YT++pWdjUGdjGaXYhoVozY4VeOIKY+qlT5F8pzN/jK+9Ktv
BTggiJmeRPNQ==
Bibliografia Complementar
SIMÕES, PEREIRA, J.M.S. Grafos e redes: teorias e algoritmos básicos. 1ª ed. Rio de Janeiro:
Interciência. 2013. Disponível em https://plataforma.bvirtual.com.br/Leitor/Publicacao/42049/pdf/0?
code=IgJQC/bM455wXE7ouBHRU6UcbnL8MHbdpPTk1bg7psenT6+siSOin7Xl4bPtlE+YNgp7yCrLeg
weQEZYV3xDUQ== TUCKER, Allen; NOONAN, Robert. Linguagens de Programação: Princípios e
Paradigmas. 11ª ed. Porto Alegre: Grupo A. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788563308566/cfi/0!/4/2@100:0.00 BOAVENTURA
NETTO, P.O.; JURKIEWICZ, S. Grafos: Introdução e prática. São Paulo: Blucher. 2009. Disponível em
https://plataforma.bvirtual.com.br/Leitor/Publicacao/173348/pdf/0?
code=UoUo3+IB8NCHRxKWvJrfCnWDmqdYcVIDe/v9kdwEufcp9Zgi8Muxy2DAZLo1M3RLKBtazI
ARik3mB9i0qRKC8A== GUEDES, S. (Org). Lógica de programação algorítmica. São Paulo: Pearson
Education do Brasil. 2014 (Biblioteca universitária Pearson). Disponível em
https://plataforma.bvirtual.com.br/Leitor/Publicacao/22146/pdf/0?
code=Gd6l/Er9nB8B3m1M966H89SgHV7eRLh7vBS9H15vqSblaw/AA8j6BsFyGS5/u26sDeNDlscN8cx
CLzQVEYJ9gw== FORBELLONE. A.L.V.; EBERSPACHER, H.F. Lógica de Programação. A
construção de algoritmos e estruturas de dados. 3ª ed. São Paulo: Pearson Prentice Hall. Disponível em
https://plataforma.bvirtual.com.br/Leitor/Publicacao/323/pdf/0?
code=3T7sRBwmA2QpVm/Hchg73eJLZhoEjrnNaiuXrjcwxIbubJt+vCbbaP7AgQyydxb3P/wRU5v9q1+
DWcz1PxIBRg==
Outras Informações
COMPLEXIDADE DE ALGORITMOS ­ EEX0030
COMPLEXIDADE DE ALGORITMOS 22/09/2021
Contextualização
Ultimamente a linguagem Python tem crescido vertiginosamente devido a sua facilidade de programação
e uma grande biblioteca de funções. No âmbito do desenvolvimento a cada dia que passa são maiores as
pressões para um desenvolvimento rápido, surgindo modelos de desenvolvimento denominado de RAD
(Rapid Application Development ou desenvolvimento rápido de aplicações), que visam desenvolver
software de forma incremental, enfatizando um ciclo de desenvolvimento curto, visando um
desenvolvimento mais rápido e melhor. A disciplina Desenvolvimento Rápido de Aplicações em Python
tem como objetivo principal aproximar o mundo do real mundo virtual, através da computação, visando
ajudar ao aluno desenvolver projetos usando o modelo RAD, a linguagem Python e frameworks como
suporte.
Ementa
Algoritmos de ordenação. Árvores Binárias. Árvores AVL. Grafos. Analise de complexidade de
algoritmos. Recursividade.
Objetivos Gerais
Possibilitar ao aluno o conhecimento de algoritmos de ordenação, bem como conhecer estruturas de
dados como árvores e grafos, bem como análise da complexidade de algoritmos e algoritmos recursivos.
Objetivos Específicos
Conhecer diferentes algoritmos de ordenação Conhecer os conceitos e percurso de árvores binárias e
AVL. Identificar a complexidade de algoritmos com base na notação O. Identificar quando usar a
recursividade para algoritmos mais eficientes.
Conteúdos
Tema 1: Análise de algoritmos 1.1 ­ Conceitos de construção de algoritmos 1.2 ­ Estruturas de dados
manipuladas pelos algoritmos 1.3 ­ Notação O e suas aplicações práticas 1.4 ­ Análise da complexidade
dos algoritmos. Tema 2: Recursividade 2.1 ­ Definição de recursividade de software (RAD) 2.2 ­
Situações de uso da recursividade 2.3 ­ Exemplos de funções recursivas Tema 3: Algoritmos de
ordenação avançados 3.1 ­ Algoritmos de ordenação elementares 3.2 ­ Algoritmo de ordenação por
intercalação (merge sort) 3.3 ­ Algoritmo de ordenação rápida (quick sort) 3.4 ­ Algoritmo de ordenação
shell sort Tema 4: Algoritmos em árvores binárias e árvores AVL 4.1 ­ Tipos de percursos em árvores
binárias 4.2 ­ Árvores binárias de busca 4.3 ­ Árvore balanceada 4.4 ­ Árvore AVL Tema 5: Algoritmos
em grafos 5.1 ­ Conceitos de grafos 5.2 ­ Representações de grafos 5.3 ­ Algoritmos de busca em grafos
5.4 ­ Problema de custo mínimo usando grafo ponderado
Procedimentos de Avaliação
A avaliação da disciplina segue as normas regimentais da Instituição.Nesta disciplina o aluno será
avaliado por seu desempenho nas avaliações presenciais, bem como nos simulados que realizar. No que
se refere as avaliações presenciais , o aluno agendará a realização da AV e, se necessário ­ e
posteriormente ­ a AVS. As referidas avaliações, realizadas no polo de apoio EAD, envolvem questões
objetivas e/ou discursivas a partir do banco de questão da disciplina e consideram diferentes níveis de
complexidade e diferentes níveis cognitivos. Os simulados tomam como base o conteúdo de toda a
disciplina e permitem a obtenção de até 2,0 pontos na média, desde que o aluno obtenha, pelo menos,
nota 4,0 na AV e na AVS.
Bibliografia Básica
BORIN, V.P. Estrutura de dados. Curitiba: Contentus. 2020. Disponível em
https://plataforma.bvirtual.com.br/Leitor/Publicacao/184420/pdf/0?
code=2LPyyy96nttDOwx8nj/HwhsFAxCDWmikVl+ZqkvaIxqbeWvqB1IrYiSfZQf1ISwqkFk9TuzWW2
0AZZQ3JKvlOg== ASCENCIO, A.F.G.; ARAUJO, G.S. Estruturas de dados: Algoritmos, análise de
complexidade e implementações. São Paulo: Prentice Hall, 2010. Disponível em
https://plataforma.bvirtual.com.br/Leitor/Publicacao/1995/pdf/0?
code=SgQsjGBCCdeGt1AoC93i5F0mXlhn7NMcaT6V4ZzYF1oYWvOxnzapHPnJBQ4kO5+iFzNAHiA
UQrTQB/G+P93org== PUGA, S.; RISSETTI, G. Lógica de Programação e estruturas de dados, com
aplicações em JAVA. 2ª ed. São Paulo: Pearson Prentice Hall. 2009. Disponível em
https://plataforma.bvirtual.com.br/Leitor/Publicacao/447/pdf/0?
code=sz7Xfx92rkCi4q+FZPjWJUKOPI0YT++pWdjUGdjGaXYhoVozY4VeOIKY+qlT5F8pzN/jK+9Ktv
BTggiJmeRPNQ==
Bibliografia Complementar
SIMÕES, PEREIRA, J.M.S. Grafos e redes: teorias e algoritmos básicos. 1ª ed. Rio de Janeiro:
Interciência. 2013. Disponível em https://plataforma.bvirtual.com.br/Leitor/Publicacao/42049/pdf/0?
code=IgJQC/bM455wXE7ouBHRU6UcbnL8MHbdpPTk1bg7psenT6+siSOin7Xl4bPtlE+YNgp7yCrLeg
weQEZYV3xDUQ== TUCKER, Allen; NOONAN, Robert. Linguagens de Programação: Princípios e
Paradigmas. 11ª ed. Porto Alegre: Grupo A. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788563308566/cfi/0!/4/2@100:0.00 BOAVENTURA
NETTO, P.O.; JURKIEWICZ, S. Grafos: Introdução e prática. São Paulo: Blucher. 2009. Disponível em
https://plataforma.bvirtual.com.br/Leitor/Publicacao/173348/pdf/0?
code=UoUo3+IB8NCHRxKWvJrfCnWDmqdYcVIDe/v9kdwEufcp9Zgi8Muxy2DAZLo1M3RLKBtazI
ARik3mB9i0qRKC8A== GUEDES, S. (Org). Lógica de programação algorítmica. São Paulo: Pearson
Education do Brasil. 2014 (Biblioteca universitária Pearson). Disponível em
https://plataforma.bvirtual.com.br/Leitor/Publicacao/22146/pdf/0?
code=Gd6l/Er9nB8B3m1M966H89SgHV7eRLh7vBS9H15vqSblaw/AA8j6BsFyGS5/u26sDeNDlscN8cx
CLzQVEYJ9gw== FORBELLONE. A.L.V.; EBERSPACHER, H.F. Lógica de Programação. A
construção de algoritmos e estruturas de dados. 3ª ed. São Paulo: Pearson Prentice Hall. Disponível em
https://plataforma.bvirtual.com.br/Leitor/Publicacao/323/pdf/0?
code=3T7sRBwmA2QpVm/Hchg73eJLZhoEjrnNaiuXrjcwxIbubJt+vCbbaP7AgQyydxb3P/wRU5v9q1+
DWcz1PxIBRg==
Outras Informações