Matematika diskretu

Wikipedia, Entziklopedia askea
Hona jauzi: nabigazioa, Bilatu

Matematika diskretua multzo zenbakigarriak aztertzen dituen matematikaren adarra da, adibidez, zenbaki osoak. Balore separatuak lantzen ditu (ez jarraituak) eta konputazioaren zientzietarako ezinbestekoa da.

Matematika jarraituetan ez bezala, limitearen nozioa ez da existitzen. Hau da, aldagai bat 5 edo 6 izan daiteke, baina ez zaio 5-i eskuinetik edo ezkerretik hurbilduko. Hortaz, funtzioek osatuko dituzten grafikoak ez dira lerro batez adieraziak izango, baizik eta infinitu puntuz.

Multzo finitu edo infinituak landu ditzake, matematika jarraituak bezala. Matematika diskretuei buruzko ikerketak asko garatu dira XX. mendeko 50. hamarkadatik aurrera, besteak beste ordenagailuen sorrerari esker, haien informazioa bit diskretuetan gordea baita.

Historia[aldatu | aldatu iturburu kodea]

Matematika diskretuak, ebatzi gabeko hainbat problemekin egin du topo historian zehar. Besteak beste, Grafoen teoria eta Königsberg-eko zazpi zubiak. Grafoen teorian eginiko ikerkuntza ugari, Lau koloreen teorema frogatu nahian sortu ziren. Zeina, lehenengo deskribapenetik ehun urtetara frogatu zen. Königsberg-eko zazpi zubietako ebazkizuna, Leonhard Eulerren problema klasikoetako bat da.

Logikan, arazo irekiko David Hilbert-en zerrendaren bigarren arazoa, aritmetikaren axiomak sendoak direla probatzea zen. Gödel-en osotasun-ezaren bigarren teoremak hau posiblea ez dela egiaztatu zuen 1931n, behintzat aritmetikaren barruan. Hilbert-en hamargarren arazoa, koefiziente osoekin emandako polinomio diofantikoak soluzio osoa duen zehaztea zen. 1970ean, Yuri Matiyasevich-ek hori egitea ezinezkoa dela probatu zuen.

Bigarren Mundu Gerran Alemaniako kodeak deszifratzeko beharrak bide eman zien kriptografiako aurrerapenei eta zientzia konputazional teorikoari, Ingalaterran garatutako lehen konputagailu elektroniko, digital eta programagarriarekin. Aldi berean, eskakizun militarrek aurrerapenak ekarri zituzten ikerkuntza eragilean. Gerra Hotzak garrantzia izan zuen kriptografian, eta indarreko mantendu zuen, kriptografia asimetrikoan aurrerapenak eginez.

Gaur egun, informatikaren teoriako arazo ireki ospetsuenetako bat konplexutasuneko klaseen arazoa,  "P = NP", da. Clay Mathematics Institute-ak milioi bat dolarreko saria eskaini du lehen frogapen zuzenerako, beste 6 arazo gehiagotarako sariekin batera.

Matematika Diskretuko Topikoak[aldatu | aldatu iturburu kodea]

Konplexutasunak, algoritmo bat exekutatzeko behar duen denbora azaltzen du.

Informatika Teorikoa[aldatu | aldatu iturburu kodea]

Informatikaren teoriak, matematika diskretuko konputazioari lotutako hainbat atal aipagarri barneratzen ditu. Hau, oso erlazionatuta dago grafoen eta logikaren teoriekin.

Informatikaren teoriaren barnean, algoritmoen teoria ageri da problema matematikoei erantzuna bilatzeko. Konputagarritasunak, konputagarri izan daitekeena aztertzen du eta logikarekin harreman handia du; konplexutasunak bestalde, kalkulu bat egiteko behar den denbora aztertzen du.

Automaten teoria, hizkera formalak eta sistemen dinamika, konputagarritasunarekin erlazionatzen dira batez ere.

Geometria konputazionalak algoritmotak ezartzen ditu problema geometrikoetan; irudien analisi digitalak bestalde, irudien errepresentazioetan ezartzen ditu.

Informatikaren teoriak, informatika jarraituaren topikoak ere barneratzen ditu.

Azaldutako kodeketa, informazioaren teorian aiderazitako hitz bat da.

Informazioaren Teoria[aldatu | aldatu iturburu kodea]

Informazioaren teoria, informazioaren zenbaketarekin nahasten da. Honen oso antzekoa kodeketaren teoria da; zeina transmisioetarako metodoen eta datu fidagarri eta eraginkorren biltegiratzearen diseinuetarako erabilia den.

Teoria honek, seinale analogo, kodifikazio analogo eta zifratu analogo topikoak barneratzen ditu.

Multzo-Teoria[aldatu | aldatu iturburu kodea]

Artikulu nagusia: Multzo teoria

Multzo-teoria multzoak, elementu ezberdinen bildumak alegia, aztertzen dituen matematikaren adarra da. Multzo bat, objetu sorta da (zenbaki bakoiti guztien multzo infinitua adibidez).

Multzo partzialki ordenatuek eta beste erlazioak dituztenek, beste hainbat arlotan dituzte aplikazioak.

Matematika diskretuan, multzo zenbakigarriak (multzo finituak barne) dira aztergai nagusia. Multzo teoria, Georg Cantorren lanarekin hasi zela esan ohi da.

Multzo infinituen teoriaren garapenik sakonena matematika diskretuaren helmenetik kanpo dago.

Konbinatoria[aldatu | aldatu iturburu kodea]

Artikulu nagusia: Konbinatoria

Konbinatoria kontaketa-ebazkizunak aztertzen dituzten teknika matematikoen multzoa da. Zehatzago, konbinatoriak propietate berdinak dituzten elementuak zenbatu eta elementu hauen multzoen ezaugarriak aztertzen ditu.

Konbinatoria zenbatzailea, objetuen "zenbaketaz" arduratzen da.

Konbinatoria analitikoa, estruktura konbinatorioen zenbaketaz arduratzen da, analisi konplexu eta probabilitatearen teoriako tresnak erabiliz.

Diseinuaren teoria, diseinu konbinatorioen ikerketan datza.

Grafo Teoria[aldatu | aldatu iturburu kodea]

Artikulu nagusia: Grafo Teoria

Lehen konbinatoriaren atal bat izango balitz bezala hartzen zen; baina asko eboluzionatu duenez, materia ezberdin baten antzera hartu daiteke.

Zenbakien Teoria[aldatu | aldatu iturburu kodea]

Ulam-en kiribilak, pixel beltz bakoitzean, zenbaki lehen bat erakusten du. Diagrama honek, zenbaki lehenen banaketaren gaineko pista posible bat erakusten du.

Artikulu nagusia: Zenbakien Teoria

Zenbakien teoria zenbakiak (batez ere zenbaki osoak) eta haien arteko erlazioak aztertzen dituen zientzia da. Hainbat aplikazio ditu Kriptografian, Kriptoanalisian eta Kriptologian, batez ere zenbaki lehenei dagokienean.  Zenbaki-teoriaren beste alderdi bat zenbakien teoria geometrikoan datza. Zenbakien teoria analitikoan ere matematika jarraituaren beste teknika batzuk erabiltzen dira.

Aljebra[aldatu | aldatu iturburu kodea]

Artikulu nagusia: Aljebra Abstraktua

Estruktura aljebraikoak diskretuki zein jarraiki gertatzen dira. Aljebra diskretuaren adibide gisa: Booleren aljebra, zirkuitu digitalen diseinuan eta programazioan erabiltzen dena; aljebra erlazionala, datu baseetan erabilia; talde finitu edo diskretuez gain eraztun eta eremuak ere  garrantzitsuak dira kodeen teorian.

Diferentzia Finituen Kalkulua[aldatu | aldatu iturburu kodea]

Puntu-tarte batean definitutako funtzioa segida deitzen da.Segida bat finitua zein infinitua izan daiteke. Funtzio diskretu hori zerrenda batez definitu daiteke (bere domeinua mugatua bada) edo bere n-garren gairako formula batez, edota funtzio errekurtsibo batez edo diferentzia ekuazio batez. Diferentziazko ekuazioak ekuazio diferentzialen antzekoak dira baina deribatuak ordezkatzen dira alboko terminoen arteko desberdintasuna hartuz eta ekuazio diferentzialak hurbiltzeko erabil daitezke. Ekuazio diferentzialen galdetzaile eta metodo askok bere ordainak dituzte desberdintasun-ekuazioetarako.

 Geometria konputazionalak algoritmoak ezartzen dizkie objektu geometrikoen irudikapenei.

Geometria[aldatu | aldatu iturburu kodea]

Geometria diskretuak eta geometria konbinatorialak objetu geometrikoen bilduma diskretuen propietate konbinatorioak aztertzen dituzte. Geometria diskretuaren topikoetako bat planoaren estaldura  da. Geometria konputazionalak problema geometrikoei algoritmoak ezartzen dizkie.

Topologia[aldatu | aldatu iturburu kodea]

Artikulu nagusia: Topologia

Askotan, topologia jarraitasunari lotzen zaio baina bere arlo batzuk diskretuak dira, hala nola Topologia konputazionala, grafoak, konbinatoria… Izan ere, arlo hauek aztertzeko matematika jarraituko topologiako printzipioak erabil daitezke, baina espazio diskretu batean (adibidez, zenbaki osoen multzoan zenbaki errealen multzoan ordez)

Ikerkuntza Eragilea[aldatu | aldatu iturburu kodea]

Artikulu nagusia: Ikerkuntza Eragilea

Erabakiak hartzeko erabiltzen da, eta horretarako estatistika, modelizazioa, analisi matematikoa eta grafoen teoria erabiltzen ditu. 2. mundu gerlan garatu zen bereziki, estrategia militarrak garatzeko.

Gaur egun, industrian eta ekonomian erabiltzen da batez ere, energia gutxiago gastatzeko estrategiak gauzatzeko, adibidez. Horrez gain, ordenagailuen kalkulu potentzia handiari esker asko garatu da azken urte hauetan.

Joko Teoria, Erabakien Teoria eta Baliagarritasunaren Teoria[aldatu | aldatu iturburu kodea]

Joko teoria lehia batean kasu arrakastatsu bat gertatzea besteek egiten dituzten ekintzen araberakoa denean erabiltzen da. Horren araberako estrategia hoberena hautatzea du helburu, irabazteko asmoarekin, estrategia eta zorizko joko askotan erabilia da, hala nola xakea, edo pokerra. Aitzinamendu handia ukan du Bigarren Mundu Gerran, estrategia militarrak garatzeko erabiltzen baitzen.

Erabakien teoriak, erabaki bat hartzerakoan, zer faktore kontutan hartzen ditugun aztertzen du, eta hautu egokia izan den ere bai.

Erabaki sozialen teorian, pertsonen hautu pertsonalek, interesek edo ongizatearen araberako erabakiek, erabaki kolektibo (edo sozial) bat nola gauzatzen ahal duten analizatzen da. Gizartearen arloan erabilia da, hauteskundeetan edo ongizatearen teorian adibidez.

Baliagarritasunaren teoriak bezero batek zerbait kontsumitzerakoan ukango duen asetzea neurtzen duen funtzio bat aztertzen du.

Diskretizazioa[aldatu | aldatu iturburu kodea]

Uhin baten diskretizazioa.

Diskretizazioa, elementu jarraiak, elemetu diskretu bilakatzea da, hau da, funtzio, aldagai edo ekuazio jarrai bat zatituko du, balore kontagarriak kontutan hartuz. Adibidez ondoko irudian ikusten den moduan momentu ezberdinetako balioa edo balio hurbilena (kasu honetan zenbaki oso hurbilena) hartzen du. Uhin jarraitu batetik, puntu segida batera pasatzen gara.


Erreferentziak[aldatu | aldatu iturburu kodea]

  • Norman L. Biggs (2002-12-19). Discrete Mathematics. Oxford University Press. ISBN 978-0- 19-850717-8.
  • John Dwyer (2010). An Introduction to Discrete Mathematics for Business & Computing. ISBN 978-1-907934-00-1.
  • Susanna S. Epp (2010-08-04). Discrete Mathematics With Applications. Thomson Brooks/Cole. ISBN 978-0-495-39132-6.
  • Ronald Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics.
  • Ralph P. Grimaldi (2004). Discrete and Combinatorial Mathematics: An Applied Introduction. Addison Wesley. ISBN 978-0-201-72634-3.
  • Donald E. Knuth (2011-03-03). The Art of Computer Programming, Volumes 1-4a Boxed Set. Addison-Wesley Professional. ISBN 978-0-321-75104-1.
  • Jiří Matoušek; Jaroslav Nešetřil (1998). Discrete Mathematics. Oxford University Press. ISBN 978-0-19-850208-1.
  • Obrenic, Bojana (2003-01-29). Practice Problems in Discrete Mathematics. Prentice Hall. ISBN 978-0-13-045803-2.
  • Kenneth H. Rosen; John G. Michaels (2000). Hand Book of Discrete and Combinatorial Mathematics. CRC PressI Llc. ISBN 978-0-8493-0149-0.
  • Kenneth H. Rosen (2007). Discrete Mathematics: And Its Applications. McGraw-Hill College. ISBN 978-0-07-288008-3.
  • Andrew Simpson (2002). Discrete Mathematics by Example. McGraw-Hill Incorporated. ISBN 978-0-07-709840-7.
  • Veerarajan, T.(2007), Discrete mathematics with graph theory and combinatorics, Tata Mcgraw Hill