Algoritmos - Pilhas e Filas

Estruturas básicas de dados, como pilhas e filas são usadas em uma grande quantidade de aplicações. O uso adequado das estruturas de dados é que faz a diferença entre algoritmos eficientes e e ineficientes.

Pilhas - LIFO (Last In First Out)

Do mesmo contexto de pilha, é um conjunto de objetos que são inseridos e removidos de acordo com o princípio descrito no título (o último a entrar é o primeiro a sair). Objetos podem ser inseridos em uma pilha a qualquer momento, mas apenas o que foi inserido mais recentemente pode ser removido. 

O nome "pilha" é derivado da metáfora de pilha de pratos de um dispositivo automático de entrega de pratos de uma lanchonete. Neste caso, as operações fundamentais envolvem empilhar() e desempilhar() pratos da pilha.

Exemplo prático: Navegadores para Internet armazenam endereços dos locais recentemente visitados em uma pilha. Cada vez que o usuário visita uma nova página, seu endereço é "empilhado" na pilha de endereços. A partir de então, o navegador permite que o usuário "desempilhe" os endereços usando o botão "voltar", retornando a páginas previamente visitadas.

Filas - FIFO (First In First Out)

Consiste em um conjunto de objetos que são inseridos e removidos de acordo com o princípio descrito no título (o primeiro que entra é o primeiro que sai). Ou seja, os elementos podem ser inseridos a qualquer momento, mas apenas o elemento que está a mais tempo na fila pode ser removido. Normalmente dizemos que os elementos entram na fila pelo fim e são removidos pela frente.


Fonte (livro): Projeto de Algoritmos: Fundamentos, análise e exemplos da internet. Michael T. Goodrich e Roberto Tamassia.

Complexidade Computacional

Olá Pessoal,

Como eu tenho uma prova sobre complexidade computacional, o post de hoje será sobre isso.
Servirá, no meu caso, para rever o conteúdo, espero que de alguma forma possa ajudá-los também.  

O material utilizado para a elaboração deste post é de anotações em sala de aula, pesquisas (segue ao final do post alguns links) e livros (também ao final do post contém os dados).

Como sabemos, o algoritmo nada mais é do que uma sequência de passos a serem executados que resolverão um problema. Os exemplo mais clássicos disso são, a receita de bolo e a troca da lâmpada, lembram?

A complexidade do algoritmo está relacionada ao trabalho que ele terá na execução. Por exemplo, quanto aumenta o custo, proporcionalmente ao número de dados?

Como fazer a escolha do algoritmo de acordo com a complexidade computacional?

• Do ponto de vista de DESEMPENHO
• SORT é melhor
• BOOLEAN é pior
• Neste caso, melhor é considerado o que exige menos trabalho.

A complexidade é medida de acordo com a quantidade de dados de entrada (n). Vejamos algumas escalas.

• Melhor: quando são necessárias poucas execuções.
• Médio: quando há a necessidade de probabilidade estatística
• Pior: quando são necessárias muitas execuções.

Complexidade Espacial e Temporal

A complexidade espacial de um algoritmo é o espaço de memória necessário para que ele seja executado até o final. Ou seja, S(n), em que S é o espaço de memória exigido e n o tamanho da entrada.

Já a complexidade temporal é o tempo de execução, ou seja, o tempo que um algoritmo demora para ser executado. Ele pode ser representado por T(n), sendo que T é o tempo de execução em função do tamanho da entrada, representado por n.

Notação de O grande

Na prática, é difícil (senão impossível) prever com rigor o tempo de execução de um algoritmo ou programa. 

• Para obter o tempo é necessário pelo menos: constantes multiplicativas (normalmente estas constantes são tempos de execução de operações atômicas) e parcelas menos significativas  para  os valores grandes de n.
• Identificam-se  as operações dominantes (mais frequentes ou mais demoradas) e determina-se o número de vezes que são executadas (e não o tempo de cada execução, que seria uma constante multiplicativa).

Maiores detalhes da análise assintótica, podem ser acessadas neste link: Ordem de O.

Classes de Complexidade

Conforme visto anteriormente, a complexidade computacional é um ramo da matemática computacional que estuda a eficiência dos algoritmos. 

Para medir esta eficiência, frequentemente utilizamos um tempo teórico que o programa leva para encontrar uma resposta em função dos dados de entrada.

Se a dependência do tempo com relação aos dados da entrada for polinomial, o programa é considerado rápido, pois dado um polinômio p(x) sabemos que |p(x)| cresce para +∞ que |x|. cresce Porém, se a dependência do tempo for exponencial, o programa/algoritmo é considerado lento.

