6,258 matches
-
star. Expresia paranteză ("s") este convertită la "N"("s"). Aici se prezintă două exemplu, unul mic și informal doar cu rezultatul, și unul mai mare cu o aplicare pas cu pas a algoritmului. Imaginea de mai jos arata rezultatul rulării algoritmului Thompson pe expresia "(ε|a*b)". Ovalul roz oval corespunde lui "a", cel turcoaz corespunde lui "a*", cel verde corespunde lui "b", cel portocaliu corespunde lui "a*b", și cel albastru corespunde lui "ε". Ca un alt exemplu, imaginea arată
Algoritmul lui Thompson () [Corola-website/Science/337610_a_338939]
-
pe expresia "(ε|a*b)". Ovalul roz oval corespunde lui "a", cel turcoaz corespunde lui "a*", cel verde corespunde lui "b", cel portocaliu corespunde lui "a*b", și cel albastru corespunde lui "ε". Ca un alt exemplu, imaginea arată rezultatul algoritmului Thompson aplicat pe expresia regulată codice 1 care reprezintă un set de numere binare care sunt multipli de 3: { ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111", "00000", ... }. Partea din dreapta sus arată structura logică (arborele de
Algoritmul lui Thompson () [Corola-website/Science/337610_a_338939]
-
0110", "1001", "1100", "1111", "00000", ... }. Partea din dreapta sus arată structura logică (arborele de sintaxă) de exprimare, unde "." reprezintă concatenarea (presupusă a avea aritate variabilă); subexpresiile sunt numite a-q pentru referință. Partea stângă arată automatul finit nedeterminist care rezultă din algoritmul lui Thompson, cu stările entry (inițială) și exit (finală) a fiecărei astfel de subexpresii colorate în magenta și, respectiv, 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
Algoritmul lui Thompson () [Corola-website/Science/337610_a_338939]
-
subexpresii colorate în magenta și, respectiv, 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
Algoritmul lui Thompson () [Corola-website/Science/337610_a_338939]
-
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 expresie regulată. Algoritmul lui Glușkov este similar celui al lui Thompson
Algoritmul lui Thompson () [Corola-website/Science/337610_a_338939]
-
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 expresie regulată. Algoritmul lui Glușkov este similar celui al lui Thompson, cu eliminarea ε-tranzițiilor.
Algoritmul lui Thompson () [Corola-website/Science/337610_a_338939]
-
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 expresie regulată. Algoritmul lui Glușkov este similar celui al lui Thompson, cu eliminarea ε-tranzițiilor.
Algoritmul lui Thompson () [Corola-website/Science/337610_a_338939]
-
alte sincronii .Din nou despre lirica Anei Pop Sîrbu ,în revista Actualitatea literară, Lugoj,iulie ,2015 ,pag.5 30. Felix Nicolau , Noua muză e inteligența ,Ana Pop Sîrbu ,Versuri & Ilie Gyurcsik, Reversuri,edit.David Press Print ,Timișoara ,2014,în rev.Algoritm literar,nr 12 ,iunie ,2015,pag.10 31.Vasile Dan,Porumbița de lut, Ana Pop Sîrbu,Poesii ,editura David Press Print,Timișoara ,2015 , în rev.lit. Arca ,Arad ,nr 1-2-3 ,2016,pag.208-210 32.Florin-Corneliu Popovici,Heraldica unei panoplii po
Ana Pop Sîrbu () [Corola-website/Science/337641_a_338970]
-
de cultură, ” Coloana Infinitului ”,anul XIX,ne.97 , Timișoara , 2016 ,pag.45-47 35.Ilie Gyurcsik, Eseu de interpretare și de parafrazare,Textul de interpretat , ”Alge ”, din vol. Ana Pop Sîrbu ,Poesii, edit.David Press Print , Timișoara ,2015 , în rev.lit Algoritm literar ,nr 2 ,trim.II ,2016,pag.24 36.Florin Dochia, Cronică literara, Ana Pop Sîrbu ,Poesii ,în revista literară Urmuz, Câmpina ,nr. 7-8 ,2016, pag.7 -9 37.Ion Valentin Ceaușescu ,Ana Pop Sîrbu ,Poesii , Cronică de carte ,în
Ana Pop Sîrbu () [Corola-website/Science/337641_a_338970]
-
fi cea mai importantă problemă deschisă din domeniu. Este una dintre cele șapte selectate de , care oferă 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
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
cele șapte selectate de , care oferă 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
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
o submulțime a mulțimii {−2, −3, 15, 14, 7, −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ă
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
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 P = NP ar determina dacă problemele ce se pot verifica în timp polinomial, ca problema sumei elementelor submulțimii
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
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 NP-complete și nu se cunoaște niciun algoritm rapid pentru oricare 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
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
găsirea unei strategii perfecte în jocul de șah (pe o tablă "N" × "N") și alte jocuri de masă. Problema de a decide adevărul unei afirmații în necesită și mai mult timp. Fischer și Rabin au demonstrat în 1974 că fiecare algoritm care decide adevărul unei afirmații Presburger are un timp de execuție de cel puțin formula 1 pentru o constantă "c". Aici, "n" este lungimea afirmației Presburger. Prin urmare, se știe că problema are nevoie de un timp mai mult decât exponențial
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
n" este lungimea afirmației Presburger. Prin urmare, se știe că problema are nevoie de un timp mai mult decât exponențial pentru a fi rezolvată. Chiar și mai grele sunt, cum ar fi . Ele nu pot fi complet rezolvate de un algoritm, în sensul că pentru orice algoritm există cel puțin o intrare pentru care algoritmul nu va produce răspunsul corect; el va produce fie răspunsul greșit, fie se va opri fără a da un răspuns concludent, sau în caz contrar, se
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
urmare, se știe că problema are nevoie de un timp mai mult decât exponențial pentru a fi rezolvată. Chiar și mai grele sunt, cum ar fi . Ele nu pot fi complet rezolvate de un algoritm, în sensul că pentru orice algoritm există cel puțin o intrare pentru care algoritmul nu va produce răspunsul corect; el va produce fie răspunsul greșit, fie se va opri fără a da un răspuns concludent, sau în caz contrar, se va executa fără a se opri
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
un timp mai mult decât exponențial pentru a fi rezolvată. Chiar și mai grele sunt, cum ar fi . Ele nu pot fi complet rezolvate de un algoritm, în sensul că pentru orice algoritm există cel puțin o intrare pentru care algoritmul nu va produce răspunsul corect; el va produce fie răspunsul greșit, fie se va opri fără a da un răspuns concludent, sau în caz contrar, se va executa fără a se opri și fără a produce vreun răspuns. S-a
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
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 calculului a unui număr întreg dat. Formulată ca o problemă de decizie, ea este problema de a decide dacă intrarea are
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
pentru un graf cu "n" noduri. este problema calculului a unui număr întreg dat. Formulată ca o problemă de decizie, ea este problema de a decide dacă intrarea are un factor prim mai mic decât "k". Nu se cunoaște niciun algoritm eficient de factorizare a numerelor întregi, și acest fapt stă la baza celor mai multe sisteme criptografice moderne, cum ar fi algoritmul RSA. Problema factorizarea numerelor întregi problemă este în NP și în (și chiar în UP și co-UP). Dacă problema este
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
ea este problema de a decide dacă intrarea are un factor prim mai mic decât "k". Nu se cunoaște niciun algoritm eficient de factorizare a numerelor întregi, și acest fapt stă la baza celor mai multe sisteme criptografice moderne, cum ar fi algoritmul RSA. Problema factorizarea numerelor întregi problemă este în NP și în (și chiar în UP și co-UP). Dacă problema este NP-completă, ierarhia polinomială se va plia la primul nivel (de exemplu, NP = co-NP). Cel mai cunoscut algoritm pentru factorizarea numerelor
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
cum ar fi algoritmul RSA. Problema factorizarea numerelor întregi problemă este în NP și în (și chiar în UP și co-UP). Dacă problema este NP-completă, ierarhia polinomială se va plia la primul nivel (de exemplu, NP = co-NP). Cel mai cunoscut algoritm pentru factorizarea numerelor întregi este , al cărui timp de rulare este la factorizarea unui număr întreg pe" n "biți. Cu toate acestea, cel mai cunoscut pentru această problemă, , rulează în timp polinomial. Din păcate, acest fapt nu spune prea multe
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
nu în P” înseamnă „greu”, o presupunere cunoscută sub numele de "". Este o ipoteză comună și de o acuratețe rezonabilă din teoria complexității; cu toate acestea, ea are unele limitări. În primul rând, nu este întotdeauna adevărată în practică. Un algoritm teoretic în timp polinomial poate avea factori constanți sau exponenți extrem de mari, ceea ce l-ar face nepractic. Pe de altă parte, chiar dacă o problemă este dovedit a fi NP-completă, și chiar dacă P ≠ NP, încă ar putea exista abordări eficiente pentru
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
factori constanți sau exponenți extrem de mari, ceea ce l-ar face nepractic. Pe de altă parte, chiar dacă o problemă este dovedit a fi NP-completă, și chiar dacă P ≠ NP, încă ar putea exista abordări eficiente pentru rezolvarea problemei pe cazurile practice. Există algoritmi pentru multe NP-complete, cum ar fi , și , care pot rezolva optim multe cazuri din lumea reală asociate lor într-un timp rezonabil. (timp vs dimensiunea problemei) a acestui fel de algoritmi poate fi surprinzător de scăzută. Un exemplu este algoritmul
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
abordări eficiente pentru rezolvarea problemei pe cazurile practice. Există algoritmi pentru multe NP-complete, cum ar fi , și , care pot rezolva optim multe cazuri din lumea reală asociate lor într-un timp rezonabil. (timp vs dimensiunea problemei) a acestui fel de algoritmi poate fi surprinzător de scăzută. Un exemplu este algoritmul simplex din programarea liniară, care funcționează surprinzător de bine în practică; în ciuda faptului că are complexitate exponențială pe cel mai rău caz, el rulează pe picior de egalitate cu cei mai
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]