Monthly Archive for abril, 2010

Page 3 of 3

Análise de Algorítimos 1218/32 – Aula 5 – 12/04/2010

Published on 13/04/2010 in Análise Alg. 1218/32. 0 Comments

Notas de Aula (Google Docs)

Exercícios: Indução
1. Demonstrar por inducao matematica que
\sum_{i=1}^{n}{\frac{1}{1i} < 1} ,   para r\succeq 1
2. Demonstrar por inducao matematica que 
n! \succ x^{n-1}  , para n>=2 
——————————————————————————
Análise de fragmentos de código

A
sum = =
for (i=1; i<=m; i++)                                          |
   for(j=1l j<=n; j++)                           | \Theta (n)    | \Theta (n^2)
      sum++;                     | \Theta (1)        |              |
Analise: Como operação SUM ++ é o(1), então a complexidade do codigo é equivalente ao numero de vezes  que a operação SUM ++ é O(n2)
Ou ainda: Temos dois lacos aninhados que executam r repetições cada um, com o corpo do laco interno com complexidade o(1). Assim, a complexidade total é n.nO(1)=O(n2)
B
SUM = 0;
for (i=1; c<=n; i++)
    for (j=1; i<=i; j++)
       sum++;
i         1        2           3                    n
1..1   1..2    1..3                             1..n
1   +   2    +   3                +               n
A linha 1 isoladamente tem complexidade \Theta (1)
A linha 4 isoladamente tem complexidade \Theta (1)
A Quantidade de vezes que a linha 4 é executada depende da quantidade de vezes que o laço
da linha 3-4 é executada. Para tal laço, seu conteudo é executado j vezesm conj=1..i
O laço das linhas 3-4 é dependente do laço das linhas 2-4 que é executado n vezes c/ assumindo os valores de 1..n
Logo a quantidade de vezes que a linha 4 é executada é dada por:
T(n) = \sum_{i=1}^{n}{}
T(n) =  \frac{ n(n-1)}{2}
T(n) = \frac{ n^{2} }{2} + \frac{ n }{2}     
Logo a complexidade é proposrcional a n^{2} , assim
T(n) = \Theta n^{2}
Demonstração pela definição assintótica:
T(n) =\frac{1}{2}\cdot n^{2} + \frac{1}{2}\cdot n  ;   T(n) = \Theta (n^2)  ?
\lim_{n \rightarrow \infty}{\frac{\frac{1}{2} \cdot n^{2}+ \frac{1}{2}\cdot n}{n^2} }
\lim_{n \rightarrow \infty}{(\frac{1}{2} \cdot n^{2}+ \frac{1}{2}\cdot n) \cdot \frac{1}{n^2} }
\lim_{n \rightarrow \infty }{\frac{1}{2} + \frac{1}{2^n} }    
L=\frac{1}{2}
Que é uma constante diferente de O logo,
T(n) = \Theta (n^2)
C
T(n) = \Theta (n^2)
sum=0                       \Theta (1)     Considerando que n seja uma potencia de 2
for (k=1; k<=n; k*=2               
  for(j=1; j<=n; j++)               | \Theta (n)
     sum ++;              | \Theta (1)   |
A linha 4 isoladamente é \Theta (1)
pelo laço das linhas 3-4 a linha 4 é executada N vezes. com as linhas 3-4 são n O(1) = O(n)
As linhas 3-4 são executadas uma quantidade de vezes depende do laço das linhas 2-4 onde tem-se
Iteração     1         2     3      4    ….    n
K               1        2     4      8    …..    n 
                2p0    2p1  2p2   2p3  …… 
Assim p/ saber quantas vezes seu conteudo é executado e necessario saber quantos valores diferente k assume até n(inclusive)
Supondo um índice i p/cada iteracao, dado pelo valor do expoente k em base 2, da forma
i = T +1
Para saber o valor de r na última iteracao, tem-se
2^{r} = n  logo   lg 2^r = lg n   logo  r lg2 = lg n +1 = lg n   
r = lg n
E p/ saber o valor de i na última iteração tem-se
i = lg n +1
Assim, o trecho 2-4 é executado
lgn +1    \Theta (n)m resultando em T(n) = \Theta (n lg n) 
D
sum = 0;
for (k=1; k<=n; k*=2);
   for (j=1; j<=k; j++);
        sum++;

Sistemas Operacionais 1219/31 AULA 06 08/04/2010 – Recado

Published on 08/04/2010 in Sistemas Op. 1219/31. 0 Comments

Recado: Para quem faltou na aula do dia 01/04/2010 e quiser fazer o trabalho  dado, deverá deixar amanhã das 19h15 às 19h35 no lab do mestrado Bloco C56, um resumo manuscrito do conteúdo visto até hoje (08/04/2010)

Banco de Dados 1217/31 – Google Groups

Published on 07/04/2010 in Banco Dados 1217/31. 0 Comments

Google Groups, pra facilitar comunicação entre turma de Banco de Dados 1217/31.
Criado por Maicon Henrique:http://groups.google.com/group/grupo-de-banco-de-dados-inf2010?hl=pt

Arquiteturas de Computadores II – 1216/31 AULA 05 30/03/2010

Published on 07/04/2010 in Arq. Comp. II 1216/31. 0 Comments

Foi passado exercícios sobre barramentos
(Obs.: Irei disponibilizar scan do carderno se houver >=1 pedidos nos comentários)

Material interessante para estudo:
Arquitetura do Processador 8085 – UNESP

Engenharia de Software II 1215/31- Aula 10 (29/03) e 11 (05/04)

Published on 06/04/2010 in Eng. Soft. II 1215/31. 0 Comments

Material Arquitetura de Software (Moodle)


Notas de Aula:



Requisitos de Arquitetura
Atributos de Projeto


Metas de Modularidade
-Diminuir o problema em subproblemas
-Entender Partes do sistema separadamente


Arquitetura Duas Camadas
  Cliente – Servidor


Arquitetura Multiplas Camadas
  Cliente – Servidor de Aplicação – Banco de Dados


Arquitetura Sistema de Tempo Real









Banco de Dados (1217/31) – Aula 10 31/03/2010 Atividade para o trabalho

Published on 02/04/2010 in Banco Dados 1217/31. 0 Comments

Referência para trabalho de Banco de Dados Resolução 061/2003-CEP

Atividades 01:
            

  • Elicitação de Requisitos
  • Diagrama Use-Case
  • Diagrama de E.R 
Download
Database System Concepts [PDF]
Obs: Pessoal, se estiver faltando algo, por favor deixem comentários. Agradeço desde já vossa ajuda.

Sistemas Operacionais 1219/31 AULA 05 01/04/2010

Published on 01/04/2010 in Sistemas Op. 1219/31. 0 Comments

Aula de Slides


Notas de Aula:


Gerenciamento de memória

  • Sistema de Arquivos
  • Tipos de chamadas ao Sistema: Criar, remover, ler, escrever arquivos
  • Path: Diretório-Raiz
  • Acessos: Pemissões especificas para manipular arquivos
  • Shell – Interpretador de comandos
  • Meio de Comunicação do usuário com o SO
  • Interface gráfica ou texto
  • Chamadas do Sistema


  1. Salva contexto dos registradores
  2. Altera modo do processador para kernel
  3. Rotina do Sistema
  4. Altera modo do processador para usuário
  5. Restaura o contexto dos registradores

  • Classificações de Estruturas de SO
  1. Monolíticas: Vários módulos que são compilados separadamente em seguida linkados
  2. Camadas: Kernel, Executivo, Supervisor e Usuário
  3. Maquina Virtual: Intermediário entre Hardware e Software; 
  4. Exonúcleo: Serviços dos sistema operacionais que são controlados por servidores (Servidor de Arquivo, Memória, Rede, Processo e Impressão) no modo usuário. 
  5. Cliente-Servidor: Sistemas Distribuídos: Cliente solicita serviços


Aviso 1218/31 – Análise de Algorítmos

Published on 01/04/2010 in Análise Alg. 1218/32. 0 Comments

Não haverá aula para turma 1218/31 hoje 01/04/2010.

Login