Curso de tecnologia em sistemas de computação disciplinar

Curso de Tecnologia em Sistemas de Computaç ̃ao Disciplina: Fundamentos de Algoritmos para Computaç ̃ao Professoras: Susana Makler e Sulamita Klein AD2 - Segundo Semestre de 2017

Nome - Assinatura -

Quest ̃oes:

1. (1.0) Usando o Teorema das Linhas, calcule a seguinte soma:

S = 4C4

15

+ 5C5

15

+ 6C6

15

··· + 15C15 15

Justifique.

2. (1.5) Calcule o coeficiente de x10 no desenvolvimento do binômio de

Newton:

(√

)

100

Justifique.

3. (1.5) Um banco está cobrando 8% de juros ao mês. Jo ̃ao tomou em- prestado R$5.000,00 e deve pagar prestaç ̃oes mensais de R$500,00. A primeira prestaç ̃ao será paga ao final do primeiro mês do emprêstimo. (a) Encontre a relaç ̃ao de recorrência para a d ́ıvida do Jo ̃ao. Justifique. (b) Determine a fórmula fechada da relaç ̃ao de recorrência. Justifique. (b) Usando a fórmula fechada, encontre a d ́ıvida do Jo ̃ao ao final do oitavo mês. Justifique. Observe que a d ́ıvida inicial é a

0

= 5.000,00.

1

x

3

-

x2

5

---

4. (1.2) Mostre que em um grupo com 15 pessoas n ̃ao é poss ́ıvel que cada pessoa do grupo conheça exatamente outras cinco pessoas deste grupo. Modele o problema como um grafo e mostre o resultado usando pro- priedades de grafos.

5. (1.3) Seja F uma floresta com 35 vértices e 10 componentes conexos.

Calcule o número de arestas de F. Justifique.

6. (3.5) Responda as seguintes perguntas considerando o grafo G dado

por: V (G) = 1a, b, c, d, e, f, g, hl, E(G) = 1(a, b),(b, c),(c, d),(d, e),(e, f),(a, f),(g,h),(h, a),(h, e),(f,g)l. (Justifique suas respostas. Respostas sem justificativas n ̃ao ser ̃ao con- sideradas.)

(a) Desenhe G e desenhe também seu grafo complementar

G. (b) Gé bipartido? Caso seja, dê sua bipartiç ̃ao. E o grafo

Gé bipar- tido? (c) Gé um grafo euleriano? E

G? (d) Gé hamiltoniano? (e) Gé planar?

2