Aritmètica computacional

L'aritmètica computacional implica la recerca matemàtica en àrees de ciència on la informàtica fa una funció central i essencial, posant importància en algoritmes, mètodes numèrics, i mètodes simbòlics. La computació en la recerca és bastant prominent.^[1]

Les matemàtiques aplicades als computadors consisteixen a utilitzar les matemàtiques per a permetre millorar la computació d'aquest àmbit. Les matemàtiques computacionals també poden referir-se a l'ús d'ordinadors per a les matemàtiques en si. Això inclou l'ús d'ordinadors per a càlculs matemàtics (àlgebra per ordinador), l'estudi de què es pot (i què no) informatitzar en matemàtiques (mètodes efectius), quins càlculs es poden fer amb la tecnologia actual (teoria de la complexitat) i quines demostracions es poden fer en ordinadors (assistents de prova), entre altres.

Història

Gràcies a l'aparició del transistor i dels circuits integrats, apareixen els primers perifèrics (dispositius que es connecten a equips informàtics) d'entrada i sortida de dades. A finals de 1960 apareix l'enginyeria informàtica especialitzada en el disseny de sistemes informàtics per gestionar els processos d'informació, alhora que sorgeix un altre tipus d'enginyeria centrada en els programes. És aquí quan comencen a aparèixer els conceptes teòrics sobre els models matemàtics i de processament de la informació relacionats amb els computadors que posteriorment donarà lloc a les ciències de la computació.

Àrees de les matemàtiques computacionals

Les matemàtiques computacionals van divergir de les matemàtiques aplicades, actualment les matemàtiques computacionals inclouen:

• Ciència computacional, també conegut com a computació científica o enginyeria computacional
• Solucionar problemes matemàtics per simulacre d'ordinador 
• Mètodes numèrics que s'utilitzen en computació científica, per exemple àlgebra lineal numèrica i anàlisi numèrica
• Mètodes estocàstics, com els mètodes Monte Carlo i altres representacions d'incertesa en computació científica, per exemple elements finits estocàstics^[2]
• Les matemàtiques de computació científica (l'apartat teòric que involucra proves matemàtiques^[3]), en particular anàlisi numèrica, la teoria de mètodes numèrics (però la teoria de la computació i la complexitat d'algoritmes pertanyen a informàtica teòrica)^[4]
• Lingüística computacional, tècniques d'ordinador en les llengües naturals
• Geometria algebraica
• Teoria de grup computacional
• Geometria computacional

Representació dels nombres

L'usuari es comunica amb el computador en sistema decimal, és a dir, introdueix i rep els nombres en base decimal. El computador quan rep aquestes dades, per tal de poder treballar amb ells, els converteix en sistema binari, que és el llenguatge natural d'operacions. Un cop la màquina ha realitzat el càlcul desitjat de forma binària, abans de mostrar el resultat a l'usuari, el converteix en format decimal.

Tanmateix, en efectuar aquestes conversions i fer els càlculs se susciten petits errors que, si no es tenen en compte, poden propagar-se i acabar en resultats inexactes i llunys de la realitat. És per això que és molt important entendre l'aritmètica dels computadors i identificar les situacions on poden aparèixer aquests errors.

Àlgebra Booleana

Tant els circuits dels computadors com els d'altres dispositius electrònics contenen entrades (inputs) amb només dos estats, el 0 o l'1. Aquests produeixen sortides (outputs) amb un dels dos dels estats anteriorment comentats. És per aquest motiu que els circuits poden construir-se de forma que només manejar elements bàsics de dos estats.

Va ser Claude Shannon, basant-se en les lleis donades per G.Boole, que va demostrar com es podien utilitzar les regles bàsiques de la lògica per dissenyar circuits. Aquestes regles van ser formar la base de l'àlgebra de Boole, de forma que l'operació realitzada per un circuit es pot definir amb una funció booleana.

L'àlgebra de Boole proporciona operacions i regles per treballar amb el conjunt binari {0,1}. Les tres operacions booleanes bàsiques són: complement, suma booleana i producte booleà.

