Universidade Federal de Minas Gerais
Departamento de Ciência da Computação

Métodos Quantitativos em
Ciência da Computação Experimental

2o Semestre de 2011

Professora: Jussara M. Almeida

Carga Horária: 60 cr

Horário: Sextas, 8:00 às 17:00 (Divinópolis - DINTER)

Motivação

Como computação é um ramo da ciência, torna-se cada vez mais importante para os pesquisadores da área desenvolverem habilidades e terem conhecimento do método científico. Muitas pesquisas em ciência da computação experimental não são devidamente consideradas porque seus resultados baseiam-se em técnicas experimentais incorretas ou deficientes. Outras pesquisas em computação falham na apresentação de evidências experimentais que suportam suas conclusões. Esta é a motivação para um curso que concentra-se em técnicas estatísticas para suportar o método científico em ciência da computação. Os exemplos ilustrativos dos métodos experimentais estará concentrados em Web, redes, recuperação de informação, engenharia de software, IHC, dentre outras áreas.

Ementa

Tratamento de dados experimentais: medição, sumarização estatística, apresentação e interpretação de dados experimentais.
Carga de trabalho (workloads): caracterização e análise.
Métricas apropriadas para as questões buscadas pela pesquisa em ciência da computação experimental.
Projeto experimental efetivo (Effective experimental design): como projetar testes de sistemas que são significativos.

Programa

• Visão geral do curso:
  • Motivação
  • Ciência da Computação Experimental e o Método Científico

• Monitoração e Sumarização de Dados Coletados:
  • Tipos de cargas, modelos de cargas,
• Revisão de probabilidade e sumarizacao de dados medidos:
  • Algebra de eventos, espacos amostrais;
  • Probabiliade, probabilidade condicional;
  • Independencia de eventos, regra de Bayes, teorema da probabilidade total
  • Variaveis aleatorias, funcoes de probabilidade;
  • Media, mediana, moda, variancia, desvio padrao, covariancia;
  • Distribuicoes comuns de variaveis aleatorias discretas e continuas;
  • Sumarizacao de dados: media aritmetica, geometrica, harmonica;
  • Intervalos de confianca
• Comparacao de Sistemas Usando Dados de Amostrangem e Intervalos de Confianca:
  • Intervalos de confianca para a meida da amostra;
  • As distribuicoes z e t ;
  • Testes para media zero ;
  • Testes para comparacao de duas alternativas e de proporcoes;
  • Testes de hipoteses;
  • Intervalos de Confianca de um lado e para proporcoes;
• Modelos de Regressao :
  • Estimativas de parametros de modelos;
  • Desvio padrao de erros;
  • Intervalos de confianca para regressoes e predicoes;
  • Testando independencia e linearidade;
  • Regressao linear multipla, analisa da variancia, F-Test;
  • Regressao curvilinear, transformacoes, outliers;
• Projeto de Experimentos:
  • Terminologia, fatores, erros comuns na experimentacao;
  • Tipos de projetos de experimentos: Projetos simples, com fatorial completo, com fatorial fracionado;
  • Projetos fatoriais 2k;
  • Computacao de efeitos;
  • Alocacao de variacao;
• Experimentos de Um-Fator:
  • Modelo, computacao de efeitos;
  • Estimativa de erros experimentais;
  • Alocacao de variancia, analise de variancia;
  • Testes visuais;
• Apresentacao Grafica de dados Experimentais:
  • Tipos de variaveis;
  • Regras praticas para apresentacao de graficos;
  • Erros comuns nos graficos;

Bibliografia

Básica:

[Jain] The Art of Computer System Performance Analysis: Techniques for Experimental Design, Measurement, Simulation and Modeling, Raj Jain, John Wiley & Sons, 1991, ISBN: 0-471-50336-3.

Outros Livros Recomendados:

[BoHH] Statistics for Experimenters: An Introduction to Design, Data Analysis, and Model Building , George E. P. Box, Wiliam G. Hunter, J. Stuart Hunter, John Wiley & Sons, Inc. 1978.

[MeAD] Performance by Design: Computer Capacity Planning by Example, Daniel A. Menasce, Virgilio A. F. Almeida, Larry W. Dowdy, Prentice Hall, 2004.

