Prévia do material em texto
Universidade Eduardo Mondlane
Faculdade de Ciências
Departamento de Matemática e Informática
Exame de Normal de Matemática Discreta II
Duração: 100 minutos Curso: Informática e CIG 28.11.2023
Apelido Nomes
1. Considere a expressão F = ú2 + /8 ≠ 75 ú 46
(a) (2.0 valores) Calcule o valor desta fórmula e escrava-a nas formas infixa e posfixa.
(b) (1.0 valores) Esboce a árvore binária correspondente a esta fórmula.
(c) (1.0 valor) Usando a operação ligação, escreva a expressão correspondente para a
sua árvore acima.
Corrector
a F 2 18 1,5
46 4 7 5 2
I 2 1
1 46
V2 8 V 812 4
F 2
tray V3 4 6 24
F 2
thy Vy Etr 4 24 28
F 42 Vy VE 2 4 2 28 56
F 2875 146 4
2 Forma Infixa
7 2 48117 5 4 61
8
6
c F light 02 light lig 1 08 list 1070s 4
0406
2. Seja f : N ◊ N æ N uma função definida recursivamente por:
(b) f(0) = 1, f(1) = 2;
(r) f(3n) = 3f(n) (r1), f(3n + 1) = f(3n) + 1 (r2).
(a) (2.0 valores) Determine o domínio S da função f e dê a sua forma inversa corres-
pondente.
(b) (1.0 valores) Determine uma forma inversa da função dada.
(c) (1.5 valores) Calcule os valores de f(9), f(10), f(11).
9 B ones
R se ne S Snes
Se 3h ES 33Mt IES
112 se ne s
e ne dinant por
3
R
en te f es
Into n
Éginanlims
h b f 101 1 fer 2
H fin 3714
2 fin fin 1 H S U E 1 mods
C 719 3 f 3 3 3711 3 3 2 18
7110 719 1 18 1 19
flu nai existe poos
n s
3. Considere o fluxo inicial na rede dada abaixo.
(a) (1.0 valores) Determine a fonte e o destino, e verifique a condição de conservação do
fluxo para os vértices A e D
(b) (2.0 valores) Calcule o fluxo máximo nesta rede aplicando o Algoritmo de Ford-
Fulkerson
(c) (1.0 valores) Encontre um a-z corte mínimo da rede.
33
I 4816
9
313
Is
a foute A Destino E
Vertu D 3 2 4 1
b Caminho A E anmenta 3
11 A F E anmenta 2
11 A B E aumenta 2
11 A D C B E aumente 2
in A D B E
BIH
Ema 3 3 7 5
i 18
tix
4 Corte minimo
V 4A D
V h E B C F
4. Considere uma mensagem escrita com as letras (a, b, c, d, e, f) cujas ocorrências são, res-
pectivamente, os números da lista L = {9, 8, 3, 7, 5, 4}.
(a) (1.5 valores) Aplicando o algorítimo de Hu�man, construa uma árvore binária mí-
nima, sendo L a lista dos pesos.
(b) (0.5 valores) Calcule o peso da árvore obtida de (a).
(c) (1.0 valores) Escreva os códigos da mensagem mínima de comprimento usando o
resultado da alínea (a).
a 1 4314,5 7 8,94
r 3 4 7
45 7,7 8 94 2 5 7 12
L 47 8,9 124 23 7 8 15
L 49 12 154 4 9 12 21
L 415214
8 15 27 36
AN ou off onA
7 8 9 off oh 8 9 off
5 0 4 3 4
5 7
3 4P 7.2 8.2 9.2 5.3 3 474 4
91
3 000
c 7 00
4 001
8 01 OU 8 01
9 10 9 10
5 110
3 1110 EIJI4 1111
(a) (1.0 valores) Dado o diagrama de autômato abaixo, determine todas as componentes
deste AF.
(b) (1.5 valores) Determine se as linhas de entrada – = bbaababb, — = ababaaab são
aceitáveis pelo autômato. Indique os caminhos de estados correspondentes.
(c) (2.0 valores) Escreva uma gramática correspondente ao diagrama acima e caracterize
a linguagem L(G) dessa gramática.
Bom trabalho!
Calisto Guambe & Alfredo Muxlhanga
a S SD B Q I ha by A 401 OED
HEFEI
D
b B
b QED ID B ID Ebba
D ID b BID IDI DID B
x e uma linha
aceita're
4 PhD ad BB B aDlbQlb Q adbaby