Técnico em Segurança do Trabalho - Informática Aplicada - 29/05/2012

APL 012 - LibreOffice Draw

O APL (Atividades Práticas de Laboratório) número 12 pode ser baixado aqui.

Técnico em Administração - Aula 28/05/2012

Tutorial Téc. Adm. - 002 - Diagrama de Gantt

O tutorial Téc. Adm. - 002 - Diagrama de Gantt pode ser baixado aqui.

Técnico em Segurança do Trabalho - Informática Aplicada - Aula 22/05/2012

APL 011 - LibreOffice Impress

Os aplicativos OpenOffice.org, BrOffice.org e LibreOffice são compatíveis entre si e têm a interface, se não iguais, quase que 100 % parecidas.

O APL (Atividades Práticas de Laboratório) 011 pode ser baixado aqui.

Ciência da Computação - Algoritmos e Estruturas de Dados III - Aula 22/05/2012

Trabalho Prático

Você sabia que 29 de Maio é o Dia do Estatístico

Objetivos Gerais
Aplicar as técnicas de ordenação de dados em memória principal e memória secundária, e pesquisa de informações, seja usando vetores ou árvores.

Objetivos Específicos
Desenvolver um software em uma linguagem qualquer (preferencialmente C, C++, Java ou Java para Android). A ideia de se produzir um software em Java para Android é simplesmente poder disponibilizá-lo no Google Play. Se não há interesse em disponibilizar o software, o desenvolvimento em Java poderá ser a porta para a portabilidade para o Java para Android, e assim, disponibilizá-lo posteriormente, quando se queira. O software deverá ser capaz de realizar estatísticas básicas de 1 ou 2 variáveis, quais sejam:

• Ordenação de dados
• Cálculo de valores Máximo e Mínimo
• Cálculo da Moda e Mediana
• Cálculo de Quartis, Decis e Percentis
• Cálculo da função Teste T (t de Student)
• Cálculo de Média Aritmética Simples e Ponderada
• Cálculo de Desvio Padrão Amostral ou do Universo
• Cálculo de Regressão Linear (deem uma olhada aqui - tem os cálculos)
• Cálculo de Correlação
• OPCIONAL: Plotar gráficos de coluna e/ou linha dos dados

Todas (ou quase todas) estas funções podem ser encontradas em aplicativos como OpenOffice Calc, BrOffice.org Calc, Libre Office Calc e Microsoft Excel. A ajuda para funções nestes aplicativos fornece explicações matemáticas e exemplos com cálculos resolvidos, que podem ser usados para teste das funções implementadas.

O software desenvolvido deverá ser capaz de trabalhar tanto com entrada manual, quanto entrada através de arquivo de texto.

Fontes de Pesquisa

• Cálculos estatísticos, com fórmulas e exemplos numéricos
• Apostila de estatística

Integrantes
O trabalho será em grupo de no máximo 5 alunos. Os grupos podem se comunicar (é óbvio), mas os trabalhos serão individualizados dentro de cada grupo, ou seja, para cada grupo um trabalho único.

Valor e Data de Entrega
O trabalho valerá 50 pontos. A entrega do trabalho será no dia 10/07/2012, conforme nosso calendário.

Ciência da Computação - Algoritmos e Estruturas de Dados III - Aula 10/05/2012

Pesquisa em Memória Primária: Pesquisa Binária

O Tutorial AED III - 016 - Pesquisa em Memória Primária: Pesquisa Binária pode ser baixado aqui.

Ciência da Computação - Algoritmos e Estruturas de Dados III - Aula 03/05/2012

Pesquisa em Memória Primária: Pesquisa Sequencial

O Tutorial AED III - 015 - Pesquisa em Memória Primária: Pesquisa Sequencial pode ser baixado aqui.

Técnico em Segurança do Trabalho - Informática Aplicada - Aula 15/05/2012

APL 010 - LibreOffice Impress

Na verdade esse APL é mais um treinamento intensivo em diversas funções do BrOffice.org Impress e não do LibreOffice em si. Entretanto, os aplicativos OpenOffice.org, BrOffice.org e LibreOffice são compatíveis entre si e têm a interface, se não iguais, quase que 100 % parecidas.

O APL (Atividades Práticas de Laboratório) 010 pode ser baixado aqui.

Ciência da Computação - Algoritmos e Estruturas de Dados III - Aula 15/05/2012

Árvore binária

Observação: esta aula será substituída depois pelo tutorial completo. No momento, devido a restrições do IF SE não consegui fazer o upload do tutorial.

Exemplo de árvore binária

Uma árvore binária é uma estrutura de dados caracterizada por:

• Ou não tem elemento algum (árvore vazia).
• Ou tem um elemento distinto, denominado raiz, com dois ponteiros para duas estruturas diferentes, denominadas sub-árvore esquerda e sub-árvore direita.

Perceba que a definição é recursiva e, devido a isso, muitas operações sobre árvores binárias utilizam recursão. É o tipo de árvore mais utilizado na computação. A principal utilização de árvores binárias são as árvores de busca binária.

Definições para árvores binárias

Os nós de uma árvore binária possuem graus zero, um ou dois. Um nó de grau zero é denominado folha.
Em uma árvore binária, por definição, cada nó poderá ter até duas folhas, sendo que ela se compara com a abb (árvore binária de busca), apesar de não ter a propriedade da mesma ("na abb, existe uma regra na inserção").
A profundidade de um nó é a distância deste nó até a raiz. Um conjunto de nós com a mesma profundidade é denominado nível da árvore. A maior profundidade de um nó, é a altura da árvore.
Uma árvore "estritamente binária" é uma árvore na qual todo nó tem zero ou duas folhas.
Existem autores, porém, que adotam essa definição para o termo quase completa, e utilizam o termo completa apenas para árvores em que todos os níveis têm o máximo número de elementos.

Definições em teoria dos grafos

Em teoria dos grafos, uma árvore binária é definida como um grafo acíclico, conexo, dirigido e que cada nó não tem grau maior que 2. Assim sendo, só existe um caminho entre dois nós distintos.
E cada ramo da árvore é um vértice dirigido, sem peso, que parte do pai e vai o filho.

Inserção

O algoritmo da inserção em árvores binárias são facilmente implementadas através de função recursiva.
Algoritmo da inserção em C:

 void inserir(struct No **pRaiz, int numero){
     if(*pRaiz == NULL){
* pRaiz = (struct No *) malloc(sizeof(struct No));
         (*pRaiz)→pEsquerda = NULL;
         (*pRaiz)→pDireira = NULL;
         (*pRaiz)→numero = numero;
     }else{
         if(numero <(*pRaiz)→numero)  
              inserir(&(*pRaiz)→pEsquerda, numero));
         else  
              inserir(&(*pRaiz)→pDireita, numero));
     }
 }

Percursos em árvore

Existem três tipos de percursos: Percurso em ordem simétrica(em-ordem), pré-ordem e pós-ordem.

Ordem Simétrica

O algoritmo recursivo desse percurso em C é:

 void emOrdem(struct No *pNo) {
     if(pNo != NULL) {
         emOrdem(pNo→pEsquerda);
         visita(pNo);
         emOrdem(pNo→pDireita);
     }
 }

Para a árvore acima, o percurso seria: 2, 7, 5, 6, 11, 2, 5, 4 e 9. Veja a linha de execução:

• emOrdem(2→esq)
  • emOrdem(7→esq)
    • emOrdem(2→esq)
    • visita(2)
    • emOrdem(2→dir)
  • visita(7)
  • emOrdem(7→dir)
    • emOrdem(6→esq)
      • emOrdem(5→esq)
      • visita(5)
      • emOrdem(5→dir)
    • visita(6)
    • emOrdem(6→dir)
      • emOrdem(11→esq)
      • visita(11)
      • emOrdem(11→dir)
• visita(2)
• emOrdem(2→dir)
  • emOrdem(5→esq)
  • visita(5)
  • emOrdem(5→dir)
    • emOrdem(9→esq)
      • emOrdem(4→esq)
      • visita(4)
      • emOrdem(4→dir)
    • visita(9)
    • emOrdem(9→dir)

Pré-Ordem

O algoritmo recursivo desse percurso em C é:

 void preOrdem(Struct No *pNo){
     if(pNo != NULL){
         visita(pNo);
         preOrdem(pNo→pEsquerda);
         preOrdem(pNo→pDireita);
     }
 }

Para a árvore acima, o percurso seria: 2, 7, 2, 6, 5, 11, 5, 9 e 4. Veja a linha de execução:

• visita(2)
• preOrdem(2→esq)
  • visita(7)
  • preOrdem(7→esq)
    • visita(2)
    • preOrdem(2→esq)
    • preOrdem(2→dir)
  • preOrdem(7→dir)
    • visita(6)
    • preOrdem(6→esq)
      • visita(5)
      • preOrdem(5→esq)
      • preOrdem(5→dir)
    • preOrdem(6→dir)
      • visita(11)
      • preOrdem(11→esq)
      • preOrdem(11→dir)