• Complexidade constante: O(1) - Independente do número de entradas tem um número fixo de execuções.
• Complexidade logarítmica: O(n) - A operação é realizada para cada elemento de entrada. Exemplo: Lista.
• Complexidade linear: (n) - Ocorre em algoritmos que o problema é dividido em problemas menores. Exemplo: Árvore, Algoritmo de busca binária.
• Complexidade nLogN: O(nLogn) - Mesmo que o anterior, (ocorre em algoritmos em que o problema é dividido em problemas menores), mas que junta as soluções dos problemas menores para compor outras soluções. Exemplo: Algoritmos de execução externa, como vetores auxiliares, MergeSort.
• Complexidade Quadrática: O(n²) - Processado aos pares.
• Complexidade Cúbica: O(n³) - Mesmo que o anterior (processado aos pares), mas com três laços de repetições.
• Complexidade Exponencial: O(n²) - Este é o pior de todos. Geralmente não são úteis do ponto de vista prático porque envolve muita complexidade. Exemplo: tentar descobrir uma senha na "força bruta", ou seja, combinação de todos os caracteres.

Existem várias classes de complexidade, as mais importantes são P e NP.

A classe de algoritmos P é formada pelos procedimentos para os quais existe um polinômio p(n) que limita o número de passos do processamento se este for iniciado com uma entrada n.

A classe de algoritmos NP é aquela para as quais podemos verificar, em tempo polinomial, se uma solução possível é correta.

Os problemas de P estão contidos nos de classe NP. Se um algoritmo pode ser executado em tempo polinomial e tivermos em mãos um possível candidato S à solução, é possível executar o programa, obter uma solução correta C e comparar com com S, para certificar que S é de fato uma solução, tudo em tempo polinomial. 

Fontes utilizadas para compor este post:

http://www-usr.inf.ufsm.br/~andrezc/ia/complexidade.pdf
http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/NPcompleto2.html

O livro:

Projeto de algoritmos: Fundamentos, análise e exemplos da internet

 Por Michael T. Goodrich,Roberto Tamassia

Como criar índice de ilustrações no Open Office Writer

Bom dia pessoal, tudo bem?

O tutorial de hoje visa sanar uma dúvida que atormenta a maioria das pessoas que precisam gerar índices automáticos. O índice que ensinarei fazer neste tópico é o de Índice de Ilustrações na ferramenta Open Office Writer.

Inicialmente, no documento deverão haver imagens com legendas.

Para inserir imagens, acesse o menu Inserir → Figura → De um Arquivo.
Observação 1: Para executar este passo você deverá ter suas imagens salvas no seu computador.
Observação 2: Para quem é fã do CTRL+C e CTRL+V poderá utilizar também, tornando assim desnecessário salvar as imagens no computador e inseri-las através do menu conforme este passo.

Após inserir todas as imagens, será necessário incluir as legendas nas mesmas.

Para inserir legenda execute os passos a a seguir em todas as imagens do documento (este passo deverá executado imagem por imagem, ou seja, a cada figura, os passos deverão ser repetidos, claro que colocando a legenda pertinente a cada imagem).

Clicar sobre a imagem com o botão direito do mouse → Legenda.

Descreva a legenda da figura. No exemplo que estou utilizando colocarei: Agnes do Filme Meu Malvado Favorito. (Veja no passo 1)

Na opção Categoria, selecione Ilustração (caso fosse uma tabela, ou outros, deveria ser selecionada a opção pertinente). (Veja no passo 2)

Em seguida clique no botão OK. (Veja no passo 3)

Veja como ficará a legenda na figura:

Execute estes passos (de inserir legenda) em todas as figuras de seu documento.
Após inserir as legendas nas imagens, deverá ser criado o índice conforme passos a seguir.

Acesse uma página em branco (de preferência no início do seu documento e após a capa, aqui não estou levando em consideração as normas, que solicitam: capa, contra capa, introdução e etc).

Acesse o menu Inserir → Índices e sumários → Índices e sumários.

Será visualizada a tela para criar o índice.
Na opção Título, coloque qual deverá ser o título do seu índice. A ferramenta Open Office Writer oferece uma opção, mas você poderá alterá-la. (1)
Na opção Tipo deverá ser selecionado qual o tipo de índice a ser criado. Neste caso faremos o de ilustrações, mas poderia ser de gráficos, tabelas, entre outros. (2)
Para gerar o índice, clicar no botão OK. (3).

