AD1-2014-1 Fundamento de Algorítmos para Computação

Prévia do material em texto

Curso de Tecnologia em Sistemas de Computac¸a˜o
Disciplina: Fundamentos de Algoritmos para Computac¸a˜o
Professoras: Susana Makler e Sulamita Klein
AD1 - Primeiro Semestre de 2014
Nome -
Assinatura -
Atenc¸a˜o! Embora o to´pico Combinac¸a˜o com Repetic¸a˜o na˜o seja abor-
dado na AD1, ele faz parte do conteu´do da AP1.
Questo˜es:
1. (1.5) Verifique se cada uma das afirmac¸o˜es abaixo e´ falsa ou verdadeira.
Se for verdadeira, prove, se for falsa justifique.
(i) A − (B − C) = (A − B) ∪ (B ∩ C), sendo A,B e C conjuntos
arbitra´rios.
(ii) Seja A = {∅, 1} e P (A) o conjunto das partes de A. Enta˜o {∅} ∈
P (A).
(iii) {√2, 3} ⊆ {x ∈ Z : |3x− 7| ≤ 15}.
2. (1.0) Todos os convidados em um jantar bebem cafe´ ou cha´; 13 con-
vidados bebem cafe´, 10 bebem cha´ e 4 bebem tanto cafe´ quanto cha´.
Quantas pessoas ha´ nesse grupo?
3. (2.5)
(a) Mostre pelo Princ´ıpio da Induc¸a˜o Matema´tica que:
3n − 2 e´ ı´mpar para todo inteiro n ≥ 1.
1
(b) Considere a sequeˆncia an tal que:
ao = 12, a1 = 29 e ak = 5ak−1 − 6ak−2 para todo inteiro k ≥ 2.
Mostre por Induc¸a˜o Forte que:
an = 5.3
n + 7.2n para todos inteiros n ≥ 0.
4. (1.2) Em quantos dos nu´meros menores do que 10.000 na˜o ocorrem
nu´meros ideˆnticos pareados (isto e´, na˜o aparecem os bocos 11, 22, etc)?
5. (1,2) Ha´ 12 cadeiras em fila. De quantos modos 6 casais podem se
sentar nas cadeiras, se nenhum marido senta separado de sua esposa?
6. (1,3) De quantas maneiras 10 livros distintos podem ser colocados em
5 caixas ideˆnticas, contendo 2 livros cada uma?
7. (1,3) Uma palavra tem 7 letras, sendo que uma delas aparece k vezes,
e as outras letras restantes aparecem sem repetic¸a˜o. Sabendo que o
nu´mero de anagramas que se obte´m permutando as letras desta palavra
e´ 210, calcule k.
2