601 matches
-
Turing deterministă are complexitatea formula 8 în cel mai rău caz, unde formula 1 este un polinom de grad finit. Cum mașinile Turing deterministe sunt un caz particular de mașini Turing nedeterministe, orice problemă rezolvată în timp polinomial de o mașină Turing deterministă este rezolvată în timp polinomial și de o mașină Turing nedeterministă. Deci orice problemă din clasa P aparține și clasei NP. Astfel, mulțimea P este o submulțime a mulțimii NP. Formal, formula 12.
NP (teoria complexității) () [Corola-website/Science/323284_a_324613]
-
Spre deosebire de o mașină Turing deterministă, tranziția formula 1 unei mașini Turing nedeterministe este o relație între mulțimile formula 2 și formula 3 iar nu o funcție. O relație între elemente ale unei mulțimi formula 4 și elemente ale unei mulțimi formula 5 se definiște ca o submulțime a produsului cartezian
Mașina Turing nedeterministă () [Corola-website/Science/323295_a_324624]
-
formula 9 cu valori in mulțimea formula 5 este o relație cu constrângerea ca fiecare element din formula 9 să fie pus in corespondență cu exact un singur element din formula 5. Formal, formula 13 în cazul mașinilor nedeterministe și formula 14 în cazul mașinilor Turing deterministe. Astfel, în cazul mașinilor Turing nedeterministe, unei stări interne curente și unui simbol curent pe bandă le pot corespunde mai multe stări interne alternative distincte imediat următoare. efectuază, în mod nedeterminist, oricare dintre mai multele tranziții posibile pentru starea curentă
Mașina Turing nedeterministă () [Corola-website/Science/323295_a_324624]
-
Spunem că mașina nedeterministă se oprește, sau „acceptă” datele de intrare, dacă există cel puțin o secvență de execuție care duce din starea inițială la o stare acceptoare. Tot așa cum o funcție este 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ă
Mașina Turing nedeterministă () [Corola-website/Science/323295_a_324624]
-
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 fi simulată de o mașină deterministă
Mașina Turing nedeterministă () [Corola-website/Science/323295_a_324624]
-
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 fi simulată de o mașină deterministă. Chiar dacă o mașină nedeterministă poate efectua una din mai multele tranziții disponibile pentru o pereche formula 15, numărul alternativelor în fiecare pas
Mașina Turing nedeterministă () [Corola-website/Science/323295_a_324624]
-
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 fi simulată de o mașină deterministă. Chiar dacă o mașină nedeterministă poate efectua una din mai multele tranziții disponibile pentru o pereche formula 15, numărul alternativelor în fiecare pas al execuției este finit pentru că mulțimile formula 16, formula 17 și implicit formula 18 sunt finite. (Faptul că alternativele de execuție sunt
Mașina Turing nedeterministă () [Corola-website/Science/323295_a_324624]
-
este finit pentru că mulțimile formula 16, formula 17 și implicit formula 18 sunt finite. (Faptul că alternativele de execuție sunt finite permite și o ordonare a lor, astfel încât putem vorbi de prima, a doua, ș.a.m.d. cale de execuție.) Astfel, o mașină deterministă ar putea simula una nedeterministă aplicând o strategie de backtracking depth-first. Pentru că mașina deterministă revine la stări interne parcurse deja pentru ca să repornească din ele pe noi căi sugerează că execuția mașinii deterministe ia mai mult timp decât execuția mașinii nedeterministe
Mașina Turing nedeterministă () [Corola-website/Science/323295_a_324624]
-
de execuție sunt finite permite și o ordonare a lor, astfel încât putem vorbi de prima, a doua, ș.a.m.d. cale de execuție.) Astfel, o mașină deterministă ar putea simula una nedeterministă aplicând o strategie de backtracking depth-first. Pentru că mașina deterministă revine la stări interne parcurse deja pentru ca să repornească din ele pe noi căi sugerează că execuția mașinii deterministe ia mai mult timp decât execuția mașinii nedeterministe echivalente pentru aceleași date de intrare. O clasă specială de mașini Turing nedeterministe au
Mașina Turing nedeterministă () [Corola-website/Science/323295_a_324624]
-
a.m.d. cale de execuție.) Astfel, o mașină deterministă ar putea simula una nedeterministă aplicând o strategie de backtracking depth-first. Pentru că mașina deterministă revine la stări interne parcurse deja pentru ca să repornească din ele pe noi căi sugerează că execuția mașinii deterministe ia mai mult timp decât execuția mașinii nedeterministe echivalente pentru aceleași date de intrare. O clasă specială de mașini Turing nedeterministe au timpul de execuție limitat superior de un polinom a cărui variabilă este dimensiunea datelor de intrare. Acestea aparțin
Mașina Turing nedeterministă () [Corola-website/Science/323295_a_324624]
-
date de intrare. O clasă specială de mașini Turing nedeterministe au timpul de execuție limitat superior de un polinom a cărui variabilă este dimensiunea datelor de intrare. Acestea aparțin clasei de complexitate NP. Întrebarea dacă există întotdeauna o mașină Turing deterministă echivalentă care să se execute și ea în timp polinomial nu a putut fi încă răspunsă.
Mașina Turing nedeterministă () [Corola-website/Science/323295_a_324624]
-
care folosește acest limbaj trebuie să știe de la început cum se va termina propoziția, lucru explicat în carte prin abordarea timpului minim în cadrul teoremei lui Fermat. Înțelegerea sistemului scris al extratereștrilor afectează percepția Louisei asupra timpului, sugerând existența unui univers determinist în care se exercită liberul arbitru, dar fără a afecta evenimentele ulterioare. În 1999, povestirea a câștigat premiul Sturgeon, iar în 2000 premiul Nebula pentru "Cea mai bună nuveletă". Producerea golemilor nu mai este apanajul rabinilor, ci este o activitate
Împărțirea la zero (carte) () [Corola-website/Science/324322_a_325651]
-
performanța. De exemplu, arbitrarea introduce nondeterminism nelimitat, care ridică probleme cu verificarea modelului, provocând o explozie în spațiul stărilor și poate duce chiar la modele cu un număr infinit de stări. Unele modele concurente de programare includ co-procese și concurență deterministă. În aceste modele, fire de execuție de control oferă în mod explicit timpul lor de execuție fie sistemului de operare, fie altui proces.
Concurență (informatică) () [Corola-website/Science/326517_a_327846]
-
cu o unică desfășurare. Multiple-lumi, cu toate acestea, interpretează realitatea că pe un copac cu multe ramificații, în care fiecare posibil rezultat cuantic este realizat. Interpretarea multiple-lumi împăca observarea evenimentelor non-deterministe, cum ar fi dezintegrare radioactivă aleatorie, cu ecuațiile complet deterministe ale fizicii cuantice. Potrivit interpretării cu mai multe lumi a lui Hugh Everett fiecare eveniment, chiar microscopic, este un punct de cotitură; toate istoriile posibile alternative există în realitate. În 1967, Andrei Saharov a emis idea explicării asimetriei materie-antimaterie în
Interpretarea multiple-lumi () [Corola-website/Science/326273_a_327602]
-
timp real, însă nu oferă garanția că va controla distrugerea obiectelor. Cu toate ca limbaje de programare precum C# și Java au nativ un astfel de sistem, implementarea lui într-o aplicație C++ anulează tocmai avantajele utilizării C++ : un management al resurselor determinist. Utilizatorul nu poate știi niciodată când se va declanșa sistemul de eliberare a memoriei sau dacă un obiect este referențiat fără a fi utilizat (deci nu previne erori de tip memory leak ). Astfel, în C++, nu există motive viabile de
RAII () [Corola-website/Science/322811_a_324140]
-
Satan și la revolta sa împotriva Raiului din Biblie. Romanul însuși poate fi considerat o critică a religiei organizate, în conformitate cu această interpretare. Totuși, părând a păstra linia lui Dostoievski, Zamiatin a făcut din roman o critică a exceselor unei societăți deterministe, atee. Romanul folosește în mod simbolic conceptele matematice. Nava spațială a cărei construcție e supervizată de D-503 se numește INTEGRALA, el sperând ca ea să "integreze grandioasa ecuație cosmică". D-503 menționează că este profund tulburat de conceptul rădăcinii
Noi () [Corola-website/Science/322124_a_323453]
-
Socialismul științific este o formă a teoriei lui Karl Marx, simplificată și în anumite privințe modificată de către Friedrich Engels, după moartea autorului, dându-i acesteia un caracter mai determinist și făcând-o mai rigidă decât a intenționat Marx. În această variantă, materialismul istoric al lui Marx a devenit o formă a materialismului filozofic. Aceste modificări ale teoriei lui Marx, care în opinia lui Engels aveau rolul de a o
Socialism științific () [Corola-website/Science/329757_a_331086]
-
cei doi călători îi cer Navei să îi ducă pe Lumea Voalată, cea care le pune nave la dispoziție sumbalanilor în schimbul informațiilor. Aici, cei doi sunt înlocuiți cu Oach, un tânăr condamnat la lichidare pentru că nu se adaptează unei societăți deterministe. Alături de el, Nava călătorește pe Zemprad, o planetă pe care locuitorii s-au condamnat singuri la extincție, precum și pe o planetă pe care oamenii au pierdut tot ce definește un om, devenind sclavii unei entități locale. După ce termină vizitarea tuturor
Un labirint de stele () [Corola-website/Science/327059_a_328388]
-
printre inspirațiile sale majore au fost Sorel, Nietzsche, Bergson, Carlyle și Newman. Ideea de bază a lui Brzozowski a fost bazată pe conceptul de angajat intelectual social (artist). Deși a fost în favoarea materialismului istoric, el a pledat puternic în interpretarea deterministă. Leopold Stanisław Brzozowski s-a născut în 1878 în Maziarnia, un sat de lângă Chełm. În ciuda faptului că provenea dintr-o familie săracă, el a fost educat la școli private care i-au permis să aplice pentru ocuparea postului universitar la
Stanisław Brzozowski (scriitor) () [Corola-website/Science/330463_a_331792]
-
În teoria haosului, efectul fluturelui este sensibilitatea dependenței față de condițiile inițiale, în care o mică schimbare într-un loc dintr-un sistem neliniar determinist poate duce la diferențe mari într-o stare târzie. Numele efectului, inventat de Edward Lorenz, este derivat din exemplul teoretic de formare a unui uragan care este condiționat de faptul dacă un fluture îndepărtat a bătut sau nu din aripi
Efectul fluturelui () [Corola-website/Science/331768_a_333097]
-
specializă într-un domeniu și insistența de a se pronunța cu egală competența în domenii că istoria instituțiilor, drept, teologie, sociologie, filozofia “tehnologiei”, mass-media. A fost unul dintre puținii intelectuali francezi anticomuniști influențați de Marx, fiind catalogat că marxist, calvinist, determinist, tehnofob, pesimist sau anarhist. Ellul nu este ușor de clasificat și nici una din etichetele de mai sus nu îi pot descrie opera. El este mai cunoscut în Statele Unite decât în Franța, fiind recomandat de Aldous Huxley, care spunea că Ellul
Jacques Ellul () [Corola-website/Science/333227_a_334556]
-
cyan. ε ca etichetă a tranziției este omis pentru claritate — tranzițiile neetichetate sunt, de fapt, ε-tranziții. Stările de intrare și ieșire corespunzătoare expresiei rădăcină q sunt starea inițială și, respectiv, finală a automatului. Pașii algoritmului sunt după cum urmează: Un automat determinist minim echivalent este afișat mai jos. este unul din multiplii algoritmi pentru construirea de AFN-uri din expresii regulate; un algoritm mai vechi fusese dat de McNaughton și Yamada. Spre deosebire de cel al lui Thompson, transformă un automat finit într-o
Algoritmul lui Thompson () [Corola-website/Science/337610_a_338939]
-
un set de intrări, există 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
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
independente de șirul de intrare, atunci putem spune că problema poate fi rezolvată în "timp polinomial" și o plasăm în clasa P. Formal, P este definită ca o mulțime a tuturor limbajelor care poate fi decise de o mașină Turing deterministă în timp polinomial. Adică, unde și o mașină Turing deterministă în timp polinomial este o mașină Turing deterministă "M" care satisface următoarele două condiții: NP poate fi definită în mod similar, folosind mașini Turing nedeterministe (în maniera tradițională). Cu toate
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
poate fi rezolvată în "timp polinomial" și o plasăm în clasa P. Formal, P este definită ca o mulțime a tuturor limbajelor care poate fi decise de o mașină Turing deterministă în timp polinomial. Adică, unde și o mașină Turing deterministă în timp polinomial este o mașină Turing deterministă "M" care satisface următoarele două condiții: NP poate fi definită în mod similar, folosind mașini Turing nedeterministe (în maniera tradițională). Cu toate acestea, o abordare modernă a definirii clasei NP este utilizarea
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]