aedsi-2-10

UFMG - ICEx - DCC

DCC003 --Algoritmos e Estruturas de Dados I -- AEDsI
2o. Semestre de 2010

Notas: Provas 1, 2 & 3: gabarito

Entrega Paradoxo do Aniversário & Farkle

Entrega Futebol & Cartas

Você deve apresentar no dia 21/out de 10:00 as 12:00 duas soluções:

Cartas & Futebol --à sala 2011

Provaveis TPs:

cofrinho

caixa – Livro-Caixa

contrato – ~~Revisão de Contrato<<<<< removido~~

formula – Fórmula 1

guerra – Guerra nas Estrelas

leitura – Leitura Ótica

plagio – Plágio Musical

robo – Robô Colecionador

velha – Jogo da Velha

Faça o cadastro e submeta os primeiros TPs -à SETP (Seu cadastro deve usar <sua conta> no DCC.UFMG.BR

Se você não tem conta no DCC (não é da Computação) mande mensagem para rodolfo [em] dcc.ufmg.br

com seu nome, numero de matricula e curso, a conta demora alguns dias até ficar disponível!!

Vá trabalhando nos TPs enquanto providencia a conta!

Prazo final

25/nov/2010 adiado

30/nov/2010 adiado

até as 17:00 02/dez/2010

Terças e quintas-feiras, sala 2013, 14:55 as 16:35;
Monitoria: todas segundas-feiras sala 2011 de 11:00 as 12:00 cascini [em] dcc

http://en.wikibooks.org/wiki/C_Programming/Standard_libraries

O objetivo desta disciplina é facilitar que o aluno domine os conceitos básicos de programação utilizando o paradigma imperativo, além disso, facilitar que o aluno aprenda uma linguagem de programação, neste caso a linguagem C e C++(*), e aprenda ainda alguns algoritmos e estruturas de dados simples. Exemplos de conceitos básicos de programação: fluxo de controle, variável, constante, operador, expressão, comando de atribuição, comando iterativo, apontador, referência, arranjo e indexação, cadeia de caracteres, funções, arquivo, entrada e saída, estrutura de dados linear. Exemplos de algoritmos simples: cálculo de digitos verificadores, seqüências, ordenação.

(*)Este é um segundo semestre de transição, ao longo do semestre haverá evolução do material de transição da linguagem JAVA para C/C++

Avaliação:
60 pontos: duas provas valendo 30 pontos cada
40 pontos: trabalhos práticos, listas de exercícios, testes etc.

Até x-feira x/x deverá ser demonstrado para a estagiaria docente um programa que simula os percentuais de pessoas com aniversário no mesmo dia (usando rand()) para P pessoas em T turmas. Alguns valores: 23 pessoas 50%; 30 pessoas 70.6%; 50 pessoas 97%;

/* primeiro deve ser lido o número de pessoas por turma

em segundo lugar leitura do numero de turmas:

com 23 (pessoas) 100 (turmas) deve imprimir: 50 50 (ou .5 .5)

ou algo próximo, pode acontecer 60 40! ou 30 70!

int numPessoas;

int numTurmas;

printf("Numero de pessoas por turma:");

scanf("%d", &numPessoas);

printf("Numero de turmas:");

scanf("%d", &numTurmas);

para cada uma das numTurmas faca

AnivMesmoDia=aniversario pessoa i == aniversario pessoa j (i<>j)

se (anivMesmoDia) ContaAnivIgual++;

fim para

printf("%d %d\n", contaAnivIgual, (numTurmas-contaAnivIgual));

printf("%.1f %.1f\n", contaAnivIgual/(double)numTurmas

(numTurmas-contaAnivIgual)/(double)numTurmas);

}

isto pode ser útil:

time_t timer;

timer=time(NULL);

srand(timer);

...

for(contaPessoa=0; contaPessoa<numPessoas; contaPessoa++)

aniv[contaPessoa]=rand()%365+1;

Também devem ser demonstradados um ou mais programas que <<comprovam>> as seguintes probabilidades para o jogo de FARKLE
(quando jogamos 6 dados):
trinca 1 / 3.1

quadrupla 1 /21

quintupla 1 / 259

sextupla 1 / 7776

três pares 1 / 26

seqüência 1 / 65

duas trincas 1 / 155

Meus resultados (farkle, farkel, 10000, 10.000, 6 dice)

tipo/type	ocorrências
dupla/duple par/pair 112345	10800
tripla/triple trinca/triplet 111234	7200
quadrupla/quadruple 111123	1800
quintupla/quintuple 111112	180
sextuplas/sextuple 111111	6
2 pares/pairs 112234	16200
2 triplas/triples 111222	300
3 pares/pairs 112233	1800
1 par/pair 1 tripla/triple 112223	7200
1 par/pair 1 quadrupla/quadruple 112222	450
seqüência/sequence straight 123456	720
total	46656

sug

A disciplina é baseada nas notas de aula. Quando o aluno não comparecer à aula, deve arranjar um colega que forneça as anotações de aula. Parte do material será disponibilizado neste sítio Web.

Material suplementar
Consulte estes livros na biblioteca do ICEx:

GUIMARÃES, Angelo de Moura, LAGES, Newton Alberto.
Algoritmos e Estruturas de Dados,
Ed. LTC, 1994.

FARRER, Harry, et. al.
Algoritmos estruturados. 3. ed.
Ed. LTC, 1999.

Existem vários cursos de C/C++ disponíveis na Internet. O problema destes cursos é que a ênfase é a linguagem. Procure cursos onde a ênfase são os conceitos de programação.

Provas:
As provas são sem consulta, mas você pode trazer uma folha tamanho A4 contendo quaisquer anotações de próprio punho; não é para imprimir, não é para copiar (não faça colagens). A folha de consulta deverá ser entregue junto com a prova. O objetivo da folha de consulta é evitar que o aluno escreva na carteira, na régua ou na borracha. O objetivo da folha de consulta não é testar se o aluno sabe condensar centenas de folhas em uma só folha.

São escolhidas as duas melhores notas caso o aluno faça as três provas. O objetivo de existirem três provas e serem escolhidas duas notas é evitar que o professor tenha que fazer julgamento de mérito no caso de alunos que não podem comparecer em algum dia de prova. A possível melhoria de nota é um efeito colateral.

1a. Prova: /2010
2a. Prova: /2010
3a. Prova: /2010

Trabalhos Práticos:

Listas de Exercícios:

Testes Surpresa:

Material Extra:

Dicas sobre o uso polido e educado de correio eletrônico

Calendário

Data	Aula	Evento	Assunto
Agosto
03		Recepção
05	01&02		Apresentação
10	03&04		Computador Simplificado
12	05&06		Computador Simplificado - Variáveis
17	07&08		Variáveis; fluxo de controle
19	09&10		Variáveis; fluxo de controle
24	11&12		Fluxo de controle; expressões
26	13&14		arranjos, ponteiros e estruturas;
31	15&16		Strings e arranjos
Setembro
02	17&18		função
07		Independência
09	19&20		função
14	21&22		função
16	23&24		ordenação; extern static
21	25&26		recursividade
23	27&28		revisão
28	29&30		1ª. Prova
30	31&32		Entrada e saída; Arquivos
Outubro
05	33&34		classes & instâncias
07	35&36		classes herdam de classes
12		Nossa Sra. Apar.
14	37&38		construção, destruição & Cia
19	39&40		factoides
21	41&42		referências
26	43&44		factoides
28	45&46		listas encadeadas
Novembro
02		Finados
04	47&48		2ª. Prova
09	49&50		programação genérica- templates
11	51&52		programação genérica-templates
16	53&54		coleções-iteradores
18	55&56		coelações-iteradores
23	57&58		3ª. Prova
25	59&60		espaço p/ elaboração de TPs
30	61&62		Revisão final- entrega de provas
Dezembro
02	63&64		-----
07	65&66	encerramento