• El complement booleà d'un cert element del conjunt binari s'indica amb un guió o bé per la paraula NOT, per tant, es defineix com: ${\displaystyle {\bar {0}}=1}$ i ${\displaystyle {\bar {1}}=0}$. El complement equival a l'operador lògic negació.
• La suma booleana de dos elements del conjunt binari, indicat pel símbol + o bé OR, és una operació sotmesa a les regles següents: ${\displaystyle 0+0=0,0+1=1,1+0=1,1+1=1}$. La suma booleana equival a l'operador lògic ᐯ.
• El producte booleà de dos elements del conjunt binari, indicat per un • o bé per AND, és una operació que respon a les següents regles: ${\displaystyle 0\bullet 0=0,0\bullet 1=0,1\bullet 0=0,1\bullet 1=1}$. El producte booleà equival a l'operador lògic ᐱ.

Sempre que no hi hagi la presència de parèntesis, les regles de presidència per l'execució concatenada de més d'una operació booleana serà la següent:

1. Càlcul de complements
2. Producte booleà
3. Suma booleana

Taula de Veritat

A B	A+B	A*B
0 0	0	0
0 1	1	0
1 0	1	0
1 1	1	1

A	A'
0	1
1	0

Les propietats que segueixen són:

1. Commutativa: A+B = B+A.
2. Distributiva A*(B+C)=A*B + A*C.
3. Elements neutres diferents: A+0=A, A*1=A.
4. Sempre existeix el complementari d'A, denominat A': A+A'=1, A*A'=0.

La taula de veritat és una forma de representar el valor de la funció per a cada combinació de les entrades més visual. Si la funció està definida per a totes les combinacions, es diu completa, si no, es diu que és una funció/taula incompleta.

Diagrama de Karnaugh

Diagrama de Karnaugh

Els diagrames de Karnaugh s'utilitzen per simplificar les funcions de l'Àlgebra de Boole, que van ser inventats per Maurice Karnaugh, reduint càlculs externs i reconeixent patrons. Es poden realitzar per funcions de fins a almenys 6 variables. Un diagrama és una quadrícula d'una mida determinada pel nombre de variables de la funció:

• si el nombre és parell: ${\displaystyle files=columnes={\sqrt {2^{variables}}}}$
• si el nombre és senar: ${\displaystyle columnes={\sqrt {2^{variables+1}}}}$ i ${\displaystyle files={\frac {columnes}{2}}}$.

A l'hora de construir el diagrama cada columna, i fila, s'anota amb la combinació corresponent de 0 i 1. A la imatge les columnes estan anotades per '00', '01', '11' i '10', el pas de '01' a '11', en comptes de '10', és degut en què les anotacions entre columnes adjacents només poden variar un bit. La combinació de cada fila i columna és el resultat de la funció per cada combinació d'entrada.