• preOrdem(2→dir)
  • visita(5)
  • preOrdem(5→esq)
  • preOrdem(5→dir)
    • visita(9)
    • preOrdem(9→esq)
      • visita(4)
      • preOrdem(4→esq)
      • preOrdem(4→dir)
    • preOrdem(9→dir)

Pós-Ordem

O algoritmo recursivo desse percurso em C é:

 void posOrdem(Struct No *pNo){
     if(pNo != NULL){
         posOrdem(pNo→pEsquerda);
         posOrdem(pNo→pDireita);
         visita(pNo);
     }
 }

Para a árvore acima, o percurso seria: 2, 5, 11, 6, 7, 4, 9, 5 e 2. Veja a linha de execução:

• posOrdem(2→esq)
  • posOrdem(7→esq)
    • posOrdem(2→esq)
    • posOrdem(2→dir)
    • visita(2)
  • posOrdem(7→dir)
    • posOrdem(6→esq)
      • posOrdem(5→esq)
      • posOrdem(5→dir)
      • visita(5)
    • posOrdem(6→dir)
      • posOrdem(11→esq)
      • posOrdem(11→dir)
      • visita(11)
    • visita(6)
  • visita(7)
• posOrdem(2→dir)
  • posOrdem(5→esq)
  • posOrdem(5→dir)
    • posOrdem(9→esq)
      • posOrdem(4→esq)
      • posOrdem(4→dir)
      • visita(4)
    • posOrdem(9→dir)
    • visita(9)
  • visita(5)
• visita(2)

Soma Elementos

 public int SomaElementos(No raiz){
    if (raiz != null){
  soma=this.SomaElementos(raiz.p_Esq)+this.SomaElementos(raiz.p_Dir)+raiz.ObtemValor();
    return soma;
    }else
        return 0;
 }

Maior Elemento

 public int MaiorElemento(No raiz){
   if (raiz != null){
      if (maior < raiz.ObtemValor())
          maior = raiz.ObtemValor();
      this.MaiorElemento(raiz.p_Esq);
      this.MaiorElemento(raiz.p_Dir);
      return maior;
    }else
         return 0;
  }

Menor Elemento

 public int MenorElemento(No raiz){
   if (raiz != null){
      if (menor > raiz.ObtemValor())
          menor = raiz.ObtemValor();
      this.MenorElemento(raiz.p_Esq);
      this.MenorElemento(raiz.p_Dir);
      return menor;
    }else
        return 0;
  }

Transformação de uma árvore n-ária

Uma árvore n-ária qualquer (árvore cujos nós possuem graus menores ou iguais a n) podem ser representados por uma árvore binária. Um exemplo dessa transformação pode ser vista em

Métodos para representação de árvores binárias

Uma das maneiras mais simples de representar árvores binárias em linguagens de programação é por meio de arranjos unidimensionais (vetores). Caso a raiz esteja na posição zero, dado um nó de índice i qualquer, os seus filhos terão índices e e o seu pai terá índice piso((i - 1)/2). Caso a raiz esteja na posição um, os filhos terão índices e e o pai terá índice piso(i/2). Essa implementação é utilizada para representar árvores completas ou quase completas. Heaps, que são árvores binárias quase completas são implementadas na forma de um vetor de uma maneira bastante eficiente.
Apesar da simplicidade, essa representação requer uma grande quantidade de memória contígua para o armazenamento de árvores grandes, o crescimento desta é díficil de implementar e manter e pode haver grande quantidade de desperdício de memória.

Uma pequena árvore binária com raiz na posição 0, representada como um vetor.

Em uma linguagem que possua suporte a estruturas e referências (por exemplo pascal e C), as árvores podem ser implementadas a partir de nós, com um, ou mais, campos para a(s) informação(ões) principal(is) e dois campos apontadores especiais, denominados esquerda e direita, que fazem referência às sub-árvores esquerda e direita, respectivamente. Algumas vezes, há um apontador para o pai. Em um nó do tipo folha, os campos apontadores possuem valores especiais (nil em Pascal e "NULL" em C).

Árvore binária de busca

Uma árvore binária de busca de tamanho 9 e profundidade 3, com raiz 8 e folhas 1, 4, 7 e 13.

Em Ciência da computação, uma árvore binária de busca (ou árvore binária de pesquisa) é uma estrutura de dados de árvore binária baseada em nós, onde todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz (esta é a forma padrão, podendo as subárvores serem invertidas, dependendo da aplicação). O objetivo desta árvore é estruturar os dados de forma flexível, permitindo busca binária.