Veja como ficou o índice de ilustrações:

Caso em algum momento foi necessário colocar uma figura a mais no documento, NÃO SE PREOCUPE!
Você poderá tranquilamente incluir a figura conforme os primeiros passos e na sequência colocar a sua legenda (a ferramente Open Office Writer tratará da numeração da figura para você, então pode fazer isso sem maiores preocupações).

Após incluir a figura faltante e sua legenda será necessário que ela seja visualizada no índice junto com as demais, certo?
Para isso clique com o botão direito do mouse sobre o índice e selecione a opção Atualizar Índice/Sumário.

O seu índice será atualizado por inteiro, ou seja, aparecerá a legenda da figura incluída com a numeração correta da mesma e se houve alteração de páginas, esta também será alterada automaticamente.

Em caso de dúvidas, não hesite em nos enviar uma mensagem.

Um abraço e ótima semana.

Origem da palavra informática

Em 1957, o cientista da computação alemão Karl Steinbuch publicou um jornal chamado Informatica: Informationsverarbeitung ("Informática: processamento de informação").

A palavra portuguesa é derivada do francês informatique, vocábulo criado por Philippe Dreyfus, em 1962, a partir do radical do verbo francês informer, por analogia com mathématique, électronique, etc.

Em português, há profissionais da área que também consideram que a palavra informática seja formada pela junção das palavras informação + automática. Pode dizer-se que informática é a ciência que estuda o processamento automático da informação por meio do Computador.

Por que devo aprender assuntos relacionados a informática?

Se perguntarmos para um grupo de pessoas com faixa etária de 12 a 30 anos de idade se eles sabem usar um computador, a maioria responderá com certa convicção que sim, sabem usar um computador. Mas se perguntarmos quantos deles sabem utilizar os recursos do computador de forma que consigam fazer algo produtivo, tanto para o uso pessoal quanto no trabalho, a resposta já não será tão rápida e tampouco afirmativa.

Em geral as pessoas estão muito acomodadas com o conhecimento que têm quando o assunto é informática. 

Muitas delas acham que saber fazer pesquisas simples em sites de busca, saber acessar mais de uma rede social, editar um texto simples e saber os comandos CTRL+C e CTRL+V é o suficiente para se dizer um “expert” em informática.

A maioria das vagas de emprego que encontramos exigem que o candidato tenha pelo menos informática básica. É aí que mora o problema: a definição que as pessoas têm de informática básica. Muitos acham que saber ligar o computador e fazer uma das atividades listadas a cima é o suficiente. Hoje é difícil encontrar entrevistados que afirmam com certeza que sabem editar um texto, fazer uma lista de contatos, enviar um e-mail com anexo, fazer uma apresentação de slides, e até mesmo encontrar candidatos que saibam digitar sem erros está sendo difícil em decorrência do uso exagerado da linguagem abreviada e confusa muito utilizadas em bate papo e nas redes sociais.

Saber o usar o computador não é um diferencial em um currículo e sim uma obrigação, não só no ponto de vista profissional como no pessoal. Diariamente nos deparamos com situações em que se soubéssemos usar bem os recursos do computador pouparíamos tempo e dinheiro. 

Um exemplo clássico é a compra pela internet, é sabido que a maioria dos produtos vendidos em lojas de varejo é encontrado em lojas virtuais por um preço mais acessível e com maior facilidade de pagamento, e além de economizar dinheiro o indivíduo não precisa sair de casa, enfrentar filas e trânsito. Ainda temos os serviços de internet banking, compra de passagens, mapas, cadastro de curriculum, cursos de diversas áreas gratuitos e muito mais.

O problema é que usuários que se dizem saber usar o computador não sabem da existência dessas possibilidades, e isso pode ser creditado ao compulsivo e limitado uso do computador para fazer atividades que na maioria das vezes não trazem nenhum beneficio intelectual ao usuário, servindo apenas como entretenimento. Um exemplo disso são as redes sociais, onde jovens, adultos e crianças gastam horas e horas na frentegn do monitor vendo “a mesma tela sempre” e não dedicam sequer quinze minutos desse tempo para ler noticias, ler sobre um assunto em pauta na mídia e até mesmo desenvolver suas habilidades como pessoa e profissional.

Um computador conectado a internet nos leva a infinitas possibilidades, é como se todo o conhecimento do mundo estivesse disponível na ponta de nossos dedos: basta apenas acessar e aproveitar. 

Isso só depende da dedicação e da força de vontade que cada um tem em adquirir conhecimento gratuito, sem pagar a ninguém.