Por que os dados em ciência da computação são considerados discretos?

35

Entendo que a "estrutura" dos dados é totalmente dependente da Álgebra Booleana, mas:

Por que os dados são considerados uma entidade matemática discreta, e não contínua?

Relacionado a isso:

Quais são os inconvenientes ou invariantes que são violados na estruturação de dados como uma entidade contínua em dimensões ?r

Eu não sou especialista na área, pois sou estudante de matemática, então eu realmente aprecio se alguém me explicasse isso como se eu tivesse cinco anos.

evil_potato
fonte
12
Computação real seria excessivamente poderoso
Harold
11
Leia este capítulo se o tempo permitir. O autor explica em muito fácil de aprender com analógico vs sinais binários
Muhammad Sayef

Respostas:

44

Responda

por que os dados foram considerados uma entidade matemática discreta e não contínua

Esta não foi uma escolha; é teoricamente e praticamente impossível representar valores contínuos e concretos em um computador digital ou, de fato, em qualquer tipo de cálculo.

Observe que "discreto" não significa "número inteiro" ou algo assim. "discreto" é o oposto de "contínuo". Isso significa que, para ter um computador realmente capaz de armazenar coisas não discretas, você precisará armazenar dois números ae bonde, abs(a-b) < εpor qualquer valor arbitrariamente pequeno de ε. Claro, você pode ir tão fundo quanto quiser (usando cada vez mais espaço de armazenamento), mas todo computador (físico) sempre tem um limite superior. Não importa o que você faça, você nunca poderá criar um computador (físico) que armazene números arbitrariamente finamente resolvidos.

Mesmo se você conseguir representar números por construções matemáticas (por exemplo π), isso não muda nada. Se você armazena um gráfico ou o que quer que represente uma fórmula matemática, isso é tão discreto quanto qualquer outra coisa.

Termo aditivo

O resto é apenas uma pequena perspectiva além do campo da ciência da computação. Como os comentários mostraram, o tópico físico não é incontestável e, como você pode ver, formulei meu próximo parágrafo de uma maneira que não é comprometida com a verdade ou não. Tome mais como motivação que o conceito de "continuum" não seja trivial. A resposta dada acima não depende se o espaço é discreto ou não.

Observe que tudo isso não é tanto um problema de computadores, mas um problema com o significado de "contínuo". Por exemplo, nem todos concordam, ou concordaram no passado, que o Universo é contínuo (por exemplo, a escala de Planck implica que o espaço-tempo é discreto? ). Para algumas coisas (por exemplo, estados de energia dos elétrons e muitas outras características da Mecânica Quântica), sabemos até que o Universo não é contínuo; para outros (por exemplo, posição ...) o júri ainda está de fora (pelo menos em relação à interpretação dos resultados da pesquisa ...). (Não obstante o problema de que, mesmo que seja contínuo, não podemos medir com precisão arbitrária => Heisenberg etc.).

Em matemática, estudar o continuum (isto é, os reais) abre muitos aspectos fascinantes, como a teoria da medida, o que torna absolutamente impossível realmente armazenar um tipo "contínuo" de número / dados.

AnoE
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
DW
29

Os computadores representam um dado como um número finito de bits (zeros e uns) e o conjunto de todas as cadeias de bits finitas é discreto. Você só pode trabalhar com, digamos, números reais se encontrar alguma representação finita para eles. Por exemplo, você pode dizer "esses dados correspondem ao número ", mas não pode armazenar todos os dígitos de π em um computador. Assim, os programas de computador que trabalham com números reais na verdade só funcionam em um subconjunto discreto de R .ππR

Christian Matt
fonte
Computadores digitais fazem isso, mas não computadores analógicos.
Drew
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
DW
8

Para adicionar todas essas ótimas respostas, vale a pena notar que Alan Turing, ao definir suas máquinas, argumenta que a quantidade de símbolos precisa ser finita (mesmo que arbitrariamente grande), já que um computador (que significa humano) não pode distinguir todos os símbolos de outra maneira.

Aqui estão alguns trechos de seu artigo de 1936, "Sobre números computáveis, com uma aplicação ao problema do Entscheidung":

