Matemàtica discreta
La matemàtica discreta és un àrea de la matemàtica encarregada de l'estudi dels conjunts discrets: finitos o infinits numerables.
En oposició a la matemàtica contínua, que s'encarreguen de l'estudi de conceptes com la continuïtat i el canvi continu, la matemàtica discreta estudia estructures els elements de les quals poden contar-se un per un separadament. És dir, els processos en matemàtica discreta són contables, com per eixemple, els número entero, grafos i sentències de llògica.[1][2][3][4]
Mentres que l'anàlisis real està fundat en el conjunt dels número real els quals no són numerables, la matemàtica discreta és la base de tot lo relacionat en els número natural i/o conjunts numerables.
Són fonamentals per a la ciència de la computació, perque solament són computables les funcions de conjunts numerables.cita requerida
La clau en matemàtica discreta és que no és possible manejar les idees de proximitat o llímit i suavitat en les curves, com es pot en l'anàlisis. Per eixemple, en matemàtica discreta una incògnita pot ser 2 o 3, pero mai s'aproximarà a 3 per l'esquerra en 2.9, 2.99, 2.999, etc. Les gràficas en matemàtica discreta vénen donades per un conjunt finito de punts que es poden contar per separat; és dir, les seues variables són discretes o digitals, mentres que les gràfiques en càlcul són traços continus de rectes o curves; és dir, les seues variables són contínues o analògiques.
Història
[editar | editar còdic]La matemàtica discreta ha vist un gran número de problemes difícils de resoldre. En teoria de grafos, molta de l'investigació realisada en els seus inicis va ser motivada per intents per a provar el teorema dels quatre colors, el qual va ser provat més de cent anys despuix de la seua inicial descripció. El problema dels ponts de Königsberg, un problema clàssic del prolífic Leonhard Euler.
En llògica, el segon problema de la llistade problemes oberts de David Hilbert, era provar que els axioma de l'aritmètica són consistents. El segona teorema de Gödel de la incompletitud va provar en 1931 que açò no és possible, per lo manco dins de l'aritmètica en sí. El dècim problema de Hilbert era determinar si un polinomi diofántico en coeficients sancers dau té una solució sancera. En 1970, Yuri Matiyasevich va provar que açò és impossible de fer.
La necessitat de dessifrar còdics alemans en la Segona Guerra Mundial va donar pas a alvanços en la criptografia i la ciència computacional teòrica, en el primera computadora electrònica, digital i programable desenrollat en Anglaterra. Al mateix temps, requeriments militars varen motivar alvanços en l'investigació d'operacions. La Guerra Freda va tindre significancia en la criptografia, i la va mantindre vigent, en lo que es varen realisar alvanços en la criptografia asimètrica.
Actualment, un dels problemes oberts més famosos en la teoria de l'informàtica és el problema de les classes de complexitat "P = NP". El Clay Mathematics Institute ha oferit un premi d'un milló de dólars per a la primera demostració correcta, junt en premis per a 6 problemes més.
Tòpics en la matemàtica discreta
[editar | editar còdic]Informàtica teòrica
[editar | editar còdic]- Artícul principal → Ciència computacional teòrica.
La teoria de l'informàtica inclou àrees de la matemàtica discreta rellevant a la computació. Està altament relacionada en teoria de grafos i llògica. Dins de la teoria de l'informàtica es troba la teoria d'algoritmes per a problemes matemàtics. La computabilidad estudia lo que pot ser computat i té llaços forts en la llògica, mentres que la complexitat estudia el temps que es necessita per a fer els càlculs. La teoria d'autómates, els llenguages formals i la Dinàmica de sistemes es relacionen de manera propenca en la computabilidad. Les rets de Petri i àlgebra de processos s'usen per a modelar sistemes de càlcul, i els métodos de la matemàtica discreta s'usen per a analisar circuits VLSI. La geometria computacional aplica algoritmes a problemes geomètrics, mentres que l'anàlisis digital d'imàgens els aplica a representacions d'imàgens. La teoria informàtica també inclou l'estudi de tòpics d'informàtica contínua.
Teoria de l'informació
[editar | editar còdic]- Artícul principal → Teoria de l'Informació.
La teoria de l'informació es veu involucrada en la quantificació de l'informació. Cercanamente relacionat en açò és la teoria de codificació, que és usada per a dissenyar métodos de transmissió i almagasenament de senyes eficients i confiables. La teoria de l'informació també inclou tòpics continus tals com senyals análogicas, codificació anàloga i sifrat anàlec.
Llògica
[editar | editar còdic]- Artícul principal → Llògica matemàtica.
La llògica és l'estudi dels principis del raonament vàlit i l'inferència, com també de la consistència, solidea i completitud. Per eixemple, en la majoria dels sistemes en la llògica, la llei de Peirce, (((P→Q)→P)→P) és una teorema. En llògica clàssica, pot ser fàcilment verificat en una taula de veres. L'estudi de les demostracions matemàtiques és particularment important en llògica i té aplicacions en la demostració automàtica de teoremes i verificació formal de software.
Les fòrmules llògiques són estructures discretes, com lo són les demostracions, les quals formen arbres finitos, o més generalment, estructures de grafos acíclics (en cada pas d'inferència combinant una o més branques de premisses per a donar una sola conclusió). Les taules de veres de fòrmules llògiques usualment formen un conjunt finito, generalment restringit a dos valors: verdader i fals, pero la llògica pot tindre valors continus, per eixemple en la llògica difusa. Els conceptes com a arbres de demostracions o derivació infinites també han segut estudiats, per eixemple en la llògica proposicional infinitaria.
Teoria de conjunts
[editar | editar còdic]- Artícul principal → Teoria de conjunts.
La teoria de conjunts és la branca de la matemàtica que estudia conjunts matemàtics, els quals són coleccions d'objectes, tals com a {blau, blanc, roig} o el conjunt infinit de tots els número primo. Conjunts parcialment ordenats i conjunts en atres relacions tenen aplicació en moltes àrees.
En la matemàtica discreta, els conjunts numerables (incloent conjunts finitos) són el principal objecte d'estudi. L'inici de la teoria de conjunts generalment es relaciona en el treball de Georg Cantor, fent distinció entre diferents tipos de conjunts infinits, motivat per l'estudi de les séries trigonométricas. El desenroll més profunt en la teoria de conjunts infinits està fòra de l'alcanç de la matemàtica discreta. De fet, el treball contemporàneu en teoria descriptiva de conjunts fa us extens de l'us de la matemàtica contínua tradicional.
Combinatoria
[editar | editar còdic]- Artícul principal → Combinatoria.
La combinatoria és la branca de la matemàtica que estudia coleccions finitas d'objectes que poden ser combinats o ordenats.
La combinatòria enumerativa s'ocupa, en particular, de el "reconte" dels objectes de dites coleccions.
La combinatoria analítica es concentra en l'enumeració d'estructures combinatòries utilisant ferramentes d'anàlisis complex i teoria de provabilitat. En contrast en la combinatoria enumerativa, que usa fòrmules combinatòries explícites i funcions generatrices per a descriure els resultats, la combinatoria analítica s'enfoca en obtindre fòrmules asintòtiques.
La teoria de disseny és l'estudi de dissenys combinatoris, que són classes de subconjunts en certes propietats numèriques d'intersecció.
La teoria de particions estudia varis problemes asintòtics i d'enumeració relacionats en particions sanceres, i està relacionada en series q, funcions especials i polinomis ortogonals. Originalment una part de teoria numèrica i anàlisis, la teoria de particions és considerada una part d'combinatoria, o un àrea independent.
La teoria de l'orde és l'estudi de conjunts parcialment ordenats, finitos i infinits.
Teoria de grafos
[editar | editar còdic]- Artícul principal → Teoria de grafos.
La teoria de grafos és l'estudi de grafos i la teoria de rets. Generalment és considerada part de la Combinatoria, pero ha evolucionat per la seua banda lo suficient com per a ser considerada una matèria per sí mateixa.[5] La teoria de grafos té extenses aplicacions en totes les àrees de la matemàtica i la ciència. Existixen, inclús, grafos continus.
Teoria de distribucions de provabilitat discretes
[editar | editar còdic]- Artícul principal → Distribució_de_provabilitatDistribucions_de_variable_discreta.
La teoria de distribucions discretes tracta en events que ocorren en espais de mostra numerables. Per eixemple, conteos com el número d'aus en una bandada solament poden tindre valors naturals {0, 1, 2,...}. Per una atra part, observacions contínues com els pesos d'estes aus es poden representar per mig d'número real, i típicament serien modelats per una distribució de provabilitat contínua, com per eixemple, la distribució normal. Distribucions contínues poden ser utilisades per a aproximar discretes i viceversa. Per a situacions en les quals els valors possibles són altament restringits en la seua variabilitat, com per eixemple en daus o cartes, calcular les provabilitats simplement necessita de combinatòria enumerativa.
Teoria de números
[editar | editar còdic]- Artícul principal → Teoria de números.
La teoria de números principalment té que vore en les propietats dels números en general i, particularment, dels sancers. Té aplicacions en la criptografia, criptoanálisis i criptología, particularment en lo que referix a número primo. Atres aspectes de la teoria de números inclou la teoria geomètrica de números. En la teoria analítica de números, també s'utilisen tècniques de matemàtica contínua.
Àlgebra
[editar | editar còdic]- Artícul principal → Àlgebra abstracta.
Les estructures algebraiques ocorren discreta i contínuament. Com a eixemples de àlgebra discretes estan: l'àlgebra booleana, utilisada en circuits digitals i programació, àlgebra relacional, utilisada en bases de senyes; grups, finitos i discrets, aixina com anells i camps són importants en la teoria de còdics.
Càlcul de diferències finitas
[editar | editar còdic]- Artícul principal → Diferència finita.
Una funció definida en un interval de sancers es diu successió. Una successió pot ser una finita o infinita. Tal funció discreta pot ser definida explícitament per una llista (si el seu domini és finito), o per una fòrmula per al seu terme n-esimo, o també pot ser donada implícitament per una relació de recurrencia o equació de diferència. Les equacions de diferència són similars a les equacions diferencials pero es reemplacen les derivades prenent la diferència entre térmens adjacents i poden ser utilisades per a aproximar equacions diferencials. Moltes interrogants i métodos de les equacions diferencials tenen les seues contrapartes per a equacions de diferències.
Geometria discreta
[editar | editar còdic]- Artícul principal → Geometria discreta.
La geometria discreta i la geometria combinatòria tracten les propietats combinatòries de coleccions discretes d'objectes geomètrics. Un antic tòpic en la geometria discreta és el recobriment del pla. La geometria computacional aplica algoritmes a problemes geomètrics.
Topología
[editar | editar còdic]- Artícul principal → Topología.
Si be la topología general és el camp de les matemàtiques que formalisa i generalisa la noció intuïtiva de "deformació contínua" dels objectes, o el procés de llímit, dona pas a molts tòpics discrets. Açò pot ser atribuït en part a l'atenció que se li dona als invariantes topològics, que prenen, per lo general, valors discrets. Entre les seues branques d'estudi es troben la topología combinatòria, topología de grafos, topología computacional i topología algebraica, entre uns atres.
Investigació Operativa
[editar | editar còdic]- Artícul principal → Investigació Operativa.
L'investigació operativa és una branca de les matemàtiques consistent en l'us de models matemàtics, estadística i algoritmes a l'objecte de realisar un procés de presa de decisions pràctiques per a negocis i atres àrees. Estos problemes poden ser, per eixemple, el repartiment de recursos per a maximizar ingressos, o agendar activitats per a minimisar riscs. Tècniques pròpies de l'investigació d'operacions inclouen programació llineal i atres àrees d'optimisació, teoria de coes, algoritmes de planificació, anàlisis de rets. L'investigació d'operacions també inclou tòpics continus com processos de Markov de temps continu, optimisació de processos, martingalas de temps continu, etc.
Teoria de jocs, teoria de la decisió, teoria d'utilitat
[editar | editar còdic]La teoria de la decisió tracta fonamentalment en identificar els valors, incertituts i atres factors rellevants en una decisió, la seua racionalitat i la decisió òptima resultant.
La teoria d'utilitats és sobre mides de la relativa satisfacció econòmica provinent del consum d'algun ben o servici.
La teoria de jocs tracta en les situacions a on l'èxit depén de les decisions d'uns atres, la qual cosa fa elegir el millor curs d'acció més complex. Tòpics inclouen la Teoria de subasta i la divisió justa.
La teoria de decisió social estudia les eleccionés.
Discretización
[editar | editar còdic]La discretización busca transformar models i equacions continus en les seues contrapartes discretes,[6] usualment per a fer càlculs més fàcilment utilisant aproximacions. L'anàlisis numèric és un important eixemple.
Vore també
[editar | editar còdic]- àlgebra llineal – l'estudi de funcions llineals relacionades.
- algoritmia – l'estudi de métodos de càlculs.
- combinatòria
- investigació d'operacions
- llògica – l'estudi del raonament
- provabilitat i cadenes de Markov
- teories de la computabilidad i de la complexitat - que tracten sobre la viabilitat i llímits dels algoritmes
- teoria de conjunts – estudi de coleccions d'objectes
- teoria de grafos
- teoria de l'informació
- teoria de números
- topología algebraica
Referències
[editar | editar còdic]- ↑ Matemàtica discreta en MathWorld.
- ↑ Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall, 2008.
- ↑ “Discrete and continuous: a fonamental dichotomy in mathematics” . Journal of Humanistic Mathematics 7 (2): 355–378. doi:.
- ↑ «Discrete Structures: What is Discrete Math?».
- ↑ Graphs on Surfaces, Bojan Mohar and Carsten Thomassen, Johns Hopkins University press, 2001
- ↑ http://ccc.inaoep.mx/emorales/Cursos/KDD/node155.html
- Archivat el 30 de abril de 2010 archivat en Wayback Machine. Discretización de Valors
Bibliografia
[editar | editar còdic]- Biggs, Norman L.. Discrete Mathematics, Oxford University Press. ISBN 978-0-19-850717-8.
- Dwyer, John (2010). An Introduction to Discrete Mathematics for Business & Computing. ISBN 978-1-907934-00-1.
- Epp, Susanna S.. Discrete Mathematics With Applications, Thomson Brooks/Cole. ISBN 978-0-495-39132-6.
- Concrete Mathematics, 2nd edició, Addison–Wesley. ISBN 0-201-55802-5.
- Grimaldi, Ralph P. (2004). Discrete and Combinatorial Mathematics: An Applied Introduction, Addison Wesley. ISBN 978-0-201-72634-3.
- Knuth, Donald E.. The Art of Computer Programming (vol. 1–4a Boxed Set), Addison-Wesley. ISBN 978-0-321-75104-1.
- (1998) Discrete Mathematics, Oxford University Press. ISBN 978-0-19-850208-1.
- Obrenic, Bojana. Practice Problems in Discrete Mathematics, Prentice Hall. ISBN 978-0-13-045803-2.
- (2000) Hand Book of Discrete and Combinatorial Mathematics, CRC Press. ISBN 978-0-8493-0149-0.
- Rosen, Kenneth H. (2007). Discrete Mathematics: And Its Applications, McGraw-Hill. ISBN 978-0-07-288008-3.
- Simpson, Andrew (2002). Discrete Mathematics by Example, McGraw-Hill. ISBN 978-0-07-709840-7.
Enllaços externs
[editar | editar còdic]- matemàtiques discretes [1] archivat en Wayback Machine. (anglés)
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Matemática discreta» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.