Grafos

UNIVERSIDADE SALGADO DE OLIVEIRA
PRÓ-REITORIA ACADÊMICA
CURSO DE ANÁLISE DE SISTEMAS

EVANDRO DE SOUZA PENA

TEORIA DOS GRAFOS E SIMULAÇÕES

Juiz de Fora
2010
EVANDRO DE SOUZA PENA

TEORIA DOS GRAFOS E SIMULAÇÕES

Relatório apresentado ao corpo docente do Curso de Análise de Sistemas da Universidade Salgado de Oliveira – UNIVERSO como requisito para aprovação na disciplina de Teoria dos Grafos.

Professor: Marcelo Linhares

Juiz de Fora
2010
“EVANDRO É BOM ALUNO, MAS NÃO TIROU BOA NOTA NA PROVA DE TEORIA DOS GRAFOS.”
A FRASE TEM UM TOTAL DE 58 CARACTERES.
OBS: Sem levar em conta espaços, acentos e pontuação. LETRAS | OCORRECIA | FREQ. RELATIVA % | BITS | N° DE BITS UTILIZADOS | F | 1 | 0,02 | 101110 | 6 | G | 1 | 0,02 | 101111 | 6 | L | 1 | 0,02 | 01000 | 5 | P | 1 | 0,02 | 01001 | 5 | B | 2 | 0,03 | 10000 | 5 | I | 2 | 0,03 | 10001 | 5 | M | 2 | 0,03 | 10010 | 5 | U | 2 | 0,03 | 10011 | 5 | V | 2 | 0,03 | 10110 | 5 | D | 3 | 0,05 | 0101 | 4 | S | 3 | 0,05 | 0110 | 4 | T | 3 | 0,05 | 0111 | 4 | E | 4 | 0,07 | 1010 | 4 | N | 5 | 0,09 | 1110 | 4 | R | 5 | 0,09 | 1111 | 4 | A | 10 | 0,17 | 110 | 3 | O | 11 | 0,19 | 00 | 2 | TOTAL | 58 | 0,99 | | 76 |

TOTAL DE CARACTERES NÃO REPETIDOS NA FRASE = 17
NUMERO DE BITS PARA FORMAR UM CARACTER = 2N => 25 = 32 Bits
TAMANHO DO ARQUIVO NÃO COMPRIMIDO = 5 X 58 = 290 bits
58 * (0,02*6)+ (0,02*6)+ (0,02*5)+ (0,02*5)+ (0,03*5)+ (0,03*5)+ (0,03*5)+ (0,03*5)+ (0,03*5)+ (0,05*4)+ (0,05*4)+ (0,05*4)+ (0,07*4)+ (0,09*4)+ (0,09*4)+ (0,17*3)+ (0,19*2)= 216
TX. DE COMPRESSÃO = ((216 / 290)-1)*100 = 25,51%
OBS: NÃO FECHOU EM 100% DEVIDO AOS AREDONDAMENTOS.
GRAFO
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
9R
9N
18
17A
6
12
3U
3M
6
3I
3B
2G
2F
4
3V
7
7E
14
35
19 O
38
5T
5S
2P
5D
4
9
2L
10
19
99
26