UNIVERSIDADE FEDERAL DO PARÁ INSTITUTO DE CIÊNCIAS EXATAS ... · - Conhecer os grafos dirigidos e não dirigidos e seus ... Isomorfismo de grafos f. Grafos regulares, completos

UNIVERSIDADE FEDERAL DO PARÁ INSTITUTO DE CIÊNCIAS EXATAS E NATURAIS PROGRAMA DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO

1. Nome da Disciplina

Tópicos Especiais em Computação: Análise de Algoritmos

2. Professor Responsável

Francisco Edson Lopes da Rocha

3. Carga Horária

60 horas

4. Créditos

4

5. Pré-Requisitos

Teoria de Grafos e Programação

6. Objetivos

Ao final da disciplina os alunos deverão estar aptos a: (i) entender e aplicar as técnicas de prova da correção de algoritmos; e (ii) dominar e aplicar técnicas de identificação do desempenho de algoritmos.

7. Ementa

Conceitos Básicos. Comparação Assintótica de Funções. Solução de Recorrências. Técnicas de Projetos de Algoritmos. Conceitos Básicos sobre Complexidade de algoritmos. Problemas Teóricos e Práticos.

8. Conteúdo Programático

1. Conceitos Básicos: Exercícios preliminares; Apresentação das técnicas de prova matemática; Problemas, instâncias, algoritmos e tempo.

2. Comparação Assintótica: Análise assintótica: ordens Ο, Ω e Θ.

3. Solução de recorrências: Recursão.

4. Análise de algoritmos: Análise de algoritmos de ordenação e pesquisa; análise de algoritmos em grafos; análise de algoritmos numéricos; análise de algoritmos de busca textual.

5. Paradigmas de projeto e análise: Divisão e conquista; Programação dinâmica; Algoritmos gulosos; Tempo amortizado.

6. Complexidade: Introdução à teoria da complexidade; Problemas NP-completos.

9. Metodologia

Aulas expositivas e seminários.


10. Recursos

Computador, data show, quadro branco e web.

11. Avaliação

Provas, trabalhos práticos, relatórios técnicos, seminários, freqüência.

12. Bibliografia

[CLRS3] Th.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd edition, MIT Press, 2009.

KT] Jon Kleinberg, Éva Tardos, Algorithm Design, Addison-Wesley, 2005. [DPV] S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani, Algorithms, McGraw-Hill, 2006.

IP] Ian Parberry, Problems on Algorithms, Prentice Hall, 1995.

[PG] Ian Parberry e William Gasarch, Problems on Algorithms, 2nd edition, 2002.

[NN] Richard E. Neapolitan, Kumarss Naimipour, Foundations of Algorithms Using Java Pseudocode, Jones & Bartlett, 2004.

[AU] A.V. Aho, J. D. Ullman, Foundations of Computer Science (C edition), Computer Science Press, 1997.

Bentley, Programming Pearls, 2nd.ed., Addison-Wesley, 2000.

D.E. Knuth, Fundamental Algorithms, 3rd.ed., (vol. 1 de "The Art of Computer Programming"), Addison-Wesley, 1997.

D.E. Knuth, Seminumerical Algorithms, 3rd.ed., (vol. 2 de "The Art of Computer Programming"), Addison-Wesley, 1997.

D.E. Knuth, Sorting and Searching, 2nd.ed., (vol. 3 de "The Art of Computer Programming"), Addison-Wesley, 1998.

D.E. Knuth, Selected Papers on Analysis of Algorithms, Center for the Study of Language and Information (CSLI), 2000.

Ph. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.


1. Nome da Disciplina TÓPICOS ESPECIAIS EM COMPUTAÇÃO DE ALTO DESEMPENHO 2. Professor Responsável JOSIVALDO DE SOUZA ARAÚJO 3. Carga Horária 60 HORAS 4. Créditos 04 CRÉDITOS 5. Pré-Requisitos Noções de Rede de Computadores 6. Objetivos Proporcionar ao aluno um entendimento sobre os princípios nos quais está baseada a computação de alto desempenho, bem como as ferramentas e os modelos que são necessários para se conseguir prover esse tipo de serviço; Compreender as arquiteturas, algoritmos e projetos que servem como base aos sistemas de alto desempenho; Analisar características como desempenho, escalabilidade, heterogeneidade, segurança e tratamento de falhas; Compreender o funcionamento de bibliotecas como Message

Passing Interface (MPI) e Bulk Synchronous Parallelism (BSP) que são utilizadas na computação paralela. 7. Ementa Conceitos de Rede de Computadores. Visão geral de computação de alto desempenho. Modelos de sistemas de alto desempenho. Comunicação em sistemas paralelos e distribuídos. Hardware e Software Paralelo. Ambientes de programação paralela, ferramentas e middlewares. 8. Conteúdo Programático Unidade 1: Noções de Redes de Computadores Unidade 2: Introdução e Modelos da Computação de Alto Desempenho Unidade 3: Cluster de Computadores Unidade 4: Grade de Computadores (Grid Computing) Unidade 5: Computação nas Nuvens (Cloud Computing) Unidade 6: Bibliotecas de Comunicação Paralela Unidade 7: Programação Paralela


9. Metodologia Ao longo do curso, o professor abordará os conteúdos por meio de: Aulas teóricas: exposição de conteúdo através de quadro e datashow;

Desenvolvimento de Trabalhos Práticos através da programação utilizando a linguagem C/C++;

Aulas de exercícios: aplicação e resolução de listas de exercícios;

Seminários a serem realizados pelos alunos sobre aplicações práticas em computação de alto desempenho;

