Interação e interatividade

Interação e interatividade são assuntos em alto nesse momento em que a internet oferece a cada dia mais ferramentas para tarefas cotidianas. Na educação não é diferente, hoje a educação a distância já uma realidade no Brasil, e para que a educação a distância seja proveitosa para o aluno precisa haver interação e interatividade.

De acordo com o dicionário Aurélio a palavra “interação” significa “ uma ação que se exerce mutuamente entre duas ou mais coisas, ou duas ou mais pessoas”, quanto a palavra “Interatividade” é definida como “capacidade (de um equipamento ou sistema de comunicação ou sistema de computação, etc.) de interagir ou permitir a interação”. O mesmo dicionário afirma que o termo “interatividade” está relacionado com o termo “interativos” que é a capacidade de um “recurso, meio, ou processo de comunicação permitir ao receptor interagir ativamente com o emissor”.

Apesar de existir divergência entre diferentes grupos de autores sobre a equivalência entre o termo Interação e Interatividade. É importante ressaltar que a Interação é inerente aos seres humanos e ocorre quase sempre quando duas ou mais pessoas se comunicam. Já a Interatividade tem relação com as Tecnologias de Informação e Comunicação (TICs), ocorre quando duas ou mais pessoas interagem tendo como mediador alguma interface tecnológica.

Segundo Belloni (2008), a interação e quando existe uma ação recíproca entre dois ou mais atores onde ocorre intersubjetividade, em outras palavras ele fala que é o encontro de duas pessoas que pode ser direta ou indireta, o autor Primo (2005) complementa falando que a interação não deve ser vista como uma característica do meio, e sim como um processo que os integrantes desenvolvem.

Para Lemos (2000), interatividade é um caso específico de interação, a interatividade digital, compreendida como um tipo de relação tecno-social, ou seja, como um diálogo entre homem e máquina, através de interfaces gráficas, em tempo real.

Recursos Educacionais

Um Recurso Educacional Digital é, na prática, um arquivo digital utilizado como ferramenta de ensino para apoiar o aprendizado.

Ao invés de indicar o produto final como um arquivo digital, já que este é um termo do domínio da informática, o termo recurso digital se torna mais adequado. O termo educacional, associado a expressão, indica sua finalidade.

No domínio do uso de tecnologias digitais na educação, existem diversos outros termos que indicam o mesmo tipo de recurso, porém, com nomes diferentes. Os novos nomes são adaptados para indicar, de forma mais precisa, a finalidade a que se destinam, podendo indicar funcionalidades dirigidas ao aprendizado, ao ensino ou a educação.

Dependendo da metodologia utilizada na aplicação, um mesmo recurso digital pode ser classificado de diversas formas, por exemplo, pode ser classificado como um Objeto de Aprendizagem Digital ou Material Didático Interativo.

Do ponto de vista da tecnologia, um recurso digital é um arquivo digital, isso significa que, pode ser um arquivo de imagem, como por exemplo um vídeo, uma foto, uma ilustração, uma animação; ou um arquivo de áudio, como por exemplo uma música, uma gravação, um som, um toque, um áudio-livro; ou um tipo específico de documento, como por exemplo, um texto, uma planilha, uma apresentação; ou, ainda, um tipo específico de arquivo associado a uma aplicação especializada, como por exemplo, arquivos de CAD, de aplicativos de simulação matemática, física, anatomia, etc.

Um excelente recurso educacional aberto na área da informática é o codecademy, que   é um site que possuí uma plataforma interativa online e oferece aulas gratuitas de codificação em linguagens de programação como jQuery, Javascript, Python, Ruby, PHP, JAVA bem como as linguagens de marcação, incluindo HTML e CSS. O serviço funciona de maneira que os usuários progridam nas lições, avançando com mais códigos progressivamente na medida que se aprende.

Em janeiro de 2014, o site teve mais de 24 milhões de usuários que completaram mais de 100 milhões de exercícios. A Codecademy recebeu diversas avaliações positivas de blogs e sites, incluindo o New York Times e a TechCrunch. Cada indivíduo que entra tem seu próprio perfil. Para motivar os usuários a participar, o site oferece feedback e emblemas ao completar exercícios. Há também glossários HTML e CSS disponíveis em cada aula. Além disso, o site permite qualquer pessoa criar e publicar um novo curso usando a ferramenta Criador de Curso. Codecademy também disponibiliza um fórum onde entusiastas, programadores iniciantes e avançados possam interagir e ajudar uns aos outros. Para alguns cursos existem as chamadas 'sandboxes' onde os usuários podem testar seu código.

