172 matches
-
se obțin trivial; funcția sinus, de exemplu, în 0 are derivatele 0 sau formula 19. Începând calculele de la 0, se poate obține seria simplificată Maclaurin Aceeași metodă de calcul a valorilor inițiale după coeficienți se poate utiliza ca și la funcțiile polinomiale. Coeficienții polinomiali constanți vor avea valorile Problema cu metodele descrise mai sus o reprezintă acumularea erorilor care vor face ca seria să nu mai conveargă la funcția reală. O soluție ce garantează o eroare maxim constantă este ajustarea curbei. Se
Mașină diferențială () [Corola-website/Science/322260_a_323589]
-
trivial; funcția sinus, de exemplu, în 0 are derivatele 0 sau formula 19. Începând calculele de la 0, se poate obține seria simplificată Maclaurin Aceeași metodă de calcul a valorilor inițiale după coeficienți se poate utiliza ca și la funcțiile polinomiale. Coeficienții polinomiali constanți vor avea valorile Problema cu metodele descrise mai sus o reprezintă acumularea erorilor care vor face ca seria să nu mai conveargă la funcția reală. O soluție ce garantează o eroare maxim constantă este ajustarea curbei. Se calculează un
Mașină diferențială () [Corola-website/Science/322260_a_323589]
-
O soluție ce garantează o eroare maxim constantă este ajustarea curbei. Se calculează un minim de N valori răspândite echilibrat de-a lungul intervalului pe care se efectuează calculele. Cu o tehnică de genul eliminării gaussiene, se găsește o interpolare polinomială de gradul N-1. Cu polinomul optimizat, valorile inițiale se pot calcula ca mai sus.
Mașină diferențială () [Corola-website/Science/322260_a_323589]
-
1685, în"Tratat istoric și practic de algebră" de John Wallis. În 1690, Joseph Raphson a publicat o descriere simplificată în "Analysis aequationum universalis". Raphson prezenta metoda lui Newton ca o metodă pur algebrică și limita utilizarea sa la funcții polinomiale, dar el descrie metoda în termeni de aproximări succesive"x" în loc de mai complicata secvență de polinoame utilizate de Newton. În cele din urmă, în 1740, Thomas Simpson a descris metoda lui Newton ca o metodă iterativă pentru rezolvarea ecuațiilor generale
Metoda tangentei () [Corola-website/Science/329756_a_331085]
-
aleator, în timp ce modelele de regresie se bazează pe observații multiple în seturi de date variate. În comunitatea statistică aceeași tehnică este cunoscută ca Procesul Gausian sau predicția Kolmogorov Wiener. Krigingul poate fi văzut de asemenea că o metodă de interpolare polinomiala (spline). Diferență față de krikingul clasic este prevăzută de interpretare: în timp ce "spline" este cauzată de un model minim de interpolare bazată pe structura Hilbert, Krigingul este motivat de o predicție a erorii pătratice induse, bazat pe un model aleatoriu.
Kriging () [Corola-website/Science/328110_a_329439]
-
un premiu de 1.000.000 de dolari pentru prima soluție corectă. Termenul informal "rapid", utilizat mai sus, se definește ca existența unui algoritm care rulează în . Clasa generală de întrebări pentru care un algoritm poate da răspuns în timp polinomial se numește „clasa de complexitate P”, sau simplu „P”. Pentru unele probleme însă, nu există o metodă de a găsi rapid un răspuns, dar dacă unui calculator i se prezintă un posibil răspuns, el îl poate verifica rapid. Clasa de
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
Pentru unele probleme însă, nu există o metodă de a găsi rapid un răspuns, dar dacă unui calculator i se prezintă un posibil răspuns, el îl poate verifica rapid. Clasa de astfel de probleme care pot fi "verificate" în timp polinomial se numește NP, care înseamnă „timp nedeterminist polinomial”. Fie sproblema sumei elementelor submulțimilor, un exemplu de problemă ușor de verificat, dar al cărui răspuns poate fi dificil de calculat. Dată fiind o mulțime de numere întregi, există vreo submulțime nevidă
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
de a găsi rapid un răspuns, dar dacă unui calculator i se prezintă un posibil răspuns, el îl poate verifica rapid. Clasa de astfel de probleme care pot fi "verificate" în timp polinomial se numește NP, care înseamnă „timp nedeterminist polinomial”. Fie sproblema sumei elementelor submulțimilor, un exemplu de problemă ușor de verificat, dar al cărui răspuns poate fi dificil de calculat. Dată fiind o mulțime de numere întregi, există vreo submulțime nevidă a ei ale cărei elemente au suma 0
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
10} ale cărei elemente adunate dau 0? Răspunsul este „da, pentru că submulțimea {−2, −3, −10, 15} are suma zero” și poate fi rapid verificat efectuând trei adunări; dar nu există niciun algoritm cunoscut care să găsească această submulțime în timp polinomial (există doar unul care îl găsește în timp exponențial, și care efectuează 2-n-1 încercări). Un astfel de algoritm există doar dacă P = NP; deci această problemă este în NP (rapid verificabilă) dar nu neapărat în P (rapid rezolvabilă). Soluția problemei
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
2-n-1 încercări). Un astfel de algoritm există doar dacă P = NP; deci această problemă este în NP (rapid verificabilă) dar nu neapărat în P (rapid rezolvabilă). Soluția problemei P = NP ar determina dacă problemele ce se pot verifica în timp polinomial, ca problema sumei elementelor submulțimii, pot fi și rezolvate în timp polinomial. Dacă se dovedește că P ≠ NP, ar însemna că există probleme din NP (cum ar fi problemele ) care sunt mai greu de calculat decât de verificat: ele nu
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
această problemă este în NP (rapid verificabilă) dar nu neapărat în P (rapid rezolvabilă). Soluția problemei P = NP ar determina dacă problemele ce se pot verifica în timp polinomial, ca problema sumei elementelor submulțimii, pot fi și rezolvate în timp polinomial. Dacă se dovedește că P ≠ NP, ar însemna că există probleme din NP (cum ar fi problemele ) care sunt mai greu de calculat decât de verificat: ele nu pot fi rezolvate în timp polinomial, dar o soluție se poate verifica
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
pot fi și rezolvate în timp polinomial. Dacă se dovedește că P ≠ NP, ar însemna că există probleme din NP (cum ar fi problemele ) care sunt mai greu de calculat decât de verificat: ele nu pot fi rezolvate în timp polinomial, dar o soluție se poate verifica în timp polinomial. Pe lângă importanța problemei în teoria 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
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
dovedește că P ≠ NP, ar însemna că există probleme din NP (cum ar fi problemele ) care sunt mai greu de calculat decât de verificat: ele nu pot fi rezolvate în timp polinomial, dar o soluție se poate verifica în timp polinomial. Pe lângă importanța problemei în teoria 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
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
o singură acțiune posibilă pe care o poate efectua calculatorul) și "secvențial" (efectuează acțiunile una după alta). În această teorie, clasa P constă din acele ' (definite mai jos) care pot fi rezolvate pe o mașină deterministă secvențială într-un timp polinomial în funcție de dimensiunea intrării; clasa NP constă din acele probleme de decizie ale căror soluții pozitive pot fi verificate în date fiind informațiile corecte, sau echivalent, a cărei soluție poate fi găsită în timp polinomial pe o mașină . Evident, P ⊆ NP
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
mașină deterministă secvențială într-un timp polinomial în funcție de dimensiunea intrării; clasa NP constă din acele probleme de decizie ale căror soluții pozitive pot fi verificate în date fiind informațiile corecte, sau echivalent, a cărei soluție poate fi găsită în timp polinomial pe o mașină . Evident, P ⊆ NP. Cea mai mare problemă deschisă în informatica teoretică privește relația dintre aceste două clase: Într-un sondaj efectuat în 2002 pe 100 de cercetători, 61 credeau că răspunsul este nu, 9 credeau că este
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
ca problema să fie rezolvată sau ca răspunsul să fie da. Pentru a aborda problema P = NP, este util conceptul de NP-completitudine. Problemele NP-complete sunt o mulțime de probleme la care poate fi redusă orice altă problemă NP în timp polinomial, și ale căror soluții pot fi verificate în timp polinomial. Adică, orice problemă NP poate fi ușor transformată în oricare dintre problemele NP-complete. Informal, o problemă NP-completă este o problemă NP care este cel puțin la fel de „grea” ca și orice
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
da. Pentru a aborda problema P = NP, este util conceptul de NP-completitudine. Problemele NP-complete sunt o mulțime de probleme la care poate fi redusă orice altă problemă NP în timp polinomial, și ale căror soluții pot fi verificate în timp polinomial. Adică, orice problemă NP poate fi ușor transformată în oricare dintre problemele NP-complete. Informal, o problemă NP-completă este o problemă NP care este cel puțin la fel de „grea” ca și orice altă problemă din NP. Problemele NP-tari sunt cele care sunt
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
NP-completă este o problemă NP care este cel puțin la fel de „grea” ca și orice altă problemă din NP. Problemele NP-tari sunt cele care sunt cel puțin la fel de grele ca problemele NP, adică toate problemele NP pot fi reduse (în timp polinomial) la ele. Problemele NP-grele nu sunt neapărat în NP, adică nu este nevoie ca ele să aibă soluții verificabile în timp polinomial. De exemplu, este NP-completă conform , deci "orice" instanță a "oricărei" probleme din NP poate fi transformată mecanic în
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
care sunt cel puțin la fel de grele ca problemele NP, adică toate problemele NP pot fi reduse (în timp polinomial) la ele. Problemele NP-grele nu sunt neapărat în NP, adică nu este nevoie ca ele să aibă soluții verificabile în timp polinomial. De exemplu, este NP-completă conform , deci "orice" instanță a "oricărei" probleme din NP poate fi transformată mecanic în timp polinomial într-o instanță a problemei satisfiabilității booleene. Problema satisfiabilității este una din multele astfel de probleme NP-complete. Dacă orice problemă
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
ele. Problemele NP-grele nu sunt neapărat în NP, adică nu este nevoie ca ele să aibă soluții verificabile în timp polinomial. De exemplu, este NP-completă conform , deci "orice" instanță a "oricărei" probleme din NP poate fi transformată mecanic în timp polinomial într-o instanță a problemei satisfiabilității booleene. Problema satisfiabilității este una din multele astfel de probleme NP-complete. Dacă orice problemă NP-completă este în P, atunci ar rezulta că P = NP. Din păcate, s-a demonstrat că multe probleme importante sunt
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
dintre ele. Doar pe baza definiției nu este evident că există probleme NP-complete; dar o problemă NP-completă trivială ar putea fi formulată astfel: dată fiind o descriere a unei mașini Turing M care în mod garantat se oprește în timp polinomial, există o intrare de dimensiuni polinomiale pe care M le va accepta? Ea este în NP deoarece (dată fiind o intrare) este simplu de verificat dacă M acceptă intrarea simulând funcționarea mașinii Turing M; este NP-completă deoarece verificatorul oricărei instanțe
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
nu este evident că există probleme NP-complete; dar o problemă NP-completă trivială ar putea fi formulată astfel: dată fiind o descriere a unei mașini Turing M care în mod garantat se oprește în timp polinomial, există o intrare de dimensiuni polinomiale pe care M le va accepta? Ea este în NP deoarece (dată fiind o intrare) este simplu de verificat dacă M acceptă intrarea simulând funcționarea mașinii Turing M; este NP-completă deoarece verificatorul oricărei instanțe de problemă din NP poate fi
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
este în NP deoarece (dată fiind o intrare) este simplu de verificat dacă M acceptă intrarea simulând funcționarea mașinii Turing M; este NP-completă deoarece verificatorul oricărei instanțe de problemă din NP poate fi codificat ca mașină Turing M de timp polinomial care primește ca intrare soluția de verificat. Apoi întrebarea dacă instanța de problemă primește un răspuns „da” sau un răspuns „nu” se determină prin verificarea existenței unei intrări valide. Prima problemă naturală demonstrată a fi NP-completă a fost . Cum s-
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
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 timp exponențial. Printre exemple se numără găsirea unei strategii perfecte în jocul de șah (pe o tablă "N" × "N") și alte jocuri de masă. Problema
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
izomorfismului grafurilor este în P, NP-completă, sau NP-intermediară. Răspunsul nu este cunoscut, dar se crede că problema cel puțin nu este NP-completă. Dacă izomorfismul grafurilor ar fi NP-completă, s-ar plia la al doilea nivel. Deoarece se crede că ierarhia polinomială nu se pliază la niciun nivel finit, se crede că izomorfismul grafurilor nu este o problemă NP-completă. Cel mai bun algoritm pentru această problemă, datorat lui și , a rulat timp de 2 pentru un graf cu "n" noduri. este problema
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]