Elaboração de artigos sobre o estado da arte e tecnologias da área; 10. Recursos Além de quadro e datashow usados em sala, será utilizado o ambiente computacional Moodle como suporte à disciplina presencial, onde serão postados materiais extraclasses. Os trabalhos práticos serão desenvolvidos em laboratório com sistema operacional Linux e linguagem de programação C/C++; 11. Avaliação A avaliação da disciplina será realizada da seguinte maneira: 01 Prova Teórica: Capítulos de 01 a 03;

Trabalhos e Listas de Exercícios no Final de cada unidade.

01 Prova Teórica: Capítulos de 04 a 06

Trabalhos e Listas de Exercícios no Final de cada unidade.

01 Trabalho Prático de Programação Paralela: Capítulo 07 12. Bibliografia

PACHECO, Peter S., An Introduction to Parallel Programming. Morgan Kaufman, 2011. HWANG, K., DONGARRA, J., FOX, G. C., Distributed and Cloud Computing: From

Parallel Processing to the Internet of Things. Morgan Kaufman, 2011. DONGARRA, J., LASTOVETSKY, A., High Performance Heterogeneous Computing. Wiley, 2009. GRAMA, A., KUMAR, V., GUPTA, A., KARYPIS, G., Introduction to Parallel Computing:

Design and Analysis of Algorithms. 2nd Edition, The Benjamin/Cummings Publishing Company, 2003. JORDAN, H. and ALAGHBAND, G., Fundamentals of Parallel Processing. Prentice Hall, 2003.



Computação evolucionária


Claudomiro de Souza de Sales Junior

3. Carga Horária

60 horas

4. Créditos

4 créditos

5. Pré-Requisitos

Programação

6. Objetivos

Apresentar os conceitos introdutórios sobre computação evolucionária, incluindo o estudo de todas as variantes tradicionais, como algoritmos genéticos, estratégias de evolução, programação evolucionária e programação genética. Além disso, serão vistos temas importantes no contexto de computação evolucionária, como controle de parâmetros, manipulação de restrições e algoritmos evolucionários multiobjetivo. Além disso, serão estudados os artigos mais recentes nessa área. Ao final dessa disciplina espera-se que o aluno seja capaz de implementar e aplicar as técnicas de computação evolucionária aos problemas comumente encontrados na engenharia e na computação, e também estar ciente do estado da arte das técnicas de computação evolucionária.

7. Ementa

Introdução à computação evolucionária, algoritmos genéticos, estratégias de evolução, programação evolucionária, programação genética, controle de parâmetros em algoritmos evolucionários, algoritmos evolucionários multiobjectivo.


1 – Introdução 1.1 – Breve histórico 1.2 – A inspiração da biologia 1.3 – Definição de algoritmos evolucionários 1.4 – Componentes de algoritmo evolucionário 1.5 – Computação evolucionária e otimização global 1.6 – Motivação em usar algoritmos evolucionários 1.7 – Exemplo de aplicações


2 – Algoritmos genéticos 2.1 – Definição 2.2 – Fluxograma de um AG 2.3 – Representação de individuos 2.4 – Calcula de aptidão 2.5 – Mutação 2.6 – Cruzamento 2.7 – Modelos de população 2.8 – Processo de seleção 2.9 – Exemplo de aplicação

3 – Estratégias de evolução 3.1 – Definição 3.2 – Representação 3.3 – mutação 3.4 – Recombinação 3.5 – Seleção 3.6 – Auto-adaptação 3.7 – Exemplo de aplicação 4 – Programação evolucionária 4.1 – Definição 4.2 – Representação 4.3 – Recombinação 4.4 – Seleção 4.5 – Exemplo de aplicação 5 – Programação genética 5.1 – Definição 5.2 - Representação 5.3 – Mutação 5.4 – Recombinação 5.5 – Seleção 5.6 – Inicialização 5.7 – Processo de seleção 5.8 – Exemplo de aplicação 6 – Programação genética 6.1 – Introdução 6.2 – Classificação de técnicas de controle de parâmetros 6.3 – Exemples de algoritmos evolucionários com variação de parâmetros 7 – Algoritmos evolucionários multiobjetivo 7.1 – Problema de otimização multiobjetivo 7.2 – Soluções ótimas de Pareto


7.3 – Dominância e otimalidade de Pareto 7.4 – Objetivos em otimização multiobjetivo 7.5 – Diferença entre otimização mono-objetivo e multiobjetivo 7.6 – Métodos clássicos de otimização multiobjetivo 7.7 – Algoritmos evolutivos para otimização multiobjetivo 7.7.1 – VEGA 7.7.2 – MOGA 7.7.3 – NPGA 7.7.4 – SPEA 7.7.5 – NSGA-II

9. Metodologia

Aulas expositivas, com emprego de recursos visuais (datashow). Exercícios em sala de aula e extraclasse; Trabalhos individuais.

10. Recursos

Quadro magnético Pincéis atômicos e apagador Laboratório com computadores

11. Avaliação

No transcorrer do semestre serão realizadas três avaliações, constando de provas escritas e/ou trabalhos. A última avaliação será um trabalho que constará de um artigo e apresentação sobre a aplicação de técnicas de computação evolucionária as áreas de estudo do aluno ou áreas de interesse.

12. Bibliografia

A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing. Springer, first edition, 2007 Z. Michalewicz, Genetic Algorithms Plus Data Structures Equals Evolution Programs. Secaucus, NJ, USA: Springer-Verlag New York, Inc., 1994. T. Back, F. Hoffmeister, and H. P. Schwefel, “A survey of evolution strategies,” in In Lashon B. Belew, Richard K.; Booker, editor, Proceedings of the 4th International

Conference on Genetic Algorithms, 1991, pp. 2–9. D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley, 1989.


