Plano de Ensino Matemática Aplicada UNIFACS

Prévia do material em texto

PLANO DE ENSINO 
 
Escola Arquitetura, Engenharia e Tecnologia da Informação – EAETI 
Curso(s) Sistemas de Informação 
Disciplina MATEMÁTICA APLICADA Código ESI019 
CH Total 60h CH Teórica 60h 
CH 
Prática 0h 
Trabalho Efetivo 
Discente 10h 
Bloco de 
conhecimento Sistemas Computacionais e Programação 
 
1. EMENTA 
Grafos e isomorfismo entre grafos. Representação computacional de um grafo. 
Conectividade de vértices e arestas. Coloração, Emparelhamento e Planaridade. Árvore 
geradora mínima. Algoritmos de busca e de ordenação. Algoritmo de caminho mínimo. 
Grafos hamiltonianos e eulerianos: Problema do caixeiro viajante e do carteiro chinês. 
Grafos orientados: fluxos em redes. Programação Linear. Modelagem de problemas: 
Modelos lineares. Problemas de alocação de recursos, programação da produção, 
localização, e roteamento. Problemas Inteiros. Método simplex. Noções de dualidade e 
de análise de sensibilidade. 
 
2. JUSTIFICATIVA 
Muitos dos problemas de forte caráter prático encontrados hoje podem ser solucionados 
por algoritmos polinomiais. Dessa forma, o domínio de técnicas de teoria dos grafos e de 
programação linear torna-se imprescindível para a modelagem e solução de tais 
problemas. Além disso, programação linear é uma ferramenta de grande utilidade no 
processo de tomada de decisões de grandes empresa. 
Esta disciplina visa fornecer ao aluno conhecimentos que deem suporte tanto à solução 
de problemas práticos encontrados no mercado de trabalho quanto em problemas 
típicos de Ciência da Computação encontrados no meio acadêmico 
 
3. CONTEÚDO PROGRAMÁTICO 
I. Introdução à Teoria dos Grafos 
● Motivação Histórica 
II. Conceitos Básicos sobre Grafos 
● Definição formal de Grafo 
● Adjacência e incidência 
● Grafos simples 
● Subgrafos 
III. Representação Computacional 
IV. Conectividade de vértices e arestas 
Página 1 de 6 
 
 
 
● Passeios, caminhos, trilhas, circuitos e ciclos 
● Distância 
V. Coloração 
VI. Emparelhamento 
VII. Planaridade 
VIII. Árvores 
● Árvore geradora 
● Árvore geradora mínima (máxima) 
● Algoritmo de Prim 
● Algoritmo de Kruskal 
● Algoritmo de Boruvka 
● Algoritmos de busca e ordenação 
IX. Algoritmos de caminho mínimo 
● Algoritmo de Dijkstra 
X. Grafos Eulerianos e Hamiltonianos 
● Problema do Caixeiro Viajante 
● Problema do Carteiro Chinês 
XI. Grafos Orientados 
● Fluxos em Redes e o Probl 
● ema do Fluxo Máximo 
XII. Programação linear 
● Modelagem Matemática de Problemas 
● Programação Linear Inteira 
XIII. Modelos / Problemas de Programação Linear 
● Problema de Alocação de Recursos, Programação de Produção, Roteamento, 
● Localização e Transporte 
XIV. Método Simplex. 
● Método Gráfico de Resolução 
● Algoritmo do Simplex 
● Método das Duas Fases 
● Dualidade 
● Análise de sensibilidade 
 
4. OBJETIVOS 
Geral: 
Resolver problemas de otimização através da aplicação dos conceitos matemáticos 
envolvidos na Teoria dos Grafos e na Programação Linear, além de analisar as 
prováveis consequências futuras de ações alternativas 
Página 2 de 6 
 
 
 
Específicos: 
1. Identificar problemas de otimização; 
2. Modelar problemas de otimização utilizando grafos; 
3. Resolver problemas de otimização modelados através de grafos; 
4. Modelar matematicamente problemas de otimização 
5. Resolver problemas de otimização utilizando métodos exatos 
 
5. COMPETÊNCIAS E HABILIDADES (Específicas) 
Descrição Objetivos Específicos 
I – Selecionar, configurar e gerenciar tecnologias da Informação nas 
Organizações; 1 a 5 
II - Atuar nas organizações públicas e privadas, para atingir os 
objetivos organizacionais, usando as modernas tecnologias da 
informação; 
2 a 5 
III - Identificar oportunidades de mudanças e projetar soluções usando 
tecnologias da informação nas organizações; 2 a 5 
IV - Comparar soluções alternativas para demandas organizacionais, 
incluindo a análise de risco e integração das soluções propostas; 2 a 5 
V - Gerenciar, manter e garantir a segurança dos sistemas de 
informação e da infraestrutura de Tecnologia da Informação de 
uma organização; 
Não se Aplica 
VI - Modelar e implementar soluções de Tecnologia de Informação em 
variados domínios de aplicação; 2 e 4 
VII - Aplicar métodos e técnicas de negociação; Não se Aplica 
VIII - Interagir com pessoas que atuam no processo de negócio 
apoiado pelo Sistema de Informação; Não se Aplica 
IX - Gerenciar equipes de trabalho no desenvolvimento de Sistemas de 
Informação; Não se Aplica 
X - Aprender sobre novos processos de negócio; Não se Aplica 
XI - Representar os modelos mentais dos indivíduos e do coletivo na 
análise de requisitos de um Sistema de Informação; 2 a 5 
XII - Aplicar conceitos, métodos, técnicas e ferramentas de 
gerenciamento de projetos em sua área de atuação. 1 a 5 
 
