334 matches
-
târziu printr-un serializer construct ([Hewitt and Atkinson 1977, 1979] and [Atkinson 1980]). Primele modele de calcul ("e.g." Turing machines, Post productions, the lambda calculus, "etc.") au fost bazate pe matematică și folosesc o stare globală să reprezinte un pas computațional (mai târziu generalizat în [McCarthy and Hayes 1969] și [Dijkstra 1976]. Starea globală a fost continuată în teoria automatelor pentru mașinile cu stări finite și mașinile cu stive push down. Astfel de automate nondeterministice au proprietatea ca nondeterminism nelegat. Adică
Modelul Actor () [Corola-website/Science/322835_a_324164]
-
aleatorii lungi de aproximativ 33 de caractere, întotdeauna începând cu cifra 1, de forma "175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W". Utilizatorii bitcoin pot deține multiple adrese, și de fapt pot genera noi adrese fără limite practice, deoarece generarea unei noi adrese necesită relativ puțină putere computațională, echivalentul la a genera o pereche de chei public/private, și nu necesită niciun contact cu vreun nod din rețea. Crearea de adrese de unică folosință ajută la menținerea anonimatului utilizatorului. O tranzacție reprezintă un transfer de valoare între portofele
Bitcoin () [Corola-website/Science/322707_a_324036]
-
un caz particular de relație, o mașină deterministă este un caz particular de mașină nedeterministă. Astfel, mulțimea tuturor mașinilor Turing deterministe este o submulțime a mulțimii tuturor mașinilor Turing nedeterministe. Cu toate acestea, mașinile Turing nedeterministe nu au o „putere computațională” mai mare decât mașinile Turing deterministe. Adică nu există limbaje care să fie acceptate de o mașină nedeterministă și să nu se poată specifica o mașină deterministă care să accepte același limbaj. Aceasta se intâmplă pentru că orice mașină nedeterministă poate
Mașina Turing nedeterministă () [Corola-website/Science/323295_a_324624]
-
o denumire generică pentru orice protocol în care două entități cunosc în prealabil o parolă și o folosesc ca bază pentru sutentificare. Există două feluri de scheme de autentificare cu parolă: slabe și puternice. Cele slabe necesită mai puțin efort computațional, designul este mai simplu, iar implementarea este mai ușoară, ceea ce le face mai potrivite pentru medii cu resurse limitate. De notat că această clasificare nu înseamnă neapărat că cele slabe sunt mai ușor de spart. Pachetul PAP inclus într-un
PAP () [Corola-website/Science/334506_a_335835]
-
echivalentă cu un automat cu stivă modificat prin relaxarea constrângerii de last-in-first-out a stivei acestuia. (Interesant este că această relaxare aparent minoră permite mașinii Turing să execute o largă varietate de calcule, astfel încât ea poate servi ca model pentru capabilitățile computaționale ale tuturor software-urilor moderne.) Mai exact, o mașină Turing constă din: De notat că toate componentele mașinii sunt finite; doar cantitatea nelimitată de bandă îi dă acesteia un volum nelimitat de spațiu. O mașină Turing este de obicei definită
Mașină Turing () [Corola-website/Science/299502_a_300831]
-
un 6-tuplu M = (Q,Γ,s,b,F,δ), unde Definițiile din literatura de specialitate diferă uneori, pentru a face demonstrațiile mai ușoare sau mai clare, dar aceasta se face întotdeauna de așa natură încât mașina să-și păstreze puterea computațională. De exemplu, schimbarea mulțimii {L,R} în {L,R,S}, unde S permite mașinii să stea pe aceeași celulă a benzii în loc să se deplaseze la stânga sau la dreapta, nu mărește puterea computațională a mașinii. O mașină Turing cu k benzi
Mașină Turing () [Corola-website/Science/299502_a_300831]
-
așa natură încât mașina să-și păstreze puterea computațională. De exemplu, schimbarea mulțimii {L,R} în {L,R,S}, unde S permite mașinii să stea pe aceeași celulă a benzii în loc să se deplaseze la stânga sau la dreapta, nu mărește puterea computațională a mașinii. O mașină Turing cu k benzi poate fi și ea descrisă ca un 6-tuplu M = (Q,Γ,s,b,F,δ), unde De notat că o mașină Turing cu k benzi nu este mai puternică decât o mașină
Mașină Turing () [Corola-website/Science/299502_a_300831]
-
intrare pentru fiecare combinație simbol-stare atunci mașina este o mașină Turing deterministă (MTD). Dacă tabela de acțiuni conține mai multe intrări pentru cel puțin o combinație simbol-stare atunci mașina este o mașină Turing nedeterministă (MTND sau MTN). Cele două sunt computațional echivalente, adică orice MTND se poate transforma într-o MTD (și "invers"). Fiecare mașină Turing calculează o funcție parțială calculabilă din șirurile de intrare peste alfabetul ei. Din acest punct de vedere, se comportă exact ca un calculator cu un
Mașină Turing () [Corola-website/Science/299502_a_300831]
-
în general, nedecidabilă în lucrarea originală a lui Turing. Teorema lui Rice arată că orice întrebare netrivială despre comportamentul sau ieșirea unei mașini Turing este nedecidabilă. Dacă în definiția "mașinii Turing universale" includem orice mașină Turing care simulează un model computațional Turing-complet, și nu doar mașinile Turing care simulează direct alte mașini Turing, o mașină Turing universală poate fi relativ simplă, folosind doar câteva stări și câteva simboluri. De exemplu, e nevoie doar 2 stări, deoarece se cunoaște o mașină Turing
Mașină Turing () [Corola-website/Science/299502_a_300831]
-
stări și câteva simboluri. De exemplu, e nevoie doar 2 stări, deoarece se cunoaște o mașină Turing universală de 2×18 (adică 2 stări, 18 simboluri). De ceva timp, cele mai mici mașini Turing universale cunoscute, care simulau un model computațional numit sistem de etichetare, avea următoarele numere de stări și simboluri : 2×18, 3×10, 4×6, 5×5, 7×4, 10×3, 22×2. (De exemplu, vezi Minsky Cap 14.8.1 p. 277 pentru o descriere detaliată a
Mașină Turing () [Corola-website/Science/299502_a_300831]
-
(n. 16 iunie 1954, Craiova) este critic de artă, critic de teatru, critic literar, publicist, eseist și traducător român. Este lusitanist, specialist în psihologie și lingvistică computațională. Debutul său în critică a avut loc încă din clasa a X-a, în revista liceului «Frații Buzești» din Craiova, publicând de atunci o serie de articole și studii de specialitate în reviste din țară și din străinătate. Treptat, eseurile
Dan Caragea () [Corola-website/Science/308610_a_309939]
-
responsabil pentru Departamentul de Semantică, OCS S.A., Madrid. Creator al e-lexis, bază de date integrată în motoare de indexare și căutare (Excalibur, azi Convera), realizată pentru a permite căutarea simultană în zece limbi. 1999 - 2000, director al Departamentului de Lexicografie Computațională, SystemHouse, Lda., Lisabona. 2000 - 2001, director al Departamentului de Științe ale Informației, Áquila - GED, Lda., Lisabona. Creator al sistemului ATHOS destinat arhivelor virtuale complexe. Din 2003, director fondator al firmei Cyberlex; creator lingvistic al variantei spaniole și portugheze al programului
Dan Caragea () [Corola-website/Science/308610_a_309939]
-
deci inițial aceasta a părut a fi o problemă mică. Într-adevăr, dublarea repetată a numărului de pași conduce în cele din urmă la o aproximare de 3,76001. Pentru aceasta este însă nevoie de 2 componente, cu un cost computațional mare pentru această precizie redusă; urmărirea unei precizii mai mari poate face pașii atât de mici încât precizia să ajungă să fie limitată de precizia reprezentării în virgulă mobilă. O abordare mai bună este înlocuirea aproximării funcției cu linii orizontale
Integrală () [Corola-website/Science/298291_a_299620]
-
ultima valoare fiind împărțite la doi, și înmulțește totul cu lățimea pasului. Aproximarea integralei este imediat îmbunătățită la 3,76925, evident mai precis. Mai mult, pentru a obține valoarea 3,76000 sunt necesare 2 componente, necesitând substanțial mai puțin efort computațional decât metoda dreptunghiului. Metoda lui Romberg elaborează cu succes metoda dreptunghiului. Întâi, lungimile pașilor sunt reduse incremental, dând trapeze de aproximare notate cu "T"("h"), "T"("h"), și așa mai departe, unde "h" este jumătate din "h". Pentru fiecare nou
Integrală () [Corola-website/Science/298291_a_299620]
-
funcției). Polinomul Lagrange de interpolare {"h","T"("h")} = {(4.00;6,128), (2,00;4,352), (1,00;3.908)} este 3,76+0,148"h", dând valoarea extrapolată 3,76 în "h" = 0. Cuadratura gaussiană necesită adesea un efort computațional considerabil mai mic pentru o precizie superioară. În acest exemplu, se pot calcula valorile funcției în doar două puncte "x", ±⁄, apoi se dublează fiecare valoare și se însumează pentru a obține răspunsul numeric exact. Explicația pentru acest succes constă în
Integrală () [Corola-website/Science/298291_a_299620]
-
oricât de mari sunt, deoarece nu necesită niciodată un număr de pași mai mare decât de cinci ori numărul de cifre (în bază 10) al celui mai mic întreg. Gabriel Lamé a demonstrat aceasta în 1844, marcând începutul teoriei complexității computaționale. În secolul al XX-lea s-au dezvoltat metode de îmbunătățire ale eficienței algoritmului. Algoritmul lui Euclid calculează cel mai mare divizor comun (CMMDC) a două numere naturale "a" și "b". Cel mai mare divizor comun "g" este cel mai
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
lui Shor, metoda de factorizare a lui Dixon și factorizarea Lenstra cu curbe eliptice. Algoritmul lui Euclid poate fi utilizat eficient pentru găsirea CMMDC în aceste cazuri. Factorizarea cu fracții continue utilizează fracțiile continue, determinate folosind algoritmul lui Euclid. Eficiența computațională a algoritmului lui Euclid a fost mult studiată. Această eficiență poate fi descrisă de numărul de pași ai algoritmului înmulțit cu costul computațional al fiecărui pas. După cum a arătat Gabriel Lamé pentru prima oară în 1844, numărul de pași necesar
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
CMMDC în aceste cazuri. Factorizarea cu fracții continue utilizează fracțiile continue, determinate folosind algoritmul lui Euclid. Eficiența computațională a algoritmului lui Euclid a fost mult studiată. Această eficiență poate fi descrisă de numărul de pași ai algoritmului înmulțit cu costul computațional al fiecărui pas. După cum a arătat Gabriel Lamé pentru prima oară în 1844, numărul de pași necesar pentru terminarea calculului nu este niciodată mai mare decât numărul "h" de cifre (în baza 10) al celui mai mic număr. Întrucât costul
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
al fiecărui pas. După cum a arătat Gabriel Lamé pentru prima oară în 1844, numărul de pași necesar pentru terminarea calculului nu este niciodată mai mare decât numărul "h" de cifre (în baza 10) al celui mai mic număr. Întrucât costul computațional al fiecărui pas este și el de ordinul lui "h", costul total crește ca "h". Numărul de pași necesari pentru calculul CMMDC a două numere naturale, "a" și "b", se poate nota cu "T"("a", "b"). Dacă "g" este CMMDC
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
lor cele mai mici sunt "F" și "F". Cea mai mică valoare a lui "a" este deci cea cu "q" = 1, de unde "a" = "b" + "r" = "F" + "F" = "F". Această demonstrație, publicată de Gabriel Lamé în 1844, reprezintă începuturile teoriei complexității computaționale, fiind și prima aplicație practică a șirului lui Fibonacci. Acest rezultat este suficient pentru a arăta că numărul de pași din algoritmul lui Euclid nu poate fi niciodată mai mare decât de cinci ori numărul cifrelor sale (în bază 10
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
formula aproximativă pentru "T"("a") în această ecuație rezultă o estimare a lui "Y"("n") La fiecare pas "k" al algoritmului lui Euclid, se calculează câtul "q" și restul "r" pentru o pereche dată de întregi "r" și "r" Costul computațional al fiecărui pas este asociat cu găsirea lui "q", întrucât restul "r" poate fi calculat rapid din "r", "r", and "q" Costul computațional al împărțirii numerelor pe "h" biți scalează ca "O"("h"("ℓ"+1)), unde "ℓ" este lungimea câtului
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
se calculează câtul "q" și restul "r" pentru o pereche dată de întregi "r" și "r" Costul computațional al fiecărui pas este asociat cu găsirea lui "q", întrucât restul "r" poate fi calculat rapid din "r", "r", and "q" Costul computațional al împărțirii numerelor pe "h" biți scalează ca "O"("h"("ℓ"+1)), unde "ℓ" este lungimea câtului. Pentru comparație, algoritmul original al lui Euclid bazat pe scăderi poate fi mult mai lent. O singura împărțire de întregi este echivalentă cu
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
cea de împărțire, mai ales în cazul numerelor mari, algoritmul lui Euclid bazat pe scăderi este competitiv cu cel bazat pe împărțiri. Acest aspect este exploatat de versiunea binară a algoritmului lui Euclid. Combinarea numărului estimat de pași cu calculul computațional estimat al fiecărui pas arată că algoritmul lui Euclid are o creștere pătratică ("h") în funcție de numărul de cifre "h" al celor două numere inițiale "a" și "b". Fie "h", "h", ..., "h" numărul de cifre ale resturilor succesive "r", "r", ..., "r
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
calculabilității, o dovadă în oricare sens ar avea profunde implicații în matematică, criptografie, algoritmică, inteligență artificială, teoria jocurilor, procesarea multimedia, filosofie, economie și în multe alte domenii. Relația între clasele de complexitate P și NP este studiată în teoria complexității computaționale, ramura care tratează resursele de calcul necesare pentru rezolvarea unei probleme date. Cele mai comune astfel de resurse sunt timpul (numărul de pași necesari rezolvării unei probleme) și spațiul (cantitatea de memorie necesară rezolvării unei probleme). În astfel de analize
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
la altele, și, într-un anume sens, sunt „aceeași problemă”. Deși nu se cunoaște dacă P = NP, se cunosc probleme care sunt în afara P. Un număr de probleme succinte (probleme care nu operează pe intrări normale, ci pe o descriere computațională a intrării) sunt cunoscute a fi . Pentru că se poate demonstra că P ≠ , aceste probleme sunt în afara P, și deci necesită timp mai mult decât polinomial. În fapt, prin , ele nu pot fi rezolvate în mod semnificativ mai rapid decât în
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]