Um recurso educacional de estudo de línguas estrangeira é o Duolingo, o aplicativo promete que seus usuários irão aprender outro idioma jogando. Duolingo é um site web de ensino de idiomas gratuito que utiliza uma plataforma crowdsourcing de tradução de textos. O serviço funciona de maneira que os usuários progridam nas lições ao mesmo tempo que traduzem conteúdo real da internet. O Duolingo está disponível na Web, iOS, Android e Windows Phone. Em 11 de novembro de 2011 sua empresa criadora lançou a versão beta privada, acumulando uma lista de espera composta por mais de 300 mil usuários, sendo posteriormente lançada ao público em geral no dia 19 de junho de 2012. Em 2016 o Duolingo possui cerca de 120 milhões de usuários cadastrados.

Atividade Didática

Atividade desenvolvida para alunos de programação orientada objeto de um curso e informática.

                O objetivo geral é desenvolver o trabalho em equipe no desenvolvimento de softwares, que é o que é usado no mercado de trabalho.

                Objetivos específicos, será conhecer nova linguagem de programação assim como ferramentas de particionamento de código.

                A proposta será dividir a turma em grupos simulando uma equipe de desenvolvimento, onde terá um grupo que serão os analistas de sistemas, um grupo de DBAs, uma de Designer, 3 esquipes de desenvolvimento, uma esquipe de testes.

                A equipe de analistas deve desenvolver o projeto do software e realizar a documentação, com a documentação a esquipe de Disigner e os DBAs começam a desenvolver o layout e o banco de dados do sistema, baseados pela documentação, também em posse da documentação os programadores devem se dividir e desenvolver o software com o auxílio de uma ferramenta de particionamento de código, após isso a equipe de teste deve testar o software, caso seja encontrados problemas deve-se se voltar nesse ciclo e resolver os problemas.

                Coma a atividade deve ser extensa todos os alunos devem se envolver em todas as etapas do desenvolvimento do software.

Conclusão

                A interação interpessoal ou interação social como uma relação de interdependência entre duas ou mais pessoas, onde a ação de cada uma depende da ação do outro (falar… ouvir… argumentar). Numa interação interpessoal (que caracteriza a comunicação humana), temos três fatores: os participantes, a relação em si e o contexto.

Atividades planejadas levando os termos “interação” e “interatividade” em consideração, fazem com que o processo de ensino aprendizagem seja mais interessante para o aluno, além de menos cansativos. Pois o padrão de alunos vem mudando a forma de se ensinar.

Referência

BELLONI, M. L. Educação a distância. 5o ed. Campinas, SP: Autores Associados, 2008.

BELLONI, Maria Luiza. Ensaio sobre a Educação a Distância no Brasil.

Educação & Sociedade, ano XXIII, no 78, Abril/2002.

LEMOS André. Anjos interativos e retribalização do mundo: sobre interatividade e interfaces digitais. Disponível em: http://www.facom.ufba.br/ciberpesquisa/lemos/interac.html Acesso em: 24/09/17.

LÉVY, Pierre. Cibercultura. São Paulo: Editora 34, 1999.

PRIMO, A. Enfoques e desfoques no estudo da interação mediada por computador. 2005.

NoSQL Databases

NoSQL Databases 

NoSQL é um padrão de armazenamento de dados alternativo ao SQL, oferecendo uma robustez e escalabilidade melhores. Os bancos de dados NoSQL não podem exigir esquemas de tabela fixa e, geralmente, não suportam instruções e operações de junção SQL e  não possuem propriedades ACID.

NoSQL tem diferentes sistemas de armazenamento que tenta suprir necessidades onde o o sistema de banco de dados relacional e ineficaz, o NoSQL tem características interessantes como alta performance, escalabilidade, replicação, suporte a dados estruturados, grafos e sub-colunas.

O NoSQL tem uma grande facilidade na distribuição horizontal, ou seja, mais dados, mais servidores, não necessariamente de alta performance. Um grande utilizador desse conceito é o Google, que usa computadores de pequeno e médio porte para a distribuição dos dados. Essa forma de utilização é muito mais eficiente e econômica. Além disso, os bancos de dados NoSQL são muito tolerantes a erros.