6. CONTEÚDOS CURRICULARES (CR99-01 – Currículo de Referência da SBC - 
2003) 
Descrição Objetivos Específicos 
Fundamentos da Computação 1 a 3 
 
7. DISPOSITIVOS LEGAIS 
Página 3 de 6 
 
 
 
Descrição 
CR99-01 – Currículo de Referência da Sociedade Brasileira de Computação – 2003 
 
 
 
8. CRONOGRAMA DE AULAS 
Título Descrição 
Aula 01:​ Introdução à Teoria dos Grafos 
Apresentação da disciplina e do Plano de 
Ensino 
Introdução à Teoria dos Grafos 
Aula 02: ​Conceitos Básicos sobre Grafos 
Conceitos Básicos sobre Grafos 
Representações computacionais usuais de 
grafos 
Aula 03: ​Isomorfismo Isomorfismo 
Aula 04:​ Planaridade Homeomorfismo 
Aula 05: ​Coloração e Emparelhamento 
Coloração e Emparelhamento 
Atividade integradora:​ Laboratório 
(4h) 
Aula 06: ​Algoritmos sobre Árvores Árvores e Algoritmos 
Aula 07​: Algoritmos sobre Grafos Orientados Grafos Orientados e Algoritmos 
Aula 08: ​Aula de Revisão 
Revisão e Exercícios 
Atividade integradora:​ Laboratório 
(4h) 
Aula 09: ​Modelagem Matemática de Problemas 
de PL 
Introdução à Programação Linear 
Modelagem Matemática de Problemas de 
Programação Linear 
Aula 10: 1ª avaliação 1ª avaliação 
Aula 11: ​Método Gráfico de Resolução 
Método Gráfico de Resolução 
Atividade integradora:​ Laboratório 
(4h) 
Aula 12: ​Método SIMPLEX Método SIMPLEX 
Aula 13:​ Método SIMPLEX 
Exercícios sobre o Método SIMPLEX 
Atividade integradora:​ Laboratório 
(4h) 
Aula 14: ​Método SIMPLEX – Aula de Exercícios Exercícios sobre o Método SIMPLEX 
Aula 15: ​Método da Função Objetivo Auxiliar 
Método da Função Objetivo Auxiliar 
(Método das Duas Fases) 
Atividade integradora:​ Laboratório 
(4h) 
Aula 16: ​Dualidade e Análise de Sensibilidade Dualidade e Análise de Sensibilidade 
Aula 17: ​Aula de Revisão 
Revisão e Exercícios 
Atividade integradora:​ Laboratório 
(4h) 
Aula 18: 2ª Avaliação 2ª avaliação 
Aula 19:​ ​Segunda chamada Segunda Chamada 
Aula 20: 3ª Avaliação 3ª valiação 
Página 4 de 6 
 
 
 
 
9. ESTRATÉGIA DE ENSINO 
● Aulas teóricas, práticas e trabalhos práticos para assimilação dos conceitos 
apresentados. 
● Resolução de listas de exercícios como estímulo na prática do estudo individual. 
 
10. MATERIAIS E EQUIPAMENTOS NECESSÁRIOS 
● Sala de aula com quadro e projetor multimídia para a apresentação dos 
conceitos. 
● Laboratório com IDE Code::Blocks disponível para as aulas práticas. 
 
11. AVALIAÇÃO DE APRENDIZAGEM 
O aluno será avaliado em três momentos distintos. Serão utilizados os seguintes 
instrumentos: 
 
Tipo Descrição Valor Peso 
Avaliação I Prova escrita individual 10,0 3,0 
Avaliação II A - Trabalho deGrafos 4,0 3,2 
B - Trabalho Simplex 6,0 
C - Avaliação de Integração Curricular (AIC) 10,0 0,8 
Avaliação III Prova escrita individual 10,0 3,0 
 
 
12. TRABALHO EFETIVO DISCENTE 
● Lista de Exercícios de Fixação 
● Exercícios Práticos 
 
13. REFERÊNCIAS 
Básicas 
● NETO, Paulo O. B., ​Grafos: teoria, modelos e algoritmos​, edt. Edgard 
Blücher Ltda., 2a. ediçao, 1996 
● SILVA, Ermes Medeiros et al. Pesquisa Operacional​, 3ªEd. Editora Atlas, 
São Paulo. 2008. 
● LUNA, H. P. e Goldbarg, M. C. ​Otimização Combinatória e Programação 
Linear​. Editora Campus, Rio de Janeiro. 2000. 
Complementares 
● DIESTEL, Richard. ​Graph Theory​, Springer 2000 
Página 5 de 6 
 
 
 
● BONDY, James Adrian e Murty, U. S. Rama. ​Graph Theory with 
Applications​, MacMillan, 1976. 
● RABUSKE, M. A. ​Introdução à teoria dos grafos​, Ed. Da UFSC, 1992. 
● STEIN, Clifford; DRYSDALE, Robert L; BOGART, Kenneth. ​Matemática 
discreta para ciência da computação.​ Ed. Pearson. 
● ASCENCIO, Ana Fernanda Gomes; ARAÚJO, Graziela Santos de. 
Estrutura de Dados: algoritmos, análise da complexidade e 
implementações em Java e C/C++.​ Ed. Pearson. 
 
Página 6 de 6