quinta-feira, 28 de julho de 2016

Relato de experiência: Atividades de acompanhamento no PET Computação



Atualmente, já faz parte da cultura do PET Computação a atividade de Acompanhamento. É uma atividade simples, que requer pouca dedicação em tempo dos integrantes, mas que contribui fortemente para o andamento das atividades. Neste texto, pretende-se compartilhar um pouco de nossa experiência com esta atividade e tentar transmitir por que o PET Computação a considera importante.


O Acompanhamento é uma atividade de respondibilidade de uma pessoa do grupo, cujo dever é lembrar e notificar os outros integrantes de suas responsabilidades. Contudo, a ideia não é que o Acompanhamento sirva como um método de coação ou pressão, mas sim de um momento em que todos os integrantes possam visualizar as responsabilidades e pendências, para um curto período de tempo, que o grupo delegou e dividiu entre si.  Isso contribui com a organização e eficiência do grupo, pois é possível que uma pessoa atarefada esqueça de alguma responsabilidade sua, e ter alguém já com a função de lembrar a todas e todos de suas obrigações evita tais esquecimentos. Além disso, o acompanhamento serve como um registro de pendências, podendo ser um termômetro de ineficiência, se, por exemplo, alguma atividade estiver sendo revisitada no acompanhamento já há algum tempo.


Além de servir como registro e lembretes de objetivos e pendências, o Acompanhamento serve também para: planejar futuras atividades; criar senso de responsabilidade nos integrantes; criar o sentimento, no grupo, de estar em intensa atividade, o que é estimulante; melhor compreender prioridades e problemas não resolvidos; e, por fim, contribui com o fluxo de atividades que sejam dependentes.


O grupo define como realizar sua atividade de Acompanhamento. Nós, do PET Computação, a realizamos semanalmente e utilizamos threads no e-mail do grupo e notificações em documentos virtuais (as pautas das reuniões) para enviar as notificações e lembretes das atividades a serem realizadas.


O Acompanhamento deve ser compreendido como uma extensão das reuniões do grupo! Portanto, é necessário que os integrantes estejam envolvidos nesta atividade!

Por,
Ítalo Medeiros - Integrante do PET Computação








quarta-feira, 27 de julho de 2016

Engenharia de Software: uma introdução

Imagine que você é líder de um grupo, no contexto de 25.000  pessoas, manipulando mais que 85 terabytes de dados, em 2 bilhões de linhas de código e essa gente toda gera 45.000 modificações diárias nisso tudo. Julga que é exagero e que não é possível gerenciar projetos com essa magnitude? Pois saiba que os produtos google estão envolvidos nessa complexidade. A pergunta que não quer calar é: como eles conseguem essa façanha?
Google-Apps.jpg
Bem vindo à Engenharia de Software, um ramo do conhecimento onde você aprenderá sobre como gerenciar pessoas com propósito de fabricar produtos e serviços de software. Em geral, uma engenharia se preocupa em responder quatro perguntas básicas no que diz respeito a gerenciar grupos de pessoas: Quem faz? O que faz? Como faz? Quando faz? Sabendo disso, basta pensar na engenharia no contexto de software...
Tudo começou com a crise do software, onde os profissionais e o mercado já entendiam a magnitude e impacto dos produtos de software e hardware na sociedade, mas ficaram paralisados com a complexidade de ter que construir projetos do zero todas as vezes para cada máquina específica. A partir disso, começou a luta para construir processos industriais robustos para efetivo desenvolvimento de software. De lá para cá, muita coisa boa tem sido proposta e aprimorada.
Para finalizar, é importante destacar duas abordagens para processo de desenvolvimento de software. A primeira é o modelo em cascata, cuja ideia é construir um produto de software em, basicamente, seis passos: Levantamento de Requisitos, Análise, Projeto, Implementação, Testes e Implantação. Como esse processo é lento, custoso e o projeto final pode não ser o que resolve o problema do cliente, há o modelo iterativo e incremental que consiste em fazer os seis passos citados em ciclos para alcançar pequenos objetivos do produto final, até que o produto esteja acabado.
Enfim, essa conversa toda é muito superficial se considerarmos todas as nuances e desafios dessa ciência. Então fica o convite para que você pesquise e aprenda mais sobre efetivo gerenciamento de pessoas com propósito bem definido no contexto de software. Quem sabe você acaba entrando para o grupo de 25.000 algum dia?