R. I. Haupt and S. E. Haupt, Practical Genetic Algorithms. 2nd ed. Wiley, 1998. K. Deb, Multi-Objective Optimization using Evolutionary Algorithms. John Wiley & Sons, 2001.



Grafos


Nelson Cruz Sampaio Neto

3. Carga Horária

60 (sessenta) horas

4. Créditos

4 (quatro) créditos

5. Pré-Requisitos

Não há

6. Objetivos

Geral: Dotar o aluno de conceitos e algoritmos que possibilitem a abstração de problemas diversos e a solução dos mesmos através de grafos.

Específicos: - Conhecer os conceitos de grafos e suas representações computacionais; - Conhecer os grafos dirigidos e não dirigidos e seus algoritmos; - Conhecer os mecanismos de busca em grafos; e - Conhecer os conceitos de árvore, coloração, fluxo de redes e seus algoritmos.

7. Ementa

Conceitos básicos. Representações. Grafos dirigidos e não dirigidos. Caminhos. Busca em grafos. Conexidade. Árvores. Coloração. Fluxo de redes. Algoritmos em grafos. Aplicações baseadas em grafos.


1. Conceitos básicos a. Revisão de relações b. Definição e notação de grafos c. Grafos, dígrafos e multigrafos d. Operações com grafos e. Isomorfismo de grafos f. Grafos regulares, completos e bipartidos g. Grafos rotulados e valorados h. Grafos planares

2. Representações Computacionais

a. Matriz de adjacência b. Matriz de incidência c. Lista de adjacência d. Bibliotecas para linguagem de programação


3. Grafos dirigidos ou dígrafos

a. Fechos transitivos b. Algoritmos de Warshall c. Ordenação topológica d. Acessibilidade

4. Caminhos em grafos

a. Caminhos e ciclos b. Grafos eulerianos e hamiltonianos c. Busca em largura e em profundidade

5. Conexidade

a. Grafos conexos e desconexos b. Componentes conexos e fortemente conexos c. Pontes e vértices de corte d. Grafo reduzido e. Base e anti-base

6. Árvores

a. Propriedades elementares b. Arborescência c. Árvore geradora d. Árvore de custo mínimo e. Expansão e compactação

7. Coloração de grafos

a. Coloração aproximada b. Coloração de mapas

8. Fluxo de redes

a. Problema do fluxo máximo b. Teorema do fluxo máximo – Corte mínimo

9. Metodologia

As aulas serão expositivas seguidas de exercícios em sala de aula. Além disso, as aulas envolvem seminários e trabalhos extraclasse.

10. Recursos

Quadro branco e data show.

11. Avaliação

O aluno será avaliado através de provas, seminários e trabalhos extraclasse. A disciplina terá 2 (duas) provas com o valor de 10 (dez) pontos cada, seminários totalizando 10 (dez) pontos e trabalhos extraclasse também totalizando 10 (dez) pontos. A nota final será obtida pela média aritmética simples dessas avaliações.


12. Bibliografia

Básica: NETTO, Paulo O. B. Teoria, Modelos e Algoritmos, 4ª Ed. Edgard Blücher. São Paulo, 2006. GERSTING, Judith L. Fundamentos Matemáticos para a Ciência da Computação, 5ª Ed. LTC – Livros Técnicos e Científico, 2004. SZWARCFITER, Jayme L. Grafos e Algoritmos Computacionais. Campus. Rio de Janeiro, 1984. Complementar: LEISERSON, Charles E.; STEIN, C.; RIVEST, Ronald L.; CORMEN, Thomas H. Algoritmos: Teoria e Prática. Tradução da segunda edição americana. Campus, 2002. Capítulos 22 a 26. GROSS, Jonathan L.; YELLEN, J. Graph Theory and Its Applications, Second Edition, Chapman and Hall/CRC, 2005. SEDGEWICK, Robert. Algorithms in Java, Part 5: Graph Algorithms, 3rd Edition, Addison-Wesley Professional, 2003.



Inteligência Artificial Simbólica


Eloi Luiz Favero

3. Carga Horária

60H ou 68H

4. Créditos

4CRE

5. Pré-Requisitos

Não tem

6. Objetivos

Apresentar ao aluno o paradigma de Inteligência Artificial Simbólica, com o estudo de linguagens, modelagens, métodos e técnicas para serem usados na solução de problemas envolvendo estudos de caso práticos.

7. Ementa

Sistemas inteligentes. Visão dos paradigmas de IA. Programação em lógica. A linguagem Prolog. Representação de conhecimento e Raciocínio. Métodos de busca para solução de problemas. Sistemas especialistas. Planejamento. Mineração de Dados. Aprendizagem de máquina. Agentes e multi-agentes. Processamento de linguagem natural.


a) Sistemas inteligentes.

b) Visão dos paradigmas de IA.

c) Programação em lógica.

d) A linguagem Prolog.

e) Representação de conhecimento e Raciocínio.

f) Métodos de busca para solução de problemas.

g) Sistemas especialistas.

h) Planejamento.

i) Mineração de Dados.

j) Aprendizagem de máquina.

k) Agentes e multi-agentes.


l) Processamento de linguagem natural.

9. Metodologia

Aula expositiva e aula prática em laboratório; estudo de programação de técnicas de IA; estudos de caso em duplas de discentes; apresentação de seminários;

10. Recursos

Slides e Laboratório.

11. Avaliação

2 provas e 3 trabalhos;

12. Bibliografia

Artigos de revistas técnicas e Livros:

ARBIB, M. A. The handbook of brain theory and Neural Networks. Cambridge: MIT Press, 1995. 1136p.

