Nombregoj: Malsamoj inter versioj
| [nekontrolita versio] | [nekontrolita versio] |
Enhavo forigita Enhavo aldonita
e r2.6.4) (robota modifo de: fr:Liste de grands nombres |
|||
Linio 62:
La leĝo de Moore, por paroli ĝenerale, taksas, ke komputiloj duobliĝas en rapido dum proksimume ĉiuj 18 monatoj. Ĉi tiu iam kondukas homojn kredi, ke eble, komputiloj estos kapablaj solvi ian ajn matematikan problemon, ne grave kiel komplika. Sed tio malveras; komputiloj estas fundamente limigitaj per la limigoj de fiziko, kaj certaj superaj baroj al tio kion oni povas atendi povas laŭkaŭze esti formulitaj. Ankaŭ, estas certaj teoriaj rezultoj kiuj montras, ke iuj problemoj estas esence preter la atingo de plena komputa solvo, ne grave kiel pova aŭ rapida estas la kalkulado; vidu en [[N-korpa problemo]].
Inter [[1980]] kaj [[2000]], la tipaj ampleksoj de [[fiksita disko|fiksitaj diskoj]] pligrandiĝis de proksimume 10 megabajtoj (1×10<sup>7</sup>) ĝis proksimume 100 gigabajtoj (10<sup>11</sup> bitokoj). 100 gigabajta disko povas stori la donitajn nomojn de ĉiuj ses bilionaj enloĝantoj de la Tero sen uzo de [[datuma kunpremo]]. Sed kio pri vortaro-sur-disko storanta ĉiujn eblajn pasvortojn enhavantajn ĝis 40 signojn? Premisante ke ĉiu signo egalas unu bitokon, estas ĉirkaŭ 2<sup>320</sup> ĉi tiaj pasvortoj, kiu estas proksimume 2×10<sup>96</sup>.
Kompreneble, eĉ se komputiloj ne povas stori ĉiujn eblajn 40-signajn ĉenojn, ili tamen povas facile esti programitaj por ekkreadi kaj elmontradi ilin unuope. Tiel longe kiel ni ne provas stori ĉiun eligon, nia programo povis kuri nedefinite. Premisante ke moderna [[persona komputilo]] povas eligi po 1 biliono ĉenojn je sekundo, ĉi tio prenus unu biliononon de 2×10<sup>96</sup> sekundoj, aŭ 2×10<sup>87</sup> sekundojn por plenumi la taskon, kio egalas ĉirkaŭ 6 × 10<sup>79</sup> jarojn. Por kontrasto, la universo estas taksita al aĝi 13,7 bilionon (1,37×10<sup>10</sup>) jarojn. Kompreneble, komputiloj supozeble daŭros plirapidiĝi, sed la sama
Problemoj kiel ĉi tiu pli supre priskribita [[eksponenta kresko|kreskas eksponente]] en la kvanto de paŝoj kiujn ili postulas, alivorte ili estas problemoj de [[eksponenta tempo]]. Estas kaŭzo kial eksponente malfacilaj problemoj estas konsiderataj kiel ''netrakteblaj'' en komputiko: por eĉ malgrandaj nombroj kiel la 40 aŭ 50 signoj kiel en la ekzemplo, la kvanto de paŝoj de komputado postulita superas eĉ teoriajn limigojn pri homara komputa kapablo. La tradicia divido inter "facilaj" kaj "pezaj" problemoj estas tial farita inter programoj kiuj postulas kaj kiuj ne postulas eksponente pligrandiĝantajn rimedojn por plenumiĝi, vidu plu en [[komplikecaj klasoj P kaj NP]].
Tamen, ne postuli eksponente pligrandiĝantajn rimedojn ne sufiĉas por garantii komputeblecon en praktiko –
Tiaj limigoj estas avantaĝo en [[ĉifriko]], ĉar iu ajn [[ĉifro]]-rompanta maniero postulanta pli ol, oni diru, la 10<sup>120</sup> operaciojn menciitajn antaŭe neniam fareblos. Kompreneble, multaj ĉifroj jam estas rompitaj per trovo de kompetentaj teknikoj kiuj postulas nur modestajn kvantojn de komputado kaj ekspluatas malfortecan nekonaton por la ĉifra dizajnisto. Ankaŭe, multaj esploroj tra ĉiuj branĉoj de [[komputiko]] fokusas super trovi novajn, kompetentajn, bonrendimentajn solvojn al problemoj, kiuj laboras kun multe malpli grandaj rimedoj ol estas postulitaj de naïva solvado. Ekzemple, unu maniero trovi la [[plej granda komuna divizoro|plej grandan komunan divizoro]] inter du 1000-ciferaj nombroj estas komputi ĉiujn iliajn faktorojn per prov-dividado. Tiu postulus 2×10<sup>500</sup> divid-operaciojn, tro multaj por esti reale farataj. Sed la [[eŭklida algoritmo]], uzante multe pli kompetentan teknikon, prenas nur proksimume 7000 operaciojn por trovi plej grandan komunan divizoron de eĉ ĉi tiaj gigantaj nombroj.
| |||