Després de la construcció del diagrama, s'han d'agrupar els 1 en grups de potències de 2 (grups d'1, de 2, de 4, de 8, etc.). Els 1 poden estar a més d'un grup, tots els 1 han d'estar en un grup i s'han de fer el menor nombre de grups. Es podrien agrupar un 1 de la columna '10' amb un 1 de la columna '00' i de la mateixa manera es podria fer amb les files.

Llavors per obtenir la funció simplificada s'ha de observar a cada grup d'1 quines variables mantenen el mateix valor i quines difereixen, les que es mantinguin s'afegiran a la funció i les que canviïn no. Si una variable que es manté té el valor 1 s'afegirà a la funció sense negar, en canvi, si la variable té valor 0 s'afegirà negada a la funció.

El mètode de diagrames de Karnaugh no és eficient per implementar-lo en computadors, és molt més eficient l'algoritme Quine-McCluskey.

Algoritme Quine-McCluskey

És un mètode de simplificació de funcions booleanes desarrollat per Williard Van Orman Quine i Edward J. McCluskey. Té la mateixa utilitat que els diagrames de Karnaugh, i tot que els diagrames són més pràctics, aquest algorisme és més eficient per implementar-lo computacionalment.

Algoritme Quine-McCluskey

S'han de seguir aquests passos per simplificar les funcions booleanes mitjançant el mètode tabular Quine-McClukey:

Pas 1 − Ordenar els termes mínims donats en ordre ascendent i fer els grups en funció del nombre d'uns presents en les seves representacions binàries. Per tant, hi haurà com a màxim "n+1" grups si hi ha "n" variables booleanes en una funció booleana o "n" bits en l'equivalent binari de termes mínims.

Pas 2 − Comparar els termes mínims presents en grups successius. Si només hi ha un canvi en la posició d'un bit, agafar el parell d'aquests dos termes mínims. Col·locar aquest símbol "_" a la posició de bit diferent i mantenir els bits restants tal com estan.

Pas 3 − Repetir el pas 2 amb termes acabats de formar fins que es tinguin tots els implicants primers.

Pas 4 − Formular la taula d'implicants primers. Està format per un conjunt de files i columnes. Els implicants primers es poden col·locar en fila i els termes mínims es poden col·locar en columna. Col·locar "1" a les cel·les corresponents als termes mínims que es cobreixen en cada implicant primer.

Pas 5 − Trobar els implicants primers essencials observant cada columna. Si el terme mínim està cobert només per un implicant primer, llavors és un implicant primer essencial. Aquests implicants primers essencials formaran part de la funció booleana simplificada.

Pas 6 − Reduir la taula d'implicants primers eliminant la fila de cada implicant primer essencial i les columnes corresponents als termes mínims que es cobreixen en aquest implicant primer essencial. Repetir el pas 5 per a la taula d'implicants primers reduïts. Aturar aquest procés quan s'acabin tots els termes mínims de la funció booleana donada.

Complexitat: és més pràctic que el mapa de Karnaugh, però quan es tracta de treballar amb més de quatre variables, el temps de resolució de l'algoritme Quine-McCluskey creix de manera exponencial amb l'augment del nombre de variables. Per tant, les funcions amb un nombre gran de variables han de ser minimitzades amb altres mètodes heurístics.

Circuits digitals combinacionals

Els circuits digitals combinacionals són circuits on l'estat lògic de la sortida només depèn de l'estat de les entrades, sense intervenir el temps ni l'estat actual del circuit. En altres paraules, no tenen memòria. Es resolen mitjançant taules de veritat. Aquests circuits es poden dividir en dos grans grups:

Circuit de portes lògiques

Portes lògiques pures

Les portes lògiques són els elements bàsics del circuits. Cada tipus de porta implementa una operació booleana i gràcies a l'àlgebra booleana, explicada anteriorment, es poden dissenyar circuits que executin diverses tasques.

Les portes lògiques pures i la resta de circuits integrats que obeeixen a una taula de veritat, en aquesta família s'integren els codificadors, descodificadors i sumadors.

Funció Buffer

La funció buffer o igualtat, és un tipus de raonament que conté una sola premissa i una sola conclusió. Si la premissa existeix, aleshores la conclusió també. És una de les comportes menys utilitzades, però de vegades és necessària. Els seus estats lògics romanen de la mateixa manera, es podria considerar com un cable connectat ja que allò que tenim a l'entrada s'obtindrà a la sortida. La funció principal del buffer és augmentar el corrent subministrat a la sortida mentre es reté l'estat lògic, a la pràctica és utilitzat per amplificar el corrent o com a seguidor de tensió per adaptar impedàncies.

• Símbol

• Expressió

Q = A

• Taula de veritat

A	Q
0	0
1	1

Circuits Aritmètics

El càlcul aritmètic exerceix un paper crucial en el processament d'informació. Aquests circuits són una part fonamental de les unitats aritmèticològiques, components de les CPUs.

Els circuits aritmètics es troben dins de la variada gamma de circuits digitals, aquests tenen com a objectiu realitzar operacions aritmètiques en format binari, punt fix o punt flotat. Depenent de l'aplicació s'utilitzaran els uns o els altres. Són dispositius que poden fer operacions aritmètiques amb números binaris.

Tenim sumadors, restadors, multiplicadors, divisors i funcions combinades per realitzar operacions complexes, com ara el càlcul d'exponencials o d'arrels quadrades. Les principals operacions aritmètiques computacionals, és a dir, que realitza un ordinador són: suma, resta, producte i divisió, però les més usades són les dues primeres.

Full-adder

Sumador

És un circuit lògic que realitza la suma aritmètica de dos paraules binàries.

La suma de nombres binaris d'n bits ens donarà un resultat format per un nombre binari d'n+1 bits.

Un sumador de dos bits haurà de tenir dues entrades i tres sortides.

Un sumador complet és un circuit que, a part de tenir les entrades corresponents als bits que es pretenen sumar, té una entrada addicional corresponent a l'arrossegament de l'etapa anterior.

Multiplicador

Els circuits multiplicadors són xarxes de díodes i condensadors que, a partir d'una tensió alterna, proporcionen una tensió continua molt alta. Es solen denominar pel factor multiplicador que tenen (triplicador, quadruplicador...).

Hi ha controladors integrats per multiplicar tensions, que necesiten condensadors externs per proporcionar tensions regulades. També es poden anomenar "bombes de tensió" i poden proporcionar, tant, tensions positives i negatives. El seu principal inconvenient és que només permet corrents baixes, ja que utilitzen condensadors com elements de pas de corrent i amb valors raonables de condensadors obtenen impedàncies bastant elevades.

Algorismes computables

No tots els algorismes es poden executar en un computador, però els que s'expliquen en aquesta secció sí que ho són.

Un algorisme és un conjunt finit d'instruccions escrites en un determinat llenguatge que contenen una descripció detallada i lògicament ordenada, instruccions que condueixen a la solució d'un problema.

Tots els algorismes han de tenir una sèrie de característiques, enumerades a continuació:

• Entrada: L'algorisme rep les dades amb les quals s'efectuaran els càlculs, input.
• Sortida: Resultats produïts pels càlculs dirigits per l'algorisme, output.
• Procés: Conté tots els passos lògics de l'algorisme.
• Determinisme: Tots els resultats intermedi obtingut en cada etapa de l'algorisme és únic i només ve determinat per les entrades i pels resultats de les etapes anteriors.
• Correcció: La sortida produïda és correcta, és a dir, l'algoritme resol correctament el problema plantejat.
• Finitud: Resol el problema en un nombre finit de passos o etapes.
• Generalitat: L'algorisme s'ha de poder aplicar a tots els problemes d'una forma determinada i no només a alguns casos particulars.
• Efectivitat: Cada etapa de l'algorisme ha de poder realitzar-se de manera exacta i en un temps finit.

Alguns exemples d'algorismes numèrics computables són la cerca del valor màxim d'una sèrie de nombres, l'ordenació de diversos nombres o el càlcul de la solució d'una equació algebraica.

Complexitat computacional

Quan es relaciona l'eficiència d'un algorisme amb el temps d'execució, fa referència a la complexitat temporal de l'algorisme. En canvi, si es relaciona la quantitat o l'espai de memòria utilitzat, fa referència a la complexitat espacial. Ambdós corresponen a la complexitat computacional de l'algorisme.

A l'hora d'escollir entre dos algorismes aquell que té més eficiència, i, per tant, menys càlculs repetits o millor plantejats, serà l'escollit.

Referències

1. National Science Foundation, Division of Mathematical Science, Program description PD 06-888 Computational Mathematics, 2006.
2. «NSF Seeks Proposals on Stochastic Systems». SIAM News, 19-08-2005. Arxivat de l'original el 5 de febrer 2012. [Consulta: 2 febrer 2015].
3. Mathematics of Computation, Journal overview.
4. Future Directions in Computational Mathematics, Algorithms, and Scientific Software, Report of panel chaired by R. Rheinbold, 1985.

Enllaços externs

• Fundacions de Matemàtiques Computacionals, una ONG (anglès)
• Aritmètica del computador
• Àlgebra Booleana, (anglès)
• Aritmètica computacional, (castellà)
• Circuits Aritmètics, (anglès)