BERRY, M. J. A., LINOFF, G. – Data mining techniques. USA: John Wiley, 1997 BIGUS, J. & BIGUS, J. Constructing Intelligent Agents with Java. USA, Jon Wiley & Sons.

1998. BITTENCOURT, G. Inteligência Artificial – Ferramentas e Teorias. Editora da UFSC. 2ª.

Edição. Florianópolis, 2001. 362pp. BRATKO, I. Prolog Programming for Artificial Intelligence. (2nd ed), Addison-Wesley.

1990. FAYYAD, U. M., Piatetsky Shapiro, G., Smyth, P. & Uthurusamy, R. – Advances in

Knowledge Discovery and Data Mining, AAAIPress, The Mit Press, 1996. HAN, J., KAMBER, M. – Data Mining: concepts and techniques. USA: Morgan

Kaufmann, 2001. HAYKIN, S. Neural Networks: A Comprehensive Foundation. Prentice-Hall. 2nd Ed,

1999. 842p. (Tradução: Neural Network: Princípios e Prática. Bookman, 2001). MITCHELL, T. M. Machine learning. New York: McGraw-Hill. Series in Computer

Science, 1997. 414p. RUSSEL, S.; NORVIG, P.: Inteligência Artificial. Campus, São Paulo, 2004. 1040 pp. RICH, E.; KNIGHT, K.: Inteligência Artificial. Makron Books. 2ª. Edição. São Paulo, 1994.

722 pp. REZENDE, S., Sistemas Inteligentes: Fundamentos e Aplicações. Manole Editora. 2003.

525p. WOOLDRIDGE, M.; JENNINGS, N. Intelligent Agents: Theory and Practice. 1997.



Introdução à Realidade Virtual


Bianchi Serique Meiguins

3. Carga Horária

60 hs

4. Créditos

4

5. Pré-Requisitos

Nenhum

6. Objetivos

O curso de Introdução à Realidade Virtual e Aumentada tem o objetivo

de expandir o entendimento dos participantes sobre a área. Para atingir esse

objetivo as etapas do curso estão baseadas nas etapas de teoria de concepção

e caracterização da área, estado atual de pesquisa da mesma, utilização de

ferramentas e desenvolvimento de projetos.

7. Ementa

Visão geral de realidade virtual. Computação gráfica 3D. Geração de

ambientes virtuais por computador. Dispositivos de E/S para realidade virtual.

Aplicações Sistemas distribuídos de realidade virtual. Plataformas para

desenvolvimento de realidade virtual. Realidade virtual na Internet. Avaliação

de sistemas de realidade virtual;


8.1 Fundamentos de Realidade Virtual e Aumentada


8.2 Técnicas de Interação para Ambientes de Realidade Virtual e Aumentada

8.3 Ambientes de Hardware e Software para Aplicações de Realidade Virtual e

Aumentada

8.4 Aspectos de Desenvolvimento de Ambientes Virtuais de Realidade Virtual e

Aumentada

8.5 Sistemas Distribuídos de Realidade Virtual e Aumentada

8.6 Aplicações de Realidade Virtual e Aumentada

8.7 Aspectos de Avaliação de Ambientes de Realidade Virtual e Aumenta

9. Metodologia

Aulas expositivas. Análise de Ferramentas de Realidade Virtual e

Aumentada. Seminários com artigos de IEEE e ACM. Escrita de artigos.

10. Recursos

Sala de Aula com computador e data show. Laboratório com

computadores com sistema operacional Windows.

11. Avaliação

Avaliação será composta das seguintes fases:

• Apresentação de Artigo

• Escrita de artigo

• Estudo de análise comparativa de ferramentas de realidade virtual

e aumentada

• Projeto de construção de aplicação de realidade virtual e

aumentada

12. Bibliografia

AMES, AL. et.; VRML 2.0 Sourcebook. John Wiley & Sons, 1996.

KIRNER, C., TORI, R. (editores); Realidade Virtual: Conceitos e

Tendências, 2004


KIRNER, C., SISCOUTO, R. (editores); Realidade Virtual: Conceitos e

Aplicações, 2007

KIRNER, C.; Realidade Virtual: Dispositivos e Aplicações. Disponível em

CARDOSO, A., KIRNER, C., LAMOUNIER JR., E., KELNER, J.;

Tecnologias para o Desenvolvimento de Sistemas de Realidade Virtual e

Aumentada, 2007

MACHADO, L. S. OLIVEIRA, M. C. F. VALERIO NETTO, A Realidade

virtual: fundamentos e aplicações. Visual books, 2002. 94p.

BURDEA, G. C.. & COIFFET, P. - Virtual Reality Technology. John Wiley

& Sons, 1994.

KIRNER, C.; Sistemas de Realidade Virtual. Disponível em

NETTO, A V. MACHADO, L. dos S. OLIVEIRA, M. C. F. Realidade

Virtual - Definições, Dispositivos e Aplicações. Revista Eletrônica de Iniciação

Científica - REI C. Ano 11. VoI. 11. Número I. Mar 2002. Disponível em .

Acesso em: 12 nov. 2002

VINCE J. - Virtual Reality Systems. Adison-Wesley, 1995



Processamento Digital de Sinais


Aldebaro Klautau

3. Carga Horária

60

4. Créditos

4

5. Pré-Requisitos

