Ciência da Computação

 

 Processamento de funções, Reconhecimento de Linguagens e Solucionabilidade de problemas, Organização e Busca da informação, Compreensão das Imagens, Raciocionio e Robótica
1. Problema 










2. Conjunto
É uma estrutura que agrupa objetos e constitui uma base para construir estruturas mais complexas. É uma coleção, sem repetições e sem qualquer ordenação, de objetos denominados elementos. Elemento pode ser um objeto concreto ou abstrato.

As relações entre elementos e conjuntos são: persistencia, sub conjuntos, igualdade de conjuntos.

As operações de conjuntos são: união (+), interseção (*), complemento (não), diferença (-) (derivada da da composição complemento e interseção), conjunto de partes e produto cartesiano.

União


Interseção





A relação sobre dois conjuntos A e B é definida como um subconjunto de A x B.

Uma função é um mapeamento que associa elementos de um conjunto denominado domínio e elementos de outro conjunto chamado de contradominio.

 
3. AlgoritimoÉ uma lista finita de instruções que tem por objetivo resolver um problema.

Caracteristicas:
1.    Solução de um problema
2.    Tem descrição finita e não ambigua
3.    É intuitivo
4.    Deve consistir de passos discretos, executáveis mecanicamente em um tempo finito.

Ex.: Problema:
       Mostar o fatorial de um número de 1 a 9
       
       Solução:
 fatorial = 1;
 Para numero = 1 até 9 com incremento de 1 for (i=1; i<10; i++ ){
 fatorial = fatorial * numero;
 mostrar número, "!=",fatorial, branco

 
5. Máquinas
O objetivo de uma máquina é suprir todas as informações para que a computação de um programa possa ser descrita. Portanto cabe a máquina suprir o significado (dar semântica) aos identificadores das operações e testes.
Assim cada identificador de operação e teste interpretado pela máquina deve ser associado a uma transformação na estrutura de memória e a uma função verdade, respectivamente. Nore-se que:
  • nem todo o identificador de operação ou teste é definido em uma máquina
  • para cada identificador de operação ou teste definido em uma máquina, existe sómente uma função associada.
Adicionalmente, a máquina deve descrever o armazenamento ou recuperação de informações na estrutura de memória.

Os computadores atuais, seguem a máquina de Turing (1950) . Usam linguagem recursivamente enumeravel e sensivel ao contexto.
O ponto de partida de Turing foi analisar a situação na qual uma pessoa, equipada com um instrumento de escrita e um apagador , realiza cálculos em uma folha de papel , organizada em quadrados.O trabalho da pessoa é :
  •  ler um simbolo de um quadrado;
  • alterar um simbolo em um quadrado;
  • mover os olhos para outro quadrado;
Quando é encontrada alguma representação satisfatória para a resposta desejada, a pessoa termina os cálculos.

A maquina é constituida de 3 partes:
  • Fita. Usada como dispositivo de entrada, saida e memória de trabalho
  • Unidade de controle. Reflete o estado corrente da máquina (numero finito e predefinido de estados). Posui uma unidade de leitura e gravação (cabeça da fita), naqual acessa uma célula da fita de cada vez e semovimenta da esquerda para direita.
  • Programa, Função Programa ou Função de Transição. Função que define o estado da máquina e comanda as leituras dos simbolos, as gravações dos simbolos e o sentido de movimento da cabeça.
A fita é finita a esquerda e infinita a direita. cada célua armazena um simbolo.
Os simbolos podem:
  • pertencer ao alfabeto de entrada;
  • pertencer ao alfabeto auxiliar;
  • ser branco; 
  • ser marcador de inicio de fita;
  Tem o seguinte desenho:






Hierarquia das classes de máquina:

5.1 Máquina Universais
 xxxxxxx



---------------->  menor poder computacional  de 5.1 para 5.1.2.1.1.1

O modelo mais utilizado como formalização de algoritimo é a máquina de Turing, proposta em 1936 (20 anos antes do primeiro computador digital). É um mecanismo simples em que uma pessoa realiza calculos, usando um instrumento de escrita e um apagador.
O modelo formal é baseado em uma fita (usada para entrada, saida e rascunho) uma unidade de controle e um programa.
Na verdade a maquina de Touring é um programa para a maquina Universal..
Os seguintes modelos são equivalentes a maquina de Turing:
  • Maquina Norma. Uma máquina registradora, sendo que o conjunto de registradores é infinito.
  • Máquina de Post. Baseada na estrutura de dados do tipo fila (o primeiro dado aramazenado é o primero a ser recuperado.
  • Máquinas de Pilhas. Baseado na estrutura de dados do tipo pilha (o ultimo dado armazenado é o primeiro a ser recuperado), onde são necessários pelo menos duas pilhas para simular o mesmo poder computacional de uma fita ou fila.
6. Linguagens
É um conjunto, finito ou infinito, de cadeias de comprimento finito, formadas pela concatenação de lementos de um alfabeto finito e não vazio.  Linguagens são autômatos ou seja maquinas abstratas.

Os mecanismos de geração formal de linguagem comumente usados para descrever a léxica, sintaxe, semantica e blocos de construção são chamados de gramatica..



6.1 Sintaxe e Semantica
Sintaxe é a forma de suas expressões , de suas instruções e de suas unidades de programa.
Semântica é o significado destes três.

Ex.: sintaxe do if         if (<expr>) <instrução> 
      semântica do if    se o valor da expressão for verdadeiro, a instrução será selecionada

Método mais comum para descrever a sintaxe: a gramatica livre de contexto (também conhecida como Forma de Backus-Naur  BNF).

A gramática de atributos pode ser usada para descrever tanto a sintaxe como a semantica estatica das linguagens de programação.

Métodos formais para descrever a semâtica  - operacional, axiomática e denotacional.



6.2 Hierarquia de linguagens segundo Chomsky



---------------->  mais restritas 6.2.1 para 6.2.1.1.1.1.1


7. Automatas finitos
É uma máquina que possue um número finito e pré definido de estados. Tem a capacidade de resolver um problema por êle mesmo.

Exemplos de automatas finito com saida: Hipertexto, Hipemidia, Animação


8. Otimização
Maquina com menor número de estado que desempenha a mesma função (algoritimo coloring)

Ferramentas para otimização podem ser: Tabela de decisões, máquinas de estado e grafos. 

8.1 Tabela de decisões
São automatas constituidos de 2 partes:
logica combinacional  ==>  estados de transição

Lógica é o estudo dos principios e métodos usados para destinguir das sentenças as verdadeiras e sentenças falsas.

Proposição é uma construção (sentença, frase, pensamento) a que se pode atribuir juizo. O tipo de juizo é verdadeiro ou falso.

Condição 1
  |Condição 2
      |Condição 3 e Condição 4

S S  S     ação 1
N N N     ação 2
N S  -     ação 3
             ação 4


8.2. Maquina de estado
São sistemas algébricos que modelam um comportamento de aplicativos, projeto de hardware de sistemas digitais, engenharia de software, no estudo da computação e das linguagens.

Ex.:



Finalidade:
   atomatas finitos com saida
   reconhecedores de linguagem

Elementos:
   automata finito - Saida limitada a ligica binária (aceita / rejeita). Gera uma palavra de saida.
   saidas - (são indicadas na transição - maquina de mealy) 
               (são indicadas no estado - maquina de Moore) - não pode ser lida ou  seja não pode ser usada como memória                          auxiliar.
   estado - armazena informações sôbre o passado. Armazena as mudanças desde a entrada num estado até o presente                            momento. É  representado por um texto ou número circulado.
   transições - indica uma mudança de estado. É descrita por uma condição. 
   ações - é a descrição de uma atividade que deve ser realizada em determinado momento. Ação de entrada (no estado)                         executa a ação quando entra no estado.
              Ação de saida : executa quando sai do estado..
              Ação de transição: executa quando ocorre uma determinda transição.
   diagrama de estado - representa uma máquina de estado finita.

Processo de construção:
   determinação do grafico de estado (forma de grafo)
   construir tabela de estado a partir do gráfico
   eliminação de estados equivalentes
   designação de estados auxiliares
   desenhar mapas de transição (tabelas de estado e de estados auxiliares)
   desenhar mapas de entrada (mapas de transiçaõ e das tabelas de entrada)
   desenhar mapa de saida (estados auxiliares e tabela de estado)


8.3 Grafos



É um conjunto não vazio de nós (vertices, ex.: 1,2,3,4,5) e um conjunto de arcos (arestas ex.:a1,a2,a3,a4,a5,a6) tais que uma função associa a cada arco um par ordenado de nós. O arco pode ser uma seta (p. ex Pert, diagrama de fluxo) ou não (mapa de estrada).

Subgrafo é um grafo obtido apagando-se aparte do grafo original e deixando o resto sem modificação.



9. Programas
Implementa o algoritimo.

São constituidos de operações  (composição sequencial, não deterministica e concorrente) e testes,
e portanto não incluem funções de entrada e saida.

A estruturas de programa podem ser:


9.1 Programas Recursivos
 OPERAÇÂO VAZIA     Programa que chama a si mesmo. Existe um algoritimo capaz de responder "pertence" ou "não pertence".

9.2 Programas Monoliticos

FLUXOGRAMA


9.2.1 Programas Iterativos
FAÇA ENQUANTO  QUE       



---------------->   programas mais gerais  de 9.1 para 9.2.1

Ex.: Programa em Html/Javascript para implentar o algoritimo para mostrar fatorial de um número variando de 1 a 9 .
<html xmlns="http://www.w3.org/1999/xhtml">

<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Tabela fatorial</title>
</head>

<body>

<h2> Tabela fatorial </h2>
<script>
var fatorial = 1;
for (numero=1; numero<10; numero++ ){
 fatorial = fatorial * i;
 document.write (numero + "!=" + fatorial + "<br>");
 }
 </script>
</body>

</html>


10. Hardware
É uma máquina de estado implementada através de circuitos sequenciais e combinacionais.







10. Rede de Conhecimento {9} 1.Problema 2. Conjunto 3.Algoritimos 5.Maquinas 6.Linguagens  7.Automatas finito 8.Otimização 9.Programa 10.Hardware
Referencia
  1. Diverio,Tiarajú Asmuz . Teoria da computação. Maquinas Universais e computabilidade. 2008,1ed,Bookman.
  2. Ramos, Marcus Vinicius Midena. Linguagens Formais. teoria, modelagem e implementação. 2009, Bookman.
  3. Gersting, Judith L. Fundamentos matemátiocos para a Ciência da computação. 2003, 5a ed. , LTC.
  4. Brookshear, Clenn. Ciência da Computação Uma visão abrangente. 2003, 7a. ed. ,Bookman.
  5. Sebesta, Robert W. Conceitos de Linguagens de programação. 2002, 5a. ed. , Bookman.