Por,

Eri Jonhson Oliveira da Silva - Integrante do PET Computação

segunda-feira, 25 de julho de 2016

Algoritmos Genéticos

 Algoritmos Genéticos


Atividades de busca e otimização são sempre necessárias nos mais diversos ambientes, essas atividades possuem vários componentes, entre eles: o espaço de busca, onde são consideradas todas as possibilidades de solução de um determinado problema e a função de avaliação (ou função de custo), que é função que avalia a qualidade dos membros do espaço de busca. Existem muitos métodos de busca e funções de avaliação. 


Nesse sentido a utilização dos algoritmos Genéticos mostra-se eficiente na busca de soluções ótimas, ou aproximadamente ótimas em uma grande variedade de problemas, pois não impõem muitas das limitações encontradas nos métodos de busca tradicionais.  

Para mais detalhes teóricos sobre o funcionamento dos algoritmos genéticos, leia nosso primeiro post sobre esse tema. Esse post possui carácter mais prático.

Os passos para construção dos algoritmos genéticos são descritos na sequencia e na imagem a seguir.
  • [Início] Geração aleatória de uma população de n cromossomos. 
  • [Adaptação] Verificar a função objetivo f(x) de cada cromossomo. 
  • População] Cria-se uma nova população pela repetição 
  • [Seleção] Selecione um par de cromossomos da população de acordo com a adaptação de cada um (os mais bem adaptados  tem maior chance de serem escolhidos) 
  • [Crossover] Produza dois descendentes (filhos) realizando cruzamento com os cromossomos dos pais. O ponto para a realização do cruzamento deve ser aleatório. 
  • [Mutação] Com uma certa probabilidade, o descendente  sofre mutação em cada posição no cromossomo.  
  • Aceitação] Coloque os descendentes em uma nova população, juntamente com a melhor solução da geração velha.
 


 Abaixo é mostrado um exemplo de algoritmo genético. 


função AlgoritmoGenético(população, função-objetivo) saídas: indivíduo
 entradas: população→ uma lista de indivíduos
           função-objetivo→ uma função que recebe um indivíduo e retorna um número real.
 repetir
    lista de pais := seleção(população, função-objetivo)
    população := reprodução(lista de pais)
 enquanto nenhuma condiçao de parada for atingida
 retorna o melhor indivíduo da população de acordo com a função-objetivo
 

Agora se você quer um exemplo mais complexo e em Java, acesse aqui.
 
Por,
Gleyser Guimarães - Integrante do PET Computação










sexta-feira, 22 de julho de 2016

A Linguagem de Programação LISP

Talvez muitos programadores da nova geração não conheçam a linguagem LISP, ou apenas a conheça superficialmente. Ela é a segunda linguagem de alto nível mais antiga (Fortran é a primeira), surgiu em 1958 e trouxe várias inovações.
Atualmente, não é muito utilizada, sendo a vigésima nona linguagem mais utilizada de acordo com índice TIOBE.
Nasceu como uma linguagem de notação matemática para programas de computador e rapidamente se tornou uma das linguagens mais utilizadas no meio da inteligência artificial.
O seu nome vem de List Processing. Trabalha com dois tipos de dados: átomo e lista. Uma lista é uma sequência finita de elementos, onde cada elemento é um átomo ou outra lista. Um átomo é um número ou um símbolo, onde um símbolo é, essencialmente, um item único (podendo ser qualquer valor alfanumérico).
Ela é uma linguagem interpretada, dinamicamente e fortemente tipada do paradigma funcional. Nela, os dados e o código fonte são dispostos como lista, o que permite que um programa inteiro seja dado como entrada de outro. Como ela é feita basicamente com funções e listas, possui um alto nível de abstração e um poderoso uso de recursividade.
Uma grande inovação para a época foi a implantação de um garbage collector, que tirava das costas do programador a necessidade de se preocupar em desalocar espaços não utilizados na memória.
Foi uma linguagem que marcou bastante a época e certamente influenciou muitas outras. Algumas universidade ainda a utilizam didaticamente para mostrar melhor o paradigma funcional. A linguagem LISP foi tema de uma das questões do POSCOMP 2015.