Cursos ao nível de graduação em: a) Probabilidade & Estatística (por exemplo, TE05191- Probabilidade e Processos Estocásticos na graduação da Engenharia Elétrica) e b) Cálculo (uso de integral e derivada, equivalente ao Cálculo I na UFPA). Capacidade de ler textos técnicos em inglês, visto que o livro-texto e grande parte do material didático estão em língua inglesa. Noções de programação. Disposição para usar matemática e aprender de maneira básica o Octave (Linux) ou Matlab para simulações. Ressalta-se que a matéria tem forte relação com disciplinas normalmente vistas em cursos de graduação em engenharia, tais como (tomando a UFPA por base): “TE05178 - Análise de Sistemas Lineares” (Eng. Elétrica) e “Processamento Digital de Sinais” (Eng. da Computação). Assim, por mais que os instrutores tentem fazer a disciplina auto-contida, alunos com formação em outras áreas (Ciência da Computação, Sistemas de Informação, Engenharia Civil, Engenharia Mecânica, etc.), podem eventualmente se sentir em “desvantagem”, apesar disso não ser a regra. Um curso básico sobre Sinais e Sistemas, útil (apesar de não ser pré-requisito) para o curso de PDS em questão, é ofertado pelo MIT na Internet: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/index.htm Mais especificamente, o curso: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-003Fall-2003/CourseHome/index.htm

6. Objetivos

Apresentar uma introdução “hands on” (prática) ao processamento digital de sinais, de forma que o aluno possa atuar em áreas como telecomunicações, mineração de dados de séries temporais, análise de vibração, análise de sinais provenientes de sistemas de potência, etc. Como a multimídia permeia a computação atualmente, essa disciplina permite ao aluno obter familiaridade com processamento digital de sinais, e com conceitos que são úteis ao se lidar com vídeo, áudio e séries temporais em geral.

7. Ementa

Sistemas e sinais discretos no tempo. Amostragem. Transformada Discreta de Fourier. Transformada Z. Resposta em freqüência. Função de transferência. Filtros digitais.


Conversores A/D e D/A. Filtros anti-aliasing e de reconstrução. Filtros FIR e IIR. Filtragem adaptativa usando LMS. Aplicações práticas.


Dividido em cinco unidades: 1) Analog and digital signals (review: probability and stochastic processes, decibel

& impulse function, manipulating signals stored in files) 2) Transforms and Signal Representation 3) Analog and Digital Systems

4) Time-Frequency Analysis and Spectral Estimation 5) Adaptive Signal Processing

9. Metodologia

A proposta é fazer o curso o mais prático possível (apesar de não se ter acesso a um laboratório) permeando as aulas teóricas com aplicações práticas.

10. Recursos

Datashow e site Moodle.

11. Avaliação

Três ou mais provas. A matéria de cada prova é toda a estudada até o momento da mesma.

12. Bibliografia

12.1. O livro-texto (leitura obrigatória) será “Digital Signal Processing and Communications in Practice”, o qual está sendo escrito pelo ministrante e será disponibilizado em PDF. Mas outros livros de PDS podem ser utilizados, tais como os listados abaixo, além dos da coleção Schaum, que são repletos de problemas resolvidos.

12.2. Bibliografia Complementar

Digital Signal Processing: A Computer-Based Approach. Sanjit Mitra. McGraw-Hill. 2nd edition. ISBN: 0-07-252261-5. 2001. (notem que já foi publicada a 3a edição). DINIZ, P. S. R.; SILVA, E. A B.; NETTO. S. L. Processamento Digital de Sinais - Projeto e análise de sistemas, Bookman Company, 2004.

Oppenheim, A. V.; Schafer, R. W. , Discrete time signal processing, Prentice-Hall, 1989. Oppenheim, A., A. S. Willsky, Signal and systems, Prentice-Hall, 1975. Proakis, J. G., Monolakis, D. G. Digital signal processing: principles, algorithms, and applications, Prentice-Hall, 3. ed., 1998.



PROGRAMAÇÃO


Benedito Ferreira

3. Carga Horária

60h.

4. Créditos

04

5. Pré-Requisitos

Conhecimentos básicos de programação

6. Objetivos

A disciplina pretende ampliar e retomar, com aprofundamento, conceitos relacionados

a programação, independentemente de paradigma. Propor problemas que levem o aluno a

realizar prática de programação, envolvendo técnicas avançadas específicas.

7. Ementa

Valores e tipos; Variáveis e armazenamento; Amarração e escopo; Abstração de Procedimentos; Abstração de dados; Abstração Genérica; Sistemas de tipos; Fluxo de controle; Resolução de problemas em programação (recursividade e backtraking)


Parte I: Conceitos de Projeto de Linguagens de programação

1 - Introdução: linguagens de programação; conceitos e paradigmas; sintaxe, semântica, e pragmática; processadores de linguagens; desenvolvimento histórico

2 Valores e tipos: tipos primitivos; tipos compostos; tipos recursivos; sistemas de tipos; expressões; aspectos de implementação.

3 Variáveis e armazenamento: variáveis simples; variáveis compostas; semântica de cópia vs semântica de referência; Tempo de vida; Ponteiros; Comandos; Expressões com efeitos colaterais;

4 Amarração e escopo: amarração e ambientes; Escopo; Declarações; Blocos;

5 Abstração de Procedimentos: Funções e procedimentos; parâmetros e argumentos; aspectos de implementação.

6 Abstração de dados: Unidades de programa, pacotes e encapsulamento; tipos abstratos; objetos e classes; aspectos de implementação.


7 Abstração Genérica: unidades genéricas e instanciação; parâmetros de tipo e parâmetro de classes; aspectos de implementação.

8 Sistemas de tipos: polimorfismo de inclusão; polimorfismo paramétrico; sobrecarga; conversão de tipos; aspectos de implementação.

9 Fluxo de controle: sequenciadores; saltos (jumps), escapes; tratamento de exceções; aspectos de implementação.

PARTE II – Resolução de problemas em Programação

Nesta parte, serão discutidas técnicas e propostos problemas a serem resolvidos em diferentes linguagens (Java, C ou C++)0