• Nós - são todos os itens guardados na árvore
• Raiz - é o nó do topo da árvore (no caso da figura acima, a raiz é o nó 8)
• Filhos - são os nós que vem depois dos outros nós (no caso da figura acima, o nó 6 é filho do 3)
• Pais - são os nós que vem antes dos outros nós (no caso da figura acima, o nó 10 é pai do 14)
• Folhas - são os nós que não têm filhos; são os últimos nós da árvore (no caso da figura acima, as folhas são 1, 4, 7 e 13)

Operações

Operações em uma árvore binária requerem comparações entre nós. Essas comparações são feitas com chamadas a um comparador, que é uma subrotina que calcula a ordem total (ordem linear) em dois valores quaisquer. Esse comparador pode ser explícita ou implicitamente definido, dependendo da linguagem em que a árvore binária de busca está implementada.

Busca

Buscando um valor na árvore binária.

A busca em uma árvore binária por um valor específico pode ser um processo recursivo ou iterativo. Essa explicação usará um método recursivo.
A busca começa examinando o nó raiz. Se a árvore está vazia, o valor procurado não pode existir na árvore. Caso contrário, se o valor é igual a raiz, a busca foi bem sucedida. Se o valor é menor do que a raiz, a busca segue pela subárvore esquerda. Similarmente, se o valor é maior do que a raiz, a busca segue pela subárvore direita. Esse processo é repetido até o valor ser encontrado ou a subárvore ser nula (vazia). Se o valor não for encontrado até a busca chegar na subárvore nula, então o valor não deve estar presente na árvore.

Inserção

A inserção começa com uma busca, procurando pelo valor, mas se não for encontrado, procuram-se as subárvores da esquerda ou direita, como na busca. Eventualmente, alcança-se a folha, inserindo-se então o valor nesta posição. Ou seja, a raiz é examinada e introduz-se um nó novo na subárvore da esquerda se o valor novo for menor do que a raiz, ou na subárvore da direita se o valor novo for maior do que a raiz. Abaixo, um algoritmo de inserção em Python:

def arvore_binaria_inserir(no, chave, valor):
    if no is None:
        return TreeNode(None, chave, valor, None)
    if chave == no.chave:
        return TreeNode(no.filho_esquerdo, chave, valor, no.filho_direito)
    if chave < no.chave:
        return TreeNode(arvore_binaria_inserir(no.filho_esquerdo, chave, valor), no.chave, no.valor, no.filho_direito)
    else:
        return TreeNode(no.filho_esquerdo, no.chave, no.valor, arvore_binaria_inserir(no.filho_direito, chave, valor))

Esta operação requer O (log n) vezes para o caso médio e necessita de Ômega (n) no pior caso. A fim de introduzir um nó novo na árvore, seu valor é primeiro comparado com o valor da raiz. Se seu valor for menor que a raiz, é comparado então com o valor do filho da esquerda da raiz. Se seu valor for maior, está comparado com o filho da direita da raiz. Este processo continua até que o nó novo esteja comparado com um nó da folha, e então adiciona-se o filho da direita ou esquerda, dependendo de seu valor.

Exclusão

A exclusão de um nó é um processo mais complexo. Para excluir um nó de uma árvore binária de busca, há de se considerar três casos distintos para a exclusão:

Exclusão na folha

A exclusão na folha é a mais simples, basta removê-lo da árvore.

Exclusão de um nó com um filho

Excluindo-o, o filho sobe para a posição do pai.

Exclusão de um nó com dois filhos

Neste caso, pode-se operar de duas maneiras diferentes. Pode-se substituir o valor do nó a ser retirado pelo valor sucessor (o nó mais à esquerda da subárvore direita) ou pelo valor antecessor (o nó mais à direita da subárvore esquerda), removendo-se aí o nó sucessor (ou antecessor).

No exemplo acima, o nó de valor 30 está para ser removido, e possui como sucessor imediato o valor 35 (nó mais à esquerda da sua sub-árvore direita). Assim sendo, na exclusão, o valor 35 será promovido no lugar do nó a ser excluído, enquanto a sua sub-árvore (direita) será promovida para sub-árvore esquerda do 40, como pode ser visto na figura. Ao excluir, ou mesmo ao incluir, um nó, pode haver o desbalanceamento da árvore, que pode ser corrigido, por exemplo, com o balanceamento AVL.

Embora esta operação não percorra sempre a árvore até uma folha, esta é sempre uma possibilidade; assim, no pior caso, requer o tempo proporcional à altura da árvore, visitando-se cada nó somente uma única vez.

Transversal