Por,
Antunes Dantas - Integrante do PET Computação

segunda-feira, 18 de julho de 2016

Algoritmos Gulosos



Vários problemas do cotidiano podem ser tratados matematicamente. Existem na matemática, por exemplo, os problemas de otimização, que consistem em determinar o valor máximo ou mínimo que uma função pode assumir em um dado intervalo. E uma infinidade de situações podem ser descritas como problemas de otimização, como saber a quantidade mínima de moedas para dar um troco, o caminho mais curto entre dois pontos de uma cidade  ou o valor máximo de objetos que podem ser colocados em uma mochila sem que estes excedam o peso suportado pela mesma.

Problemas desse tipo podem ser computacionalmente resolvidos utilizando o MÉTODO GULOSO de construção de algoritmos, que visa o alcance de uma solução ótima global a partir da realização das melhores escolhas momentâneas.

Têm-se como características dos Algoritmos Gulosos:
  • Em cada iteração escolhem o objeto mais “apetitoso” que veem pela frente;
  • Não medem a consequência futura dos seus atos;
  • Jamais se arrependem ou voltam atrás, as escolhas em cada iteração são definitivas;
  • Têm prova de correção não trivial.

Os Algoritmos Gulosos em geral são rápidos e de fácil implementação, porém em algumas situações a melhor solução não é uma sequencia das melhores escolhas do momento.

Um exemplo de aplicação, é a bastante utilizada CODIFICAÇÃO DE HUFFMAN.

HUFFMAN(C)
n = |C|
Q = C
for i=1 to n-1
alocar um novo nó z
z.esquerda = x = EXTRAIR_MIN(Q)
z.direita = y = EXTRAIR_MIN(Q)
z.freq = x.freq + y.freq
INSERIR(Q, z)
return EXTRAIR_MIN(Q) //retorna a raiz da árvore

A Codificação de Huffman é um algoritmo de compressão de dados que usa a probabilidade de ocorrência dos símbolos no conjunto de dados a ser comprimido para determinar códigos de tamanho variável para cada símbolo, visando atribuir a um símbolo de alta frequência, uma curta sequência de bits. Para isto constrói-se uma árvore binária baseada nas probabilidades de ocorrência de cada símbolo.

Cada folha da árvore representará um símbolo presente no dado e a sua probabilidade de ocorrência. Os nós intermediários representam a soma das probabilidades de seus descendentes, enquanto a raiz representa a soma das probabilidades de todos os símbolos. A cada iteração, são unidos os dois símbolos de menor probabilidade, que são unidos em um nó com a soma destas probabilidades. Este novo nó terá como filhos os elementos que foram somados e passa a ser considerado como um símbolo único. O processo é repetido até que todos os símbolos estejam atrelados à raiz.

A cada aresta da árvore resultante será associado um dígito binário, e o código correspondente de cada símbolo será determinado pelo caminho da raiz até a sua respectiva folha.

Para exemplificar a execução do algoritmo, vamos contrair a string "PERERECA":

Utilizando a codificação ASCII temos a seguinte representação dos caracteres:
Caractere
P
E
R
C
A
Código
01010000
01000101
01010010
01000011
01000001

O que, para representar a palavra, geraria a sequência de bits:
0101000001000101010100100100010101010010010001010100001101000001. Um total de 64 bits.

Utilizando a forma padrão de compressão, onde cada caractere tem um tamanho fixo, a menor codificação que obteríamos seria com 3 bits para cada caractere:
Caractere
P
E
R
C
A
Código
000
001
010
011
100

Gerando a sequência 000001010001010001011100. Um total de 24 bits, 40 a menos que em ASCII.

Para usar o código de Huffman, precisamos montar a árvore. Inicialmente vamos contar o número de ocorrência dos caracteres:
Caractere
P
E
R
C
A
Ocorrência
1
3
2
1
1

Já temos alguns nós na nossa árvore:

Vamos agrupar o dois caracteres menos frequentes em um novo nó:

A cada iteração faremos o mesmo (a melhor solução local: agrupar os dois nós com menor frequência):



Até, enfim obtermos uma raiz que agrupará todos os caracteres.


O caminho da raiz até a folha que representa o caractere definirá o seu código:
Caractere
P
E
R
C
A
Código
101
0
100
110
111

O que gera a sequência 101010001000110111. Um total de 18 bits, 6 a menos que a compressão padrão e 46 a menos que em ASCII. Para um grande volume de dados a diferença é ainda mais significativa.

Com base em um sequência das melhores respostas do momento, o algoritmo guloso obtêm uma ótima solução global.

Por, Laybson Plismenn - Integrante do PET Computação

sexta-feira, 15 de julho de 2016

Analise Assintótica de Algorítimos


O mundo ao nosso redor está em constante mudança, principalmente se considerado o lado tecnológico das coisas, isso exige que profissionais das ares que envolvem TI estejam sempre se atualizando. Para que ocorra essa atualização e percepção profissional dos métodos e atividades que se tornaram obsoletos com o passar do tempo, os profissionais contam com um auxilio um tanto quanto especial: A matemática. É ela que torna possível a criação e a avaliação de novos modelos , ponto inicial de processos de desenvolvimento de todas as inovações tecnológicas.

Dentro dessa perspectiva não basta apresentar uma solução para um determinado problema. Na analise de algorítimos é importante apresentar a melhor solução ou até a solução mais viável para o momento e com os recursos disponíveis. Nunca deixando de se analisar os pontos positivos e negativos.

Para criar ou utilizar um algorítimo é importante determinar seu desempenho. Todo algoritmo é projetado e planejado para executar determinadas funções que exigem memoria e tempo de execução. E essa execução pode requerer diferentes algorítimos, sendo assim necessário analisar qual deles é mais eficiente em diversos aspectos.




Analisar um algorítimo significa prever os recursos de que ele necessitará. Em geral, memoria, largura de banda ou hardware são preocupações primordiais. Mas frequentemente é o tempo de computação que se deseja medir. Esse tempo de execução ou custo de utilização pode ser medido por meio de sua execução de um computador real, anotando-se o tempo levando em conta que depende do compilador, do hardware e quantidade de memória principal e secundaria.

Outro detalhe importante é o tamanho da entrada de dados no algorítimo. Para valores pequenos, para qualquer algorítimo, mesmo ineficiente, gastará pouco tempo. O que faz o programador escolher um algorítimo não é o seu desempenho sobre tamanhos de entrada pequenos, mas sim sobre tamanhos de entradas grandes. Logo, sua analise é feita sobre tamanhos de entradas grandes. Analisa-se então comportamento assintótico da função de complexidade de tempos dos algorítimos, sua eficiência assintótica.

Para isso existem os tipos de notação assintótica ou os elementos de analise assintótica. São utilizadas para representar o comportamento assintótico das funções de complexidade de tempo de algorítimos.
Seguindo esta linha de raciocínio temos:

  • Notação O: Utilizada para da um limite superior
  • Notação Ômega: Utilizada para dar um limite inferior
  • Notação Teta: Utilizada para dar um limite "firme"
  • Entre outras derivadas das já mencionadas.

Alguns algorítimos são recursivos, e tem por base a chamada a si próprio, dividindo um problema maior em sub-problemas menores.

Por terem uma estrutura diferenciada das demais estruturas algorítmicas, requerem maneiras um pouco diferentes para calcular-se a notação assintótica, contado com auxilio dos metodos iterativos e mestre.
De modo geral um método de uma classe que chama a si mesma é dita recursiva, e a analise do tempo de execução de um algorítimo recursivo é um pouco diferente dos algorítimos que não possuem recursividade.

Por exemplo, o calculo do fatorial de um numero n, pode ser elaborado por recursividade, e como a solução do problema de tamanho n depende da solução de problemas menores, o tempo de execução também é representado através do tempo de execução do problema para tamanhos menores.

Portanto, desenvolver uma solução nas basta, mas sim a melhor solução utilizando a ferramenta de analise de algorítimos.


Por,
Igor Matheus Diniz - Integrante do PET Computação