1 – Recursividade: definição; as quatro regras da recursividade; programação dinâmica.

2 – Backtraking: construção de todos os conjuntos; construção de todas as permutações.

Parte I – Instrumentos de Trabalho

9. Metodologia

Aulas expositivas e realização de seminários; trabalhos práticos de síntese e documentação dos diversos materiais trabalhados.

10. Recursos

Projetor multimídia, quadro branco.

11. Avaliação

Frequência, entrega/qualidade dos trabalhos propostos (seminários): 50% . Prova: 50%

12. Bibliografia

WATT, David. Programming Languages Design Concepts. John Wiley and Sons, 2004, 492 p.

SKIENA, Steven & Revilla, Miguel. Programming Challenges. Springer; 1 edition. 2003. 368 p.



Redes de Computadores


Antônio Jorge Gomes Abelém

3. Carga Horária

60hs

4. Créditos

04 créditos

5. Pré-Requisitos

Não tem.

6. Objetivos

Apresenta os conceitos essenciais sobre redes de computadores através do estudo em camadas do tema, com ênfase na arquitetura da Internet.

7. Ementa

Introdução e conceitos básicos. Camada de aplicação: serviços, funcionalidades da camada e os principais protocolos de aplicação da Internet (http, ftp, smtp, dns, entre outros). Camada de Transporte: Serviços funcionalidades da camada e os protocolos de transporte da Internet (UDP e TCP). Camada de Rede: Serviços funcionalidades da camada e o protocolo IP. Camada de enlace e as principais tecnologias de redes locais e metropolitanas. Conceitos básicos sobre mobilidade e o IP móvel. Comunicação Multicast e o IP Multicast. Conceitos básicos sobre Qualidade de Serviço e de Experiência (QoS e QoE).


Capítulo 1 – Introdução 1. Introdução às Redes de Computadores;

a. O que é a Internet? b. Definições de Protocolo c. Estrutura de Redes.

i. Núcleo e Terminais d. Redes de acesso e meios físicos.

i. Topologias 2. Tecnologia de Comutação

a. Comutação por Circuito e Comutação por Pacotes i. Redes Orientadas a Conexão – X.25, Frame Relay, ATM

ii. Redes sem Conexão b. Atrasos e perda em redes de pacote.

i. Tipos de Atrasos e perdas 3. Os Modelos de Referência OSI e TCP/IP;

a. Conceitos e Arquitetura Capítulo 2 – Camada de Aplicação


1. Arquiteturas de Aplicações 2. Funções e Serviços da camada de aplicação 3. Protocolos da camada de aplicação

a. HTTP i. Conexões persistentes e não persistentes

ii. Formatos de mensagem iii. Caches

b. FTP – Comandos e respostas; c. Correio Eletrônico – SMTP, IMAP, POP d. DNS

i. Modo de funcionamento ii. Serviços oferecidos

iii. Registros e mensagens 4. Programação com sockets (laboratório)

a. TCP e UDP

Capítulo 3 – Camada de Transporte 1. Serviços da camada de transporte 2. Multiplexação e Demultiplexação 3. Transporte não orientado a conexão

a. Segmento UDP b. Verificação de erros

4. Transferência confiável de dados a. Protocolos b. Maquina de estados finitos - FSM c. Controle de erros (ARQ) - Go-Back-N, Repetição seletiva, ...

5. Transporte orientado a conexão a. Controle de Fluxo b. Controle de Congestionamento

i. Controle de congestionamento TCP- Justiça Capítulo 4 – Camada de Rede

1. Modelos de Serviços de Redes; 2. Redes de Circuitos Virtuais e Datagrama; 3. Rotadores

a. Elementos de Comutação b. Comutação store-and-forward

4. O Protocolo da Internet – IP a. Formato do Datagrama b. Endereçamento IPv4 c. Protocolo ICMP d. Endereçamento IPv6

5. Algoritmos de Roteamento a. Algoritmo de Roteamento Link State b. Algoritmo de Roteamento Distance Vector c. Roteamento Hierárquico d. Roteamento Intra-AS (RIP, OSPF) e. Roteamento externo (BGP)

Capítulo 5 – Camada de Enlace

1. Serviços fornecidos pela camada de enlace 2. Detecção e correção de erros

a. Verificação de paridade b. Soma de Verificação c. Redundância Cíclica – CRC

3. Protocolos de Acesso Múltiplos a. Divisão do Canal


i. TDM e FDM

ii. CDMA b. Protocolos de acesso aleatório

i. ALOHA, CSMA, CSMA/CD, CSMA/CA, Control Token,... c. Redes locais (LANs)

i. Ethernet ii. Token Ring

iii. Interface de Dados Distribuída por Fibra FDDI d. Endereçamento

i. Endereço MAC ii. Protocolo DHCP

iii. Protocolo ARP e. Topologia Ethernet

i. Comutadores ii. HUB X Comutadores

iii. Roteadores f. Protocolo PPP

i. Endereçamento ii. Byte Stuffing

g. Virtualização da Camada de Enlace i. Redes ATM

ii. Comutação por Rótulos – MPLS e GMPLS Capítulo 6 – Mobilidade, Multicast e Multimídia

1. Mobilidade e o IP Móvel 2. Comunicação multiponto e o IP Multicast 3. Qualidade de Serviço e de Experiência

a. Conceitos básicos b. RSVP c. Serviços Diferenciados

9. Metodologia

As aulas serão expositivas e/ou práticas, utilizando recursos de projeção multimídia disponibilizados nas salas de aula e laboratórios. A Internet será usada como recurso complementar para pesquisa e consolidação de conceitos. Haverá uma lista de e-mail da turma para discussões.

10. Recursos

Datashow, lista eletrônica de discussão e site para disciplina.