Em uma árvore binária de busca podem-se fazer os três percursos que se fazem para qualquer árvore binária (percursos em inordem, pré-ordem e pós-ordem). É interessante notar que, quando se faz um percurso em ordem em uma árvore binária de busca, os valores dos nós aparecem em ordem crescente. A operação "Percorre" tem como objetivo percorrer a árvore numa dada ordem, enumerando os seus nós. Quando um nó é enumerado, diz-se que ele foi "visitado".
Pré-ordem (ou profundidade):

1. Visita a raiz
2. Percorre a subárvore esquerda em pré-ordem
3. Percorre a subárvore direita em pré-ordem

Ordem Simétrica:

1. Percorre a subárvore esquerda em ordem simétrica
2. Visita a raiz
3. Percorre a subárvore direita em ordem simétrica

Pós-ordem:

1. Percorre a subárvore esquerda em pós-ordem
2. Percorre a subárvore direita em pós-ordem
3. Visita a raiz

Algoritmo de busca transversal:

def arvore_binaria_transversal(nó_arvore):
    if nó_arvore is None: return
    esquerda, nó_valor, direita = nó_arvore
    arvore_binaria_transversal(esquerda)
    visite(nó_valor)
    arvore_binaria_transversal(direita)

Árvore tranversal requer O(n) vezes, desde que se visite cada nó.

Ordenação

Uma árvore binária de busca pode ser usada para executar um simples algoritmo de ordenação. Para fazer isto, são introduzidos todos os valores desejados, classificado-se depois em uma árvore binária de busca, atravessando-a em ordem, construindo um novo resultado:

def criar_arvore_binaria(valor):
    arvore = None
    for v in valor:
        arvore = arvore_binaria_de_insercao(arvore, v)
    return arvore
 
def arvore_binaria_transversa(nó_arvore):
    if nó_arvore is None: return []
    else:
        esquerda, valor, direita = nó_arvore
        return (arvore_binaria_transversal(esquerda) + [valor] + arvore_binaria_transversal(direita))

No pior caso criar_arvore_binaria é O(n²) se lhe alimentar uma lista ordenada de valores, de forma semelhante a uma lista ligada . Para o exemplo, o criar_arvore_binaria([1, 2, 3, 4, 5]) rende a árvore (None, 1, (None, 2, (None, 3, (None, 4 (None, 5, None))))).

Técnico em Administração - Aula 14/05/2012

Tutorial Téc. Adm. 001 - Curva ABC e Princípio de Pareto

Não Conhece o BrOffice.org Calc

Para os alunos que ainda não conhecem a planilha eletrônica BrOffice.org Calc, deem uma olhada aqui.



Já Conhece o BrOffice.org Calc

Curva ABC e Princípio de Pareto 

A Curva ABC e o Princípio de Pareto, também conhecido como regra do 80-20, são muito usadas em administração. Por exemplo, segundo este princípio, podemos dizer que 80% das pessoas que leem esta postagem entenderão apenas 20% do que ela diz. Por outro lado, 20% das pessoas que leem esta postagem entenderão 80%.

Você pode pesquisar a Curva ABC pelo Google clicando aqui e o Princípio de Pareto clicando aqui.

Se você já conhece a planilha eletrônica BrOffice.org Calc, o Tutorial Téc. Adm. 001 - Curva ABC e Princípio de Pareto pode ser baixado aqui.

Observação

Na figura 3.2 do Tutorial Téc. Adm. - 001 - Curva ABC, corrija os valores da coluna C e D, a partir da linha 3, para:
120 e 50
100 e 10
40 e 100
400 e 20
2000 e 10
10000 e 10
135 e 10
135 e 10

Técnico em Administração - Aula 07/05/2012

APL 008 - BrOffice.org Calc

Continuação da aula anterior. O APL (Atividades Práticas de Laboratório) número 8 pode ser baixado aqui.

Ciência da Computação - Algoritmos e Estruturas de Dados III - Aula 10/05/2012

Usos dos algoritmos de busca
 
Determinação da moda

início

  para i de 1 até n - 1 faça

    conta <-- 1;

    para j de i + 1 até n faça

      se tabela[i] = tabela[j] então 

        conta <-- conta + 1;

      fim-se;

    fim-para;

    freq[i] <-- conta;

  fim-para;

  max <-- 1;

  para i de 2 até n faça

    se freq[i] > freq[max] então 

      max <-- i; 

    fim-se;

  fim-para;

  moda <-- tabela[max];

  imprima("Moda igual a ", moda);

fim.

Tente fazer um algoritmo mais eficiente...

Técnico em Segurança do Trabalho - Informática Aplicada - Aula 08/05/2012

APL 009 - LibreOffice Impress

O APL (Atividades Práticas de Laboratório) 009 pode ser baixado aqui.