[MeAl] Capacity Planning for Web Services: metrics, models, and methods, Daniel Menasce, Virgilio Almeida, Prentice Hall, 2002.

[Tufte] The Visual Display of Quantitative Information, Edward R. Tufte, Graphics Press, Cheshire, Connecticut, 1983.

How to Give a Talk, Arnaud Legout .

Artigos:

1. Walter Tichy, "Should Computer Scientists Experiment More?", IEEE Computer, May 1998, pages 32-40

2. Peter Denning, "Is Computer Science a Science?" Communications of ACM, Maio 2005, pages 27-31.

3. Keith Devlin, "Why universities require computer science students to take math", Communications of ACM, Setembro 2003

4. Dror G. Feitelson, "Experimental Computer Science", Comm. of ACM, Nov. 2007, Pages: 24 - 26

5. Larry Peterson, Vivek S. Pai, "Experience-Driven Experimental Systems Research, Communications of ACM, November 2007.

6. Mary Shaw, "What Makes Good Research in Software Engineering?", International Journal of Software Tools for Technology Transfer, 2002, vol. 4, no. 1, pp. 1-7.

7. John Platt, "Strong Inference", Science, October 1964, Vol. 196, pages 347-353

8. Virgilio Almeida, Daniel Menasce, Rudolf Riedi, Flavia Peligrinelli, Rodrigo Fonseca, Wagner Meira Jr., "Analyzing Web Robots and Their Impact on Caching", Web Caching Workshop, 2001

9. Jussara M. Almeida, Derek L. Eager, Mary K. Vernon", "A Hybrid Caching Strategy for Streaming Media Files", MMCN 2001

Avaliação

• 2 provas em sala de aula: 25 pontos cada prova
• Projeto : 40 pontos
• Participação em sala de aula: 10 pontos

Projeto: O projeto pode ser realizado individualmente ou em grupo de até 2 alunos. O trabalho deverá desenvolver um projeto experimental, de maneira sistemática, de acordo com o método científico. O projeto poderá usar temas de outras disciplinas. Entretanto, tem de ser um projeto novo e não algo já apresentado em outra disciplina. Pode aproveitar trabalhos iniciados em outras disciplinas, mas tem necessariamente de incluir os conhecimentos deste curso. Em particular, o projeto experimental realizado deve incluir no mínimo três das classes de técnicas apresentadas no curso (caracterização de cargas, comparação de sistemas com Intervalos de Confiança e teste-t, modelos de regressão, projetos fatoriais, projetos de um fator, etc).

O projeto inclui:

• (10%) Proposta com 2-3 páginas descrevendo:
  • O problema que você planeja estudar: seja sucinto, específico, concreto e direto!
  • Porque você pensa que o problema é importante. Em outras palavras, porque você deseja desenvolver o tópico;
  • Trabalhos relacionados
  • Plano e metodologia de trabalho: pontos específicos que deseja alcançar. Você será avaliado por esta referência, logo, seja coerente e consistente.
• (15%) Relatório intermediário .
• (10%) Apresentação em classe
• (65%) Relatório final, contendo:
  • (10%) motivação e originalidade;
  • (10%) clareza do texto
  • (25%) completude (uso das ténicas disponíveis, exploração do escopo definido.)
  • (20%) análise quantitativa e crítica dos resultados

Participação: Os alunos deverão ler antes das aulas os artigos que serão discutidos. Além disso, deverão ler os capítulos utilizados do livro básico: Jain, The Art of Computer Systems Performance Analysis. Possivelmente, os alunos também deverão fazer apresentaçõs e seminários sobre outros artigos.

Listas de Exercícios

Planejamento das Aulas

'

Aula	Mês	Dia	Assunto
01	Agosto	08	Apresentacao
02	Agosto	10	Método Científico
02	Agosto	10	Caracterização de Cargas
02	Agosto	10	Caracterização de Cargas: Exemplos
02	Agosto	10	Revisão: Probabilidades
02	Agosto	10	Revisão: Estatística
02	Agosto	10	Revisão: Estatística
02	Agosto	10	Comparando Sistemas
02	Agosto	10	Projetos Experimentais
02	Agosto	10	Regressao Linear
02	Agosto	10	Simulacao
02	Agosto	10	Apresentacao de Resultados

About this document ...