11. Avaliação

Provas e Trabalhos práticos e teóricos.

12. Bibliografia

KUROSE & ROSSI. Computer Networking: A Top-Down Approach

Featuring the Internet. 5ª edição. 2009.

o Título da tradução: Redes de Computadores e a Internet. Ed.

Pearson Brasil. 3ª edição. 2005.

TANENBAUM, A. Computer Network. 5ª edição. Prentice Hall, 2010.


o Título da tradução: Redes de Computadores. 4ª edição. PHB, 2003.

COMER, D. Internetworking with TCP/IP. 5ª edição. Prentice Hall, 2005.

o Título da tradução: Interligação em Rede com TCP/IP. Vol.1. Ed.

Campus. 2001.

DAY, J. Patterns in Network Architecture : a return to fundamentals.

Pearson Education, Inc, 2009.

RFCs e artigos diversos.



Tópicos Especiais em Sistemas de Informação – Sistemas Colaborativos


Cleidson R. B. de Souza

3. Carga Horária

60h

4. Créditos

4

5. Pré-Requisitos

CSCW é uma área bastante extensa e que utiliza abordagens de diversas outras ciências, desta forma, torna-se difícil especificar os pré-requisitos necessários a um bom desempenho na disciplina. Os alunos serão “convidados” a participar das discussões em sala de aula e pesquisar material adicional ao apresentado em sala de aula. Um bom domínio da língua inglesa será necessário para o acompanhamento das leituras da disciplina.

6. Objetivos

Devido a diversidade de tópicos que podem ser abordados na área de CSCW / groupware, o objetivo do curso é fornecer apenas uma visão geral da área apresentando os conceitos básicos da área fornecendo aos alunos o conhecimento mínimo para que as idéias vistas no curso possam ser posteriormente detalhadas. Espera-se que as idéias , conceitos, e técnicas apresentadas no curso possam ser utilizadas pelos alunos no decorrer de sua vida profissional e que, ao final da disciplina, alguns alunos definam o tema de TCC nesta área.

7. Ementa

Groupware é a tecnologia empregada para auxiliar grupos de trabalho envolvidos em uma determinada atividade, como por exemplo desenvolver um software ou escrever um texto. CSCW(do inglês, Computer-Supported Cooperative Work) é o nome da área de pesquisa que estuda o uso de tecnologias de computação e comunicações para apoiar atividades realizadas por grupos. No Brasil, estas duas áreas têm sido referenciadas como “Sistemas Colaborativos”. Esta área adota métodos, técnicas e abordagens de diversas disciplinas, incluindo sociologia, antropologia, psicologia, ciência organizacional, ciência da computação, etc. De maneira similar, diversos aspectos da ciência da computação podem ser aplicados em CSCW / groupware, como por exemplo, sistemas distribuídos, redes de computadores, engenharia de software, interação homem-computador, computação gráfica, inteligência artificial, etc.


1. Definição de Sistemas Colaborativos (CSCW/Groupware)


2. Classificações de Sistemas Colaborativos 3. Métodos de Pesquisa Quantitativos e Qualitativos 4. Conceitos Básicos

a. Percepção b. Protocolos e Artefatos de Coordenação c. Aspectos Organizacionais

5. Aplicações a. Escrita Colaborativa e Wikis b. Sistemas de Comunicação: Media Spaces c. Workflow e Processo de Software d. Mídias Sociais

6. Domínios a. Desenvolvimento Distribuído de Software b. Hospitais; c. Educação

7. Considerações Finais

9. Metodologia

Ao longo do curso, os conteúdos serão abordados por meio de: 1. Aulas introdutórias com o professor; 2. Leituras e resumos a serem solicitados com antecedência pelo professor; 3. Seminários a serem apresentados pelos alunos, cujo tema será negociado

entre os grupos e o professor.

10. Recursos

Quadro magnético, acesso a bases de referências bibliográficas da ACM e IEEE.

11. Avaliação

A avaliação dos alunos será feita através de: 2 (duas) provas escritas e 1 (uma) apresentação e relatório. A nota final será obtida a partir da media aritmética das três avaliações.

A frequência será feita em sala de aula após 15 (quinze) minutos do início da aula. Alunos que não obtiverem frequência mínima serão reprovados por frequência (SF).

12. Bibliografia

1. Livro-texto: PIMENTEL, M.; FUKS, H. (Org.) . Sitemas Colaborativos. Elsevier (Serie CAMPUS/SBC), 2011. v. 1. 416 p.

2. Este livro será complementado por artigos de conferências e revistas a serem fornecidos pelo professor, em sua maioria em inglês.



Tópicos Especiais em Tecnologias, Plataformas e Serviços para Cidades Inteligentes


Eduardo Coelho Cerqueira

3. Carga Horária

60h

4. Créditos

4

5. Pré-Requisitos

Nenhum

6. Objetivos

A disciplina tem o objetivo de apresentar os conceitos fundamentais a serem aplicados para o desenvolvimento de Tecnologias, Plataformas e Serviços para Cidades Inteligentes, através de abordagem teórica e prática, incluindo temas como automação, computação verde e eficiência energética.

7. Ementa

Redes de Computadores, Sistemas Multimídias, Redes de Sensores, Redes baseadas em Software, Tecnologias, Plataformas e Serviços para Cidades Inteligentes, Simulação e Experimentação.


Introdução a Redes de Computadores: Aplicações, Serviços e Protocolos Sistemas Multimídia: Distribuição de vídeos em cidades inteligentes Redes de Sensores: Aplicações, serviços, protocolos e eficiência energética para cidades inteligentes Redes baseadas em Software: Openflow, modelo baseado em componentes Tecnologias, Plataformas e Serviços para Cidades Inteligentes Avaliação de Desempenho: Simulação e Experimentação

9. Metodologia

O conteúdo é apresentado através de exposições orais, guiadas pelo uso de data show, bem como do quadro-branco. A aplicação dos conceitos vistos em sala de aula será reforçada através de projetos focados no desenvolvimento de Tecnologias, Plataformas e Serviços para Cidades Inteligentes

10. Recursos

Data show e quadro-branco


11. Avaliação

Projeto e artigo

12. Bibliografia

Artigos científicos especializados.



Tópicos Especiais em Computação: Tecnologias de Redes sem Fio


Raimundo Viégas Jr.

3. Carga Horária

60 horas/aula

4. Créditos

04 Créditos

5. Pré-Requisitos

Redes de Computadores (Graduação)

6. Objetivos

Fornecer ao aluno uma visão abrangente do estado da arte na área de redes locais sem

fio, apresentando as tecnologias, arquiteturas e protocolos utilizados. Um enfoque

especial é dado nos tópicos de suporte à Qualidade de Serviço (QoS) .

7. Ementa

1. Fundamentos de Redes de Computadores

2. Introdução a redes sem fio

3. Tecnologias de redes sem fio (Padrões IEEE WPAN e WLAN)

4. Rede Ad-hoc e Infraestruturada (IEEE 802.11)

5. Camadas: Física, Enlace e Redes (IEEE 802.11)

6. Qualidade de Serviço (IEEE 802.11e)


1. Introdução a redes de computadores sem fio (IEEE WPAN e WLAN)

• Componentes

• Fundamentos

• Topologias

2. Padrões para redes locais IEEE 802.11

3. Tecnologias IEEE 802.11a/b/g/n

4. Redes Ad-Hoc e Infraestruturada

5. Camadas: Física, Enlace e Redes (IEEE 802.11)

6. Qualidade de Serviço (IEEE 802.11e)

7. Estudo de Caso utilizando simuladores de rede sem fio.


9. Metodologia

Aulas expositivas com transparências apresentadas em data show. Exemplos e

exercícios que estimulem o aluno a desenvolver uma análise crítica das diversas

técnicas estudadas. Estudo de casos que destaque a importância da disciplina e sua

aplicação em problemas reais. Trabalhos desenvolvidos e apresentados em seminários

para a consolidação dos conceitos desenvolvidos em sala de aula.

10. Recursos

Data Show, quadro branco, Marcador de quadro magnético e Laboratório de

Informática.

11. Avaliação

1. Prova escrita

2. Trabalhos em grupo (listas de exercícios e simulações de redes sem fio)

3. Escrita de Artigos e Seminários

12. Bibliografia Básica

GAST, Matthew, "802.11 Wireless Networks: The Definitive Guide", Second Edition

(Definitive Guide), April 25, 2005.

KUROSE, James F.; ROSS, Keith W. Redes de Computadores e a Internet: Uma

Abordagem Top-Down. 3ª Ed. São Paulo: Pearson, 2006.

TANENBAUM, Andrew S. Redes de Computadores. 4º Ed. Rio de Janeiro: Campus,

2003.

COMER, Douglas E. Redes de Computadores e Internet. 4º Ed. Porto Alegre: Bookm,

2007.

IEEE, 802.11 (2005), IEEE 802.11e Standard for Information Technology - Wireless

LAN- Medium Access Control (MAC) and Physical Layer (PHY) Specifications

Amendment 8: Medium Access Control (MAC) Quality of Service Enhancements.

IEEE, 802.11 (2007), IEEE 802.11 Standard - Part 11: Wireless LAN Medium Access

Control (MAC) and Physical Layer (PHY) Specifications.

IEEE, 802.1D (2004), IEEE 802.1D Standard for Local and Metropolitan Area Net-

works Media Access Control (MAC) Bridges.



<Introdução a Teoria de Filas com Aplicações em Sistemas de Comunicação e Computação >


<Glaucio H.S. Carvalho>

3. Carga Horária

<68>

4. Créditos

<4>

5. Pré-Requisitos

<O curso será ministrado de forma autocontida>

6. Objetivos

<Capacitar os estudantes em modelagem com cunho em avaliação de desempenho de sistemas de TIC via soluções analíticas por meio de modelos de filas.>

7. Ementa

<Probabilidade, Sistemas de Filas Markovianos e Semi-Markovianos e Redes de Filas>


<Revisão de Probabilidade, Introdução aos sistemas de filas, Cadeia de Markov a tempo discreto e contínuo, Sistemas de Filas Markovianos, Sistemas de Fila Semi-Markovianos, Redes de Filas >

9. Metodologia

<Aulas expositivas e palestras>

10. Recursos

<Datashow, quadro magnético>

11. Avaliação

<Duas avaliações tradicionais (cada uma com três capítulos), e um trabalho prático final de modelagem a respeito da aplicação em sistemas de TIC de um dos temas ministrados na disciplina.>

12. Bibliografia

<Livro texto: Chee-Hock Ng, Soong Boon-Hee, Queueing Modelling Fundamentals: With Applications in Communication Networks, Wiley, 2 edition, 2008; Livro de apoio:


John N. Daigle, Queueing Theory with Applications to Packet Telecommunication, Springer; 2005. Henry H. Liu, Software Performance and Scalability: A Quantitative Approach, Wiley, 2009. Diversos artigos: IEEE, ACM, Elsevier, Springer, etc.>

Documents

UNIVERSIDADE FEDERAL DO PARÁ INSTITUTO DE CIÊNCIAS EXATAS ... · - Conhecer os grafos dirigidos e não dirigidos e seus ... Isomorfismo de grafos f. Grafos regulares, completos