Laritmè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.National Science Foundation, Division of Mathematical Science, Program description PD 06-888 Computational Mathematics, 2006.
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 d'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 Les matemàtiques de computació científica (l'apartat teòric que involucra proves matemàtiquesMathematics of Computation, Journal overview .), 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)Future Directions in Computational Mathematics, Algorithms, and Scientific Software, Report of panel chaired by R. Rheinbold, 1985. 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: i . 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: . 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: . 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:
Càlcul de complements Producte booleà Suma booleana +Taula de VeritatA BA+BA*B0 0000 1101 0101 111 AA'0110
Les propietats que segueixen són:
Commutativa: A+B = B+A. Distributiva A*(B+C)=A*B + A*C. Elements neutres diferents: A+0=A, A*1=A. 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. miniatura|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: si el nombre és senar: i .
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. miniatura|260x260px|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.
é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:
miniatura|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 sense marc|130x130px
Expressió
Q = A
Taula de veritat
AQ0011
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.