No caso dos bancos NoSQL, toda a informação necessária estará agrupada no mesmo registro, ou seja, em vez de você ter o relacionamento entre várias tabelas para formar uma informação, ela estará em sua totalidade no mesmo registro.

História 

Carlo Strozzi em 1998 usou pela primeira vez o termo NoSQL como o nome de um banco de dados relacional de código aberto que não possuía uma interface SQL. 

Com o aumento de dados gerados a partir da popularização da internet diversos novos dados foram surgindo e tratá-los foi se tornando gradualmente mais complexo e sua manutenção cada vez mais cara.

Em 2006, o artigo: BigTable: A Distributed Storage System for Structured Data, publicado pelo Google em 2006, traz novamente à tona o conceito NoSQL.

Em 2009 por um funcionário do Rackspace, Eric Evans, quando Johan Oskarsson da Last.fm queria organizar um evento para discutir bancos de dados open source distribuídos.

NORMAS E MODELOS DE QUALIDADE DE SOFTWARE: CMM, CMMI e TMMI

1. INTRODUÇÃO

Após décadas de incontroláveis promessas sobre como aumentar a produtividade e a qualidade do software, as organizações chegaram à conclusão que o problemas principais eram a incapacidade e a inexperiência para gerenciar os processos de desenvolvimento de software. Em muitas organizações, os projetos não cumpriam os prazos planejados e os custos orçados, afetando os benefícios que o projeto traria. Como resposta para esse ambiente caótico, foram desenvolvidos normas e modelos de qualidade de software, como o propósito de melhorar o desenvolvimento de aplicações em organizações que trabalham com tais tecnologias.

Esse trabalho tem como objetivo mostrar a importância da adoção dessas normas e padrões de software na obtenção da qualidade dos processos e certificações de produtos. Além disso, será considerado as necessidades dos clientes, a qualidade do produto de software, a qualidade do processo de desenvolvimento e o nível de maturidade da organização. Será tomado com destaque os modelos CMM, TMM e TMMI.

2. HISTÓRICO

            A Crise do Software foi termo utilizado nos anos de 1970 para expressar as dificuldades do desenvolvimento de software frente ao rápido crescimento da demanda do mesmo, da complexidade dos problemas a serem resolvidos e da inexistência de técnicas estabelecidas para o desenvolvimento de sistemas que funcionassem adequadamente ou pudessem ser validados. Projetos estourando o orçamento e o prazo, a baixa qualidade e o não cumprimento dos requisitos desejados eram problemas frequente dos sistemas encomendados pelo DoD - Departamento de Defesa dos Estados Unidos.

            O modelo CMM surgiu durante a década de 1980, produzido pelo SEI (Instituto de Engenharia de Software) da Universidade Carnegie Mellon, em Pittsburgh, EUA, por um grupo de profissionais de software. Foi instituído como um modelo para avaliação de riscos na contratação de empresas de software pelo Departamento de Defesa dos Estados Unidos que desejava ser capaz de avaliar os processos de desenvolvimento utilizados pelas empresas que concorriam em licitações como indicação da previsibilidade da qualidade, custos e prazos nos projetos contratados. Em junho de 1987, ocorreu a liberação de uma breve descrição do modelo de maturidade de processo de software. Em setembro do mesmo ano, foi lançada uma versão preliminar do questionário de maturidade. Em agosto de 1991, foi entregue a versão 1.0 do SW-CMM, e quase dois anos depois, em fevereiro de 1993 foi divulgada a versão 1.1.

Com o sucesso do SW-CMM, outros modelos semelhantes foram criados para demais áreas, como por exemplo, Gestão de Recursos Humanos (People-CMM), Aquisição de Software (SA-CMM) e Engenharia de Sistemas (SE-CMM). Entretanto, esses diversos modelos apresentavam estruturas, termos e formatos diferentes, dificultando sua aplicação conjunta. Como consequência dessa proliferação de modelos e padrões em diversas áreas, foi criado o CMMI, com a finalidade de integrar os diversos modelos CMM. Em agosto de 2000, foi criada a versão 1.0 e em novembro de 2010, a versão 1.3.

O TMMI nada mais é do que o complemento do CMMI. Seu objetivo deve ser usado de maneira semelhante ao CMM, ou seja, fornecer um quadro para a avaliação da maturidade dos processos de uma organização, e assim, proporcionar melhorias da maturidade. O TMMI veio da necessidade de se ter um processo evolutivo e bem definido de testes para as empresas já possuidoras do certificado CMMI (nível 2 ao 5), focando o objetivo dos testes na prevenção de defeitos e não na detecção deles.

RIC-Identidade única

Prometido há muito tempo (a lei é de 1997) a identidade única aqui no Brasil, que seria um único documento para substituir carteira de identidade, unificar o CPF e titulo de eleitor e o numero de identificação do social do trabalhador, tudo em um cartão de plástico com um chip um modelo contra a fraude, o custo seria de 40 reais e ate um cronograma de implementação do RIC foi anunciado. Esse projeto esta sempre sendo rediscutido, mudado e adaptado, mas nunca chega em um consenso, já deveria ter sido implementado em 7 cidades no Brasil inclusive em Brasilia chegando a um total de 100 mil brasileiro com usando RIC, mas ainda nada foi colocado em pratica.

Em Portugal existe o Cartão de cidadão que sem limite mínimo de idade, começou a ser implementado em forma de experimental em meados de 2006-2007, este cartão substitui não só o bilhete de identidade (ainda em vigor), como também outros documentos, nomeadamente, o cartão de beneficiário da Segurança Social, o cartão de utente do Serviço Nacional de Saúde, o cartão de contribuinte e o cartão de eleitor. O principal objetivo era reduzir o número de cartões de identificação necessários para o cidadão se apresentar perante as instituições do Estado. Os cartões contem um chip que segundo o governo português, permite garantir a privacidade dos dados, onde os dados médicos não poderiam ser lidos por funcionários das finanças. O Cartão de cidadão teve contestações, como seu preço que seria em torno de 15 euros (mais barato que o brasileiro), também foi levantado à integridade dos dados contida nos catões. No modelo de Portugal os números de identificação do cidadão continuarão a ser os antigos números do Bilhete de Identidade, Segurança Social, Sistema Nacional de Saúde e Finanças, e continua a não haver cruzamento direto de dados.

A identidade única vai trazer inúmeros benefícios como alta produtividade, mais prevenção ao crime, melhora no atendimento médico, diversão interativa, conveniências burocráticas, dificuldades de falsidade ideológicas, diminuição de documentos oficiais, entre outras. A identidade única o RIC impedira que uma pessoa possa ser condenada por tráfico no Estado de São Paulo, fugir de lá, chegar ao Estado de Mato Grosso, conseguir uma nova identidade e ficar trabalhando ali por muito tempo ou cometendo novos delitos com identidade falsa, dificultando o trabalho da polícia. Com a adoção da identidade única, isso vai ser praticamente impossível. Por isso a importância do Projeto AFIS no combate também ao tráfico de drogas. Mas o ponto forte do RIC e ter todos os documentos em um único documento.

Por outro lado o RIC tem seus pontos fracos como menos e menos privacidade. Quando colocam em uso essas tecnologias, governos e companhias privadas repetem à exaustão o belo e convincente discurso sobre os benefícios que elas trazem. O ponto chave é que em um único cartão/documento estará armazenados muitos dados e que esses dados serão controlados pelo governo assim podendo rastrear todos que possuem a identidade única. A The Economis defende que "A maioria das pessoas concorda em dar alguma informação sobre elas mesmas para poder votar, trabalhar, comprar, fechar um negócio, sociabilizar ou mesmo emprestar um livro de uma biblioteca. Mas exercer o controle sobre quem sabe o que sobre sua vida também tem sido uma característica essencial de uma sociedade civilizada” e de acordo com a Privacy International, uma organização não-governamental com representantes em 40 países, "a existência do histórico de vida de pessoas em centenas de bancos de dados, necessariamente não relacionados, é uma condição importante de proteção da privacidade. Mas, quando se reúnem esses dados em uma rede interligada, você torna essa proteção absolutamente vulnerável".

O fato que o RIC tem um preço para ser pago por todos os brasileiros onde cada cartão custa 40 reais, tem pontos positivos que não nos faz entender por que ainda não foi implementando, mas olhando friamente o projeto se vê muitas falhas e um grande controle de dados pelo governo, o projeto continua sendo discutido e ajustado, a implementação do RIC não será fácil de chegar a um meio termo onde somente haja benefícios e os pontos fracos sejam eliminados.  Opinião que corrobora um relatório produzido há dois anos pelo governo britânico: "Para que um esquema de identidade única funcione, será necessário criar um banco de dados nacional. Isso significa dizer que os vários departamentos do governo poderão colher, transferir e guardar informações sobre o cidadão de uma forma muito mais fácil do que hoje. O que aumenta muito o risco de que a informação seja usada fora do contexto em que foi colhida. Decisões serão tomadas sobre você com base em dados imprecisos, irrelevantes ou incompletos. E, uma vez que o erro é cometido, ele pode se repetir várias vezes", alerta o relatório, invalidando a argumentação de que, se você é inocente, não tem nada a temer.

Algoritmo do banqueiro

O algoritmo foi desenvolvido por Edsger Dijkstra em 1965. É um algoritmo de alocação de recursos com prevenção de impasses que testa a segurança pela simulação da alocação do máximo pré-determinado possível de montantes de todos os recursos computacionais, logo em seguida faz uma verificação de estados-seguros para testar a possibilidade de condições de impasse para todas as outras atividades pendentes, antes de decidir se a alocação deve prosseguir.

Algoritmo do banqueiro com múltiplos recursos

O algoritmo do banqueiro pode ser generalizado para tratar múltiplos recursos. A figura abaixo mostra como ele funciona.

Na figura 1 vemos duas matrizes. A primeira, do lado esquerdo, mostra quanto de cada recurso atualmente está alocado para cada um dos cinco processos. A matriz do lado direito mostra de quantos recursos cada processo ainda precisa para completar sua execução.

Os três vetores à direita da figura mostram:

·         E recursos existentes.

·         P recursos alocados.

·         A recursos disponíveis.

Grafos- Caminho mínimo

Introdução

A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal são empregadas estruturas chamadas de grafos, G(V,A), onde V é um conjunto não vazio de objetos denominados vértices e A é um conjunto de pares não ordenados de V, chamado arestas.

Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio e vértices e/ou arestas podem ter um peso (numérico) associado. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um grafo direcionado, grafo orientado ou digrafo. Um grafo com um único vértice e sem arestas é conhecido como o grafo trivial.

Estruturas que podem ser representadas por grafos estão em toda parte e muitos problemas de interesse prático podem ser formulados como questões sobre certos grafos. Por exemplo, a estrutura de links da Wikipedia pode ser representada por um dígrafo: os vértices são os artigos da Wikipedia e existe uma aresta do artigo A para o artigo B se e somente se A contém um link para B. Dígrafos são também usados para representar máquinas de estado finito. O desenvolvimento de algoritmos para manipular grafos é um importante tema da ciência da computação.

Caminho mínimo

Na teoria de grafos, o problema do caminho mínimo consiste na minimização do custo de travessia de um grafo entre dois nós (ou vértices); custo este dado pela soma dos pesos de cada aresta percorrida.

Os algoritmos especializados em solucionar o problema do caminho mínimo são eventualmente chamados de algoritmos de busca de caminhos. Entre os algoritmos dessa classe, os mais conhecidos são:

•         Algoritmo de Dijkstra
•          Algoritmo de Bellman-Ford
•          Algoritmo A*
•          Algoritmo de Johnson
•          Algoritmo de Prim

Algoritmo de Dijkstra

O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger Dijkstra em 1956 e publicado em 19591 2 , soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo, em tempo computacional O([m+n]log n) onde m é o número de arestas e n é o número de vértices. O algoritmo que serve para resolver o mesmo problema em um grafo com pesos negativos é o algoritmo de Bellman-Ford, que possui maior tempo de execução que o Dijkstra.

O algoritmo de Dijkstra assemelha-se ao BFS, mas é um algoritmo guloso, ou seja, toma a decisão que parece ótima no momento. Para a teoria dos grafos uma "estratégia gulosa" é conveniente já que sendo P um menor caminho entre 2 vértices U e V, todo sub-caminho de P é um menor caminho entre 2 vértices pertencentes ao caminho P, desta forma construímos os melhores caminhos dos vértices alcançáveis pelo vértice inicial determinando todos os melhores caminhos intermediários. Nota: diz-se 'um menor caminho' pois caso existam 2 'menores caminhos' apenas um será descoberto.

O algoritmo considera um conjunto S de menores caminhos, iniciado com um vértice inicial I. A cada passo do algoritmo busca-se nas adjacências dos vértices pertencentes a S aquele vértice com menor distância relativa a I e adiciona-o a S e, então, repetindo os passos até que todos os vértices alcançáveis por I estejam em S. Arestas que ligam vértices já pertencentes a S são desconsideradas.

O algoritmo de Dijkstra não consegue encontrar o menor caminho em um grafo com pesos negativos. Para esse propósito, pode-se usar o algoritmo de Floyd-Warshall, que consegue descobrir a menor distância entre todos os pares de vértices de qualquer grafo sem ciclos com peso negativo em uma complexidade de tempo O(V³). Se o problema não exigir o cálculo da distância entre todos os pares de vértices ou se existirem ciclos com peso negativo, pode-se aplicar o algoritmo de Bellman-Ford, com complexidade de tempo O(V*E). Em uma árvore, é possível encontrar a distância entre um vértice inicial e todos os outros vértices em tempo O(V+E), utilizando busca em profundidade (também conhecida como DFS). Em um grafo cujas arestas têm todas o mesmo peso, pode-se encontrar a distância entre um vértice inicial e todos os outros vértices, para um grafo qualquer, em O(V+E), utilizando busca em largura (também conhecida como BFS). O processo utilizado no algoritmo de Dijkstra é bastante similar ao processo usado no algoritmo de Prim. O propósito deste último, entretanto, é encontrar a árvore geradora mínima que conecta todos os nós de um grafo.

Algoritmo de Bellman-Ford

O Algoritmo de Bellman-Ford é um algoritmo de busca de caminho mínimo em um dígrafo ponderado, ou seja, cujas arestas têm peso, inclusive negativo. O Algoritmo de Dijkstra resolve o mesmo problema, em um tempo menor, porém exige que todas as arestas tenham pesos positivos. Portanto, o algoritmo de Bellman-Ford é normalmente usado apenas quando existem arestas de peso negativo.

Algoritmo A*

Algoritmo A* é um algoritmo para Busca de Caminho. Ele busca o caminho em um grafo de um vértice inicial até um vértice final. Ele é a combinação de aproximações heurísticas como do algoritmo Best-first Search e da formalidade do Algoritmo de Dijkstra.

O algoritmo foi descrito pela primeira vez em 1968 por Peter Hart, Nils Nilsson, e Bertram Raphael. Na publicação deles, ele foi chamado de algoritmo A; usando este algoritmo com uma heurística apropriada atinge-se um comportamento ótimo, e passou a ser conhecido por A*.

Sua aplicação vai desde aplicativos para encontrar rotas de deslocamento entre localidades a resolução de problemas, como a resolução de um quebra-cabeças. Ele é muito usado em jogos.

Algoritmo de  Johnson

Algoritmo de Johnson é uma forma de encontrar o menor caminho entre dois pontos. Ele permite que algumas bordas tenham número negativo, mas ciclos negativos não devem existir. Este algoritmo trabalha com base no Algoritmo de Bellman-Ford, para computar uma transformação de um grafo de entrada, que remove todos os pesos negativos, permitindo o uso do algoritmo de Dijkstra no grafo transformado. Recebe esse nome em homenagem a Donald B. Johnson, o primeiro a descrevê-lo, em 1977.

Algoritmo de Plim

O algoritmo de Prim é um algoritmo guloso (greedy algorithm) empregado para encontrar uma árvore geradora mínima (minimal spanning tree) num grafo conectado, valorado e não direcionado. Isso significa que o algoritmo encontra um subgrafo do grafo original no qual a soma total das arestas é minimizada e todos os vértices estão interligados. O algoritmo foi desenvolvido em 1930 pelo matemático Vojtěch Jarník e depois pelo cientista da computação Robert Clay Prim em 1957 e redescoberto por Edsger Dijkstra em 1959.

Outros algoritmos conhecidos para encontrar árvores geradoras mínimas são o algoritmo de Kruskal e algoritmo de Boruvka. No entanto estes algoritmos podem ser empregados em grafos desconexos, enquanto o algoritmo de Prim precisa de um grafo conexo.

O Problema a ser resolvido

Imagine que uma transportadora decidiu alavancar as suas entregas e fez uma promoção de 50% em todas as entregas da cidade A até a cidade F. Para que ela não tenha prejuízo ela terá sempre que percorrer o menor caminho entre as cidades. Como fazer isso?

·         Problema:

o   Obter Caminhos interligando Vértices de um Grafo, cujo comprimento (Custo) seja Mínimo.

·         Implementações:

o   Algoritmo de Dijkstra

·         Aplicação:

o   Redes de Computadores (Percurso entre Roteadores)

o   Tráfego Urbano.

o   Sistemas Rodoviários, Ferroviários e Aéreos,

o   Importante para vários outros problemas

Será resolvido com o algoritmo de Dijkstra melhor algoritmo conhecido aplicado a grafos com pesos não negativos. Passo-a-passo a seguir:

•          Encontra os caminhos mais curtos de acordo com a distância a uma dada fonte

•           Primeiro,encontra o caminho mais curto da fonte ao vértice mais próximo e assim por diante.

•           Em geral, antes da i-ésima iteração iniciar, o algoritmo já encontrou os menores caminhos para os outros i-1 vértices próximos da fonte

•          Estes vértices, a fonte, e as arestas dos caminhos mais curtos formam uma subárvore Ti.

•           Como todos os pesos das arestas são não negativos, o vértice seguinte mais próximo da fonte pode ser encontrado dentre os vértices adjacentes aos vértices de Ti.

•           Para identificar o i-ésimo vértice mais próximo, o algoritmo calcula, para cada vértice candidato u, a soma da distância ao vértice da árvore v mais próximo e o comprimento dv do caminho mais curto da fonte à v e então seleciona o vértice cuja soma seja a menor.

•            Cada vértice possui duas etiquetas:

•          Um valor numérico d que indica o comprimento do caminho mais curto da fonte ao vértice encontrado pelo algoritmo até o momento. Quando um vértice for adicionado a árvore, d indica o comprimento do caminho mais curto da fonte até o vértice.

•          A outra etiqueta indica o nome do próximo ao último vértice neste caminho, i.e., o pai do vértice na árvore sendo construída.

•          Com estas etiquetas, encontrar o vértice mais próximo u* seguinte torna-se uma tarefa simples que consiste em encontrar o vértice candidato com o menor valor de d.

•           Após identificado o vértice u* a ser adicionado a árvore, as seguintes operações devem ser realizadas:

•           Mover o vértice u* do vértice candidato para o conjunto dos vértices da árvore

•          Para cada vértice candidato remanescente u que estiver conectado a u* por uma aresta de pesos(u*,u) tal que du* + w(u*,u) < dw, atualize as etiquetas de u por u* e du* + w(u*,u) respectivamente.

•           Dijkstra compara comprimento de caminhos

•          Algoritmo de Dijkstra

•          topologia da rede, custos dos enlaces conhecidos por todos os nós

•          realizado através de “difusão do estado dos enlaces”

•          todos os nós têm mesma info.

•          calcula caminhos de menor custo de um nó (“origem”) para todos os demais

•          gera tabela de rotas para aquele nó

•          iterativo: depois de k iterações, sabemos menor custo p/ k destinos

•          Notação:

•          c(i,j): custo do enlace do nó i ao nó j. custo é infinito se não forem vizinhos diretos

•          D(V): valor corrente do custo do caminho da origem ao destino V

•          p(V): nó antecessor no caminho da origem ao nó V

•          N: conjunto de nós cujo caminho de menor custo já foi determinado

Resumo:

1         Inicialização:

2         N = {A}

3         para todos os nós V

4         se V for adjacente ao nó A

5         então D(V) = c(A,V)

6         senão D(V) = infinito

7         Repete

8         determina W não contido em N tal que D(W) é o mínimo

9         adiciona W ao conjunto N

10     atualiza D(V) para todo V adjacente ao nó W e ainda não em N:

11     D(V) = min( D(V), D(W) + c(W,V) )

12     /* novo custo ao nó V ou é o custo velho a V ou o custo do

13     menor caminho ao nó W, mais o custo de W a V */

14     até que todos nós estejam em N

A eficiência do algoritmo de Dijkstra depende das estruturas de dados usadas na implementação da fila de prioridade e do grafo.

Este algoritmo parte de uma estimativa inicial para o custo mínimo e vai sucessivamente ajustando esta estimativa. Ele considera que um vértice estará fechado quando já tiver sido obtido um caminho de custo mínimo do vértice tomado como raiz da busca até ele. Caso contrário ele dito estar aberto.

Referencia

•          CORMEN,T.H.; LEISERSON, C.E. and RIVEST, R.L. Introduction to Algorithms. Cambridge: MIT Press, 1996.

•          Algoritmo de Dijkstra Disponível em: <http://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra>  acesso em: 10/12/2013.

•          Algoritmo de Dijkstra para cálculo do Caminho de Custo Mínimo Disponível em: < http://www.inf.ufsc.br/grafos/temas/custo-minimo/dijkstra.html> acesso em: 11/12/2013.

ENTENDA OS BIPS DA SUA BIOS

Antonio Vilhena - 21/2/2002

Muitas vezes quando ligamos o computador, damos de cara com problemas e só recebemos de informação os apitos da BIOS (chamados de BIOS Tone POST Codes)! Se não temos à mão uma tabela com o significado dos apitos, o trabalho se torna um exercício de adivinhação que além de tomar muito tempo, pode acabar resultando em gastos de dinheiro trocando peças desnecessárias, ou para os mais irritadiços, jogar o computador pela janela ou dar uns pontapés para ver se funciona! Pensando nisso, conseguimos umas tabelas dos famosos apitos, para que você possa ter alguma dica com que iniciar a solução do problema! Maiores informações vocês poderão conseguir nos sites dos produtores de BIOS e das PLACAS-MÃE.

Nenhum vídeo funcional
Nenhum vídeo Monocromático funcional
Nenhum vídeo CGA funcional
1-1-3 CMOS write/read
1-1-4 ROM BIOS checksum
1-2-1 Timer do Sistema
1-2-2 inicialização do DMA
1-2-3 registro da página de DMA (write/read)
1-3-1 verificação da atualização da memória RAM
1-3-3 chip dos 64K RAM iniciais ou linha de dados
1-3-4 lógica odd/even dos 64K RAM iniciais
1-4-1 endereço de linha dos 64K RAM iniciais
1-4-2 falha de paridade nos 64K RAM iniciais
2-1-1 Bit 0, 64K RAM iniciais
2-1-2 Bit 1, 64K RAM iniciais
2-1-3 Bit 2, 64K RAM iniciais
2-1-4 Bit 3, 64K RAM iniciais
2-2-1 Bit 4, 64K RAM iniciais
2-2-2 Bit 5, 64K RAM iniciais
2-2-3 Bit 6, 64K RAM iniciais
2-2-4 Bit 7, 64K RAM iniciais
2-3-1 Bit 8, 64K RAM iniciais
2-3-2 Bit 9, 64K RAM iniciais
2-3-3 Bit 10, 64K RAM iniciais
2-3-4 Bit 11, 64K RAM iniciais
2-4-1 Bit 12, 64K RAM iniciais
2-4-2 Bit 13, 64K RAM iniciais
2-4-3 Bit 14, 64K RAM iniciais
2-4-4 Bit 15, 64K RAM iniciais
3-1-1 registro de DMA Slave
3-1-2 registro de DMA Master
3-1-3 Registrador da interrupção Master
3-1-4 Registrador da interrupção Slave
3-2-4 controlador de teclado
3-3-4 inicialização do vídeo
3-4-1 retrace do vídeo
3-4-2 procura por ROM de vídeo em processamento
4-2-1 teste da interrupção do Timer
4-2-2 teste de Shutdown
4-2-3 falha na porta A20
4-2-4 interrupção inesperada em modo protegido
4-3-1 teste de RAM (endereço da falha >FFFFh)
4-3-3 Intervalo do timer canal 2
4-3-4 relógio do sistema
4-4-1 porta Serial
4-4-2 porta Paralela
4-4-3 teste do co-processador matemático
1-1-2* seleção da placa de sistema
1-1-3* Extender CMOS RAM

*código de áudio precedido por tom mais grave

Referências:
• AMI BIOS: http://www.amibios.com
• Phoenix BIOS: http://www.phoenix.com/index.html
• AWARD BIOS: http://www.phoenix.com/pcuser/awardbios/Award.html