insira a descrição da imagem aqui

E então na seção 9:

insira a descrição da imagem aqui insira a descrição da imagem aqui

Guido
fonte
11
Transcreva as imagens para que possam ser indexadas por pesquisas.
Raphael
7

Está tudo na implementação.

Se você pensar bem, os computadores realmente são dispositivos contínuos. Isso é facilmente demonstrado pelo fato de que todas as equações EM que regem como funcionam são contínuas. O que é discreto são os modelos que usamos para decidir como usar esses dispositivos de computação. As máquinas abstratas que usamos para descrever a computação são todas discretas.

A enorme vantagem prática disso é ter independência em relação a muitos desafios de controle de qualidade. Se nossos modelos de computadores alavancassem a natureza contínua e completa de seus transistores e capacitores, teríamos que nos preocupar com o quão bem construímos todos os transistores em um tremendo grau. Podemos ver isso no mundo do áudio. No mundo em que os audiófilos habitam, é razoável gastar US $ 2.000 em um amplificador que pode ter 10 transistores cuidadosamente selecionados e combinados, que fazem exatamente a coisa contínua que desejam. Compare isso com 1.400.000.000 de transistores em uma CPU Core i7 a um custo enorme de US $ 400.

Como nossos modelos computacionais são discretos, podemos modelar todos os sinais que vemos em um computador como um sinal discreto mais algum termo de erro contínuo. Podemos então filtrar os erros simplesmente observando que eles não têm a forma correta para fazer parte do sinal discreto.

Uma parte importante disso é a remoção de termos de tempo em nossos modelos abstratos. Muitos de nossos modelos não medem o tempo contra algum processo físico, mas contra algum sinal "lógico" conhecido como relógio. Se você interromper um relógio, o sistema para de se mover, mas não quebra. Ele acaba de eliminar os erros analógicos que possa ter e fica aguardando o próximo pulso discreto do relógio. A remoção de termos de tempo contínuos simplifica drasticamente a computação e as provas sobre a computação. Em vez disso, nossos conceitos de tempo são medidos discretamente, como visto nas categorizações de algoritmos P e NP.

Cort Ammon
fonte
7

Porque:

  • Computadores digitais não podem armazenar números reais arbitrários.

  • Os computadores analógicos são atormentados por ruídos térmicos (se eletrônicos), fricção (se mecânicos ou hidráulicos), distúrbios, sensibilidade a variações de temperatura, imperfeições inevitáveis ​​e envelhecimento. Lidar com essas dificuldades é o que os físicos e engenheiros (experimentais) fazem. A maioria das ciências da computação simplesmente abstrai a física.

Aqui estão alguns trabalhos sobre computação real :

e aqui está um artigo sobre computação analógica :

Rodrigo de Azevedo
fonte
4

O termo "computador" na linguagem moderna significa "computador digital"; a essência de um computador digital é que ele possui um número finito de estados discretos. Poder-se-ia ter um debate interessante sobre se as razões pelas quais os computadores digitais foram favoráveis ​​aos computadores analógicos se referiam principalmente à praticidade da engenharia ou se deviam principalmente à melhor sustentação da ciência da computação teórica. Mas, sejam quais forem as razões, acabamos com os computadores digitais e qualquer modelo matemático útil de um computador digital (e, portanto, seus dados) será discreto e não contínuo.

Michael Kay
fonte
2

A palavra dataderiva da palavra latina datum, que significa algo que foi dado. Com o tempo, a forma plural mudou de uso e agora é comumente usada como singular e plural. Também passou a ser associado especificamente a informações.

Observe que há uma diferença entre um item de informação (um dado) e sua representação.

A Teoria da Informação lida com (entre outras coisas) informações discretas representadas por variáveis. Essas são entidades contáveis. Por exemplo, velocidade, localização, massa etc. são quantidades contínuas, mas discretas uma da outra: não há transformação entre massa e localização. Quando essas quantidades são representadas numericamente, seus itens de dados, independentemente de serem representados, também são discretos.

Por outro lado, a grande maioria de nossos computadores atuais usa alguma forma de carga elétrica para representar informações. A cobrança está presente ou não; existe corrente no circuito ou não. Isso também é discreto, mas não precisa ser! É simplesmente por causa da maneira como nossa tecnologia se desenvolveu que usamos a representação binária. É possível que a evolução da computação quântica mude isso no futuro próximo. Também não é inconcebível que computadores analógicos ressurgam e nossas noções de que os números devem ser representados por binários serão lavadas!

Resumindo: datasão compostos por itens discretos de informação, cada um dos quais é um dado; enquanto que cada dado não precisa ser representado usando matemática discreta, mas atualmente é puramente por coincidência contemporânea.

Torta má do cão
fonte
11
A teoria da informação também pode lidar com variáveis ​​contínuas.
Yuval Filmus
11
Veja, por exemplo, entropia diferencial .
Yuval Filmus
2

Quero desafiar sua premissa fundamental:

Por que os dados são considerados uma entidade matemática discreta, e não contínua?

Não é.

Por exemplo, o estudo de algoritmos é um subcampo importante da ciência da computação e existem muitos algoritmos que trabalham com dados contínuos. Você provavelmente conhece o algoritmo de Euclides para calcular o maior divisor comum de dois números naturais, mas você sabia que Euclides também tinha uma versão geométrica do mesmo algoritmo que calcula a medida comum mais longa de duas linhas comensuráveis? Este é um exemplo de algoritmo (e, portanto, um objeto de estudo da ciência da computação) sobre números reais, ou seja, dados contínuos, embora Euclid não tenha pensado dessa maneira.

Existem muitas maneiras diferentes de classificar algoritmos, mas uma maneira usada é classificá-los por sua "continuidade":

  • Algoritmos digitais (algoritmos de eventos discretos sobre dados digitais):
    • a variante numérica do algoritmo de Euclides
    • divisão de mãos longas, multiplicação, etc., como ensinado na escola
    • qualquer programa de computador, programa de cálculo λ, máquina de Turing
  • Dados não digitais, algoritmos de eventos discretos (algoritmos sobre dados contínuos, que ainda têm uma noção de "etapa", ou seja, dados contínuos, mas com tempo discreto):
    • a variante geométrica do algoritmo de Euclides
    • algoritmos em números reais (por exemplo, procedimento de eliminação de Gauss)
    • algoritmos em funções contínuas (por exemplo, o algoritmo de bissecção)
  • Algoritmos analógicos (tempo contínuo, dados contínuos):
    • circuitos elétricos
    • giroscópios mecânicos
  • Algoritmos híbridos (qualquer combinação dos itens acima)
    • robôs

Outras respostas já mencionaram Computação Real na Teoria da Computabilidade, outro subcampo importante da Ciência da Computação.

r

A única desvantagem real (trocadilho com muita intenção) é que esses dados não podem ser representados com computadores digitais comuns. Você pode pensar em algoritmos sobre dados contínuos, mas não pode executá- los nas máquinas padrão que costumamos usar para executar algoritmos.

Essa é a principal razão pela qual os dados contínuos não são tão "visíveis" quanto os dados digitais.

No entanto, uma implementação de um algoritmo analógico não precisa ser complicada de se imaginar ou até de construir. Por exemplo, esta é uma implementação de um algoritmo analógico: Bicicleta do ciclo do triunfoPor Andrew Dressel  - Trabalho próprio, CC BY-SA 3.0 , Link

rqrq×rπq×π

Jörg W Mittag
fonte
"existem muitos algoritmos que funcionam com dados contínuos" - Poderíamos ter uma longa discussão se essas coisas fossem chamadas de "algoritmos", mas isso seria uma guerra na semântica, então não vamos. A questão é que esses não são "algoritmos" executados em computadores, mas em dispositivos super-Turing teóricos, formalmente definidos.
Raphael
11
Acho a metáfora da bicicleta enganosa. Algo que calcula uma função não é um computador, que assumimos implicitamente como universal hoje em dia.
Raphael
1

π

Agora, o conjunto de todos os dados finitos possíveis pode ser colocado em ordem lexicográfica, o que significa que o conjunto é contável. Porém, o conjunto de números reais contínuos é incontável; portanto, sempre existem números no continuum que não podem ser armazenados por um determinado sistema de computação. A partir disso, podemos concluir que o armazenamento de um número real arbitrário requer recursos infinitos.

Mark H
fonte
11
Eu acho que isso está implorando a pergunta . Considere um computador que recebe sua entrada de um pedaço de papel que examina e que fornece sua saída em um pedaço de papel em que desenha. Se os dados fossem contínuos, como sugere o OP, esse computador poderia ser infinitamente preciso com apenas uma quantidade finita de dados.
Ruakh 18/03
@ruakh Você está falando de algo como uma máquina de Turing analógica, onde poderia, por exemplo, ler o comprimento exato de uma linha desenhada?
Mark H
Sim, exatamente. Pelo que entendi, esse é o tipo de pergunta sobre o OP.
Ruakh 18/03
0

Os dados nem sempre são considerados discretos. A programação científica geralmente envolve aritmética de ponto flutuante. O programador geralmente finge que as variáveis ​​envolvidas são contínuas, mantendo em mente a questão da estabilidade numérica, que decorre do fato de que os dados são armazenados apenas com uma precisão finita.

Yuval Filmus
fonte
12
O ponto flutuante é discreto ... se um programador fingir que é contínuo, isso significa apenas que os resultados não importam ou que o programador não entendeu o que está fazendo.
AnoE
2
Eu discordo respeitosamente.
Yuval Filmus
6
@YuvalFilmus, como o ponto flutuante é discreto, não há mais nada a dizer. Cada vez que algo é colocado em um computador comum, ele é discretizado.
Jean-Baptiste Yunès
5
@AnoE significa que os resultados são confiáveis ​​até uma certa precisão, é isso que Yuval quer dizer com "finge". Você pode obter alguns resultados úteis, mas precisa desfocar a precisão. Para conjuntos grandes, faz sentido. Compare isso com os problemas clássicos da mecânica: você sabe que suas medidas não são precisas. um objeto de 3 cm não possui, na verdade, 3.000000000 ~ cm de comprimento. Você acabou de cortar a precisão da sua medição em algum ponto razoável.
Mindwin 17/03
6
Não acho que a pergunta seja sobre como nossas mentes funcionam. Eu acho que é sobre como as coisas realmente funcionam. A razão pela qual os números de ponto flutuante são aproximados é porque são discretos. O fato de você pensar neles como contínuo, mesmo que realmente não o sejam, não ajuda a responder à pergunta sobre por que os valores são discretos nos computadores. Em uma nota lateral, seu modo de pensar pode ser perigoso. Muitos erros resultaram de programadores que pensam no ponto flutuante como contínuo. Mesmo números comuns que tendemos a considerar precisos como 1 décimo ou 1 centésimo são aproximados em ponto flutuante.
JimmyJames
-2
  • Para um computador trabalhar com dados, os dados devem existir na memória acessível do computador
  • A memória acessível de um computador é finita
  • Somente dados finitos podem existir na memória acessível de um computador
  • Valores não discretos são infinitos

Os dados em ciência da computação são considerados discretos.

Repomeister
fonte
elimt(1+1/t)t
A fórmula que você especificou é abreviação - você não pode usá-la em nenhum cálculo cuja "resposta" real real seja necessária e, portanto, nenhum "trabalho" significativo possa ser feito pelo computador. Você pode escrever um pequeno programa de análise de texto para captar e cuspir representações textuais de números irracionais, mas a representação numérica real dos "valores" desses números não pode ser armazenada na memória - mais do que eu posso escrever "isso é infinito" em um pedaço de papel e dizer que estou segurando tudo na minha mão.
Repomeister 19/03/19
11
Você parece estar assumindo que a única maneira de calcular um número real é produzir sua expansão decimal. Simplesmente não é esse o caso.
David Richerby
2
eiπ=116π
11
<,,>,,=,+,,×,÷x1,x2,,xnx1,,xn