10 Probleme algoritmice Cu toate acestea, algoritmii Solve - dummies

Algoritmii au fost într-adevăr de-a lungul secolelor, așa că ați crede că oamenii de știință ar fi descoperit și rezolvat fiecare algoritm până acum. Din păcate, contrariul este adevărat. Rezolvarea unui anumit algoritm prezintă deseori câteva întrebări pe care algoritmul nu le rezolvă și care nu păreau aparente până când cineva nu a venit cu soluția.

Algoritmii reprezintă o serie de pași folosiți pentru a rezolva o problemă și nu ar trebui să le confundați cu alte entități, cum ar fi ecuațiile. Un algoritm nu este niciodată o soluție în căutarea unei probleme. Nimeni nu ar crea o serie de pași pentru a rezolva o problemă care încă nu există (sau nu poate exista niciodată).

Această listă se referă la probleme algoritmice care ar servi unui scop dacă cineva va găsi o soluție pentru ei.

Rezolvarea căutărilor de text

Multe căutări de text implică utilizarea unor expresii regulate - un fel de stenogramă care îi spune computerului ce să găsească. Gramatica utilizată pentru expresia regulată depinde de limbă sau de aplicație, dar găsiți expresii regulate utilizate în mai multe locuri, inclusiv procesoare de text, aplicații de e-mail, dialoguri de căutare și în tot felul de alte locuri unde trebuie să furnizați o căutare precisă termeni pentru o serie de elemente de text.

Una din problemele actuale cu expresii regulate este că se pare că fiecare mediu de aplicații are un set similar de reguli, dar cu diferențe suficiente pentru a face din greu crearea unui termen de căutare. Problema generalizată a înălțimii stea încearcă să descopere dacă există o sintaxă generalizată a expresiei regulate. Dacă da, algoritmul rezultat ar face posibil ca cineva să învețe o singură metodă de a crea expresii regulate pentru a efectua căutări.

Diferențierea cuvintelor

Când lucrați cu caractere, un computer vede numere, nu litere. Numerele sunt de fapt doar o serie de 0s și 1s la calculator și nu au de fapt nici un sens. Combinarea de caractere în șiruri face doar seria de 0s și 1s mai lungă. În consecință, compararea a două șiruri de caractere, ceva pe care un om o poate face dintr-o privire, poate să ia timp într-un calculator, iar confuzia este posibilă între conjugate. De exemplu, dacă nu sunteți atent la construirea algoritmului, un calculator ar putea confunda enlist și asculta. Mai important, calculatorul ar avea nevoie de timp pentru a discerne diferența dintre cele două. Problema cuvintele separatoare încearcă să găsească algoritmul cel mai mic (și cel mai rapid) posibil (un automat finit determinat, DFN, în acest caz) pentru a efectua separarea cuvintelor.Scopul este de a accepta un cuvânt și de a respinge altul, datând două cuvinte de o anumită lungime.

Determinarea faptului dacă o aplicație se va termina

Una dintre problemele pe care Alan Turing le-a propus în 1936 este problema dacă un algoritm, dat fiind descrierea unui program și a unei intrări, ar putea determina dacă programul ar fi oprit în cele din urmă oprirea problemei). Când lucrați cu o aplicație simplă, este ușor să determinați în multe cazuri dacă programul se va opri sau va continua să funcționeze într-o buclă nesfârșită. Cu toate acestea, pe măsură ce crește complexitatea programului, determinarea rezultatului de rulare a programului cu orice intrare dată devine mai dificilă. O mașină Turing nu poate face această determinare; rezultatul este codul buggy cu bucle infinite. Nici o cantitate de testare care utilizează tehnologia actuală nu poate rezolva această problemă.

Un hipercomputer este un model de calcul care merge dincolo de mașina Turing pentru a rezolva probleme cum ar fi problema stopării. Cu toate acestea, aceste mașini nu sunt posibile folosind tehnologia actuală. Dacă ar fi posibil, ați putea să le întrebați tot felul de improbabile pe care computerele nu le pot răspunde în prezent. Acest articol vă oferă o idee bună despre ce s-ar întâmpla dacă cineva ar fi capabil să rezolve această problemă.

Crearea și utilizarea funcțiilor într-o singură direcție

O funcție cu o singură cale este o funcție ușor de utilizat pentru a obține un răspuns într-o direcție, dar aproape imposibil de utilizat cu inversul răspunsului. Cu alte cuvinte, utilizați o funcție unidirecțională pentru a crea ceva asemănător unui hash care ar apărea ca parte a unei soluții de criptografie, identificare personală, autentificare sau alte nevoi de securitate a datelor.

Existența unei funcții unice este mai puțin misterioasă și mai mult o probă. Multe sisteme de telecomunicații, e-commerce și e-banking se bazează în prezent pe funcții care se presupune că sunt într-un fel, dar nimeni nu știe cu adevărat dacă sunt într-adevăr o cale. Existența unei funcții unice este în prezent o ipoteză, nu o teorie. Dacă cineva a fost capabil să demonstreze că există o funcție unică, problemele de securitate a datelor ar fi mai ușor de rezolvat dintr-o perspectivă de programare.

Înmulțirea unor numere foarte mari

Numerele foarte mari există în multe locuri. De exemplu, luați în considerare efectuarea calculelor care implică distanțe față de Marte sau, probabil, Pluto. Metodele există în prezent pentru a efectua multiplicarea pe un număr foarte mare, dar ele tind să fie lentă deoarece necesită operații multiple pentru a fi finalizate. Problema apare când numerele sunt prea mari pentru a se încadra în registrele procesorului. În acest moment, multiplicarea trebuie să aibă loc în mai multe etape, ceea ce încetinește considerabil lucrurile. Soluțiile actuale includ:

• algoritmul de înmulțire complex al lui Gauss
• multiplicarea Karatsuba
• Toom-Cook
• metode de transformare Fourier

atunci când aveți o mulțime de calcule pentru a efectua, problema de timp poate deveni critică. În consecință, multiplicarea numărului mare este una dintre acele probleme care necesită o soluție mai bună decât cele disponibile astăzi.

Împărțiți o resursă în mod egal

Împărțirea resurselor în mod egal poate să nu pară tare, dar oamenii, fiind un fel de invidios, ar putea vedea resursa ca fiind neuniform împărțită dacă nu puteți găsi o cale de a vă asigura că diviziunea este într-adevăr corectă. Aceasta este problema invidioasă de tăiere a tortului. Bineînțeles, atunci când tăieți un tort, indiferent cât de corect îl faceți, există întotdeauna percepția că diviziunea este nedreaptă. Crearea unei repartizări echitabile a resurselor este importantă în viața de zi cu zi pentru a minimiza conflictele dintre părțile interesate din orice organizație, ceea ce face ca toată lumea să fie mai eficientă.

Există deja două soluții pentru problema cu privire la reducerea tortului fără invidie cu un anumit număr de persoane, dar nu există o soluție generală. Când sunt implicați doi oameni, primul tăie tortul, iar al doilea alege prima piesă. În acest fel, ambele părți sunt asigurate de o diviziune egală. Problema devine mai dificilă cu trei persoane, dar puteți încerca soluția Selfridge-Conway pentru această problemă. Cu toate acestea, după ce ajungeți la patru persoane, nu există nicio soluție.

Reducerea timpului de calcul al distanței de editare

Distanța de editare între două șiruri este numărul de operații necesare pentru transformarea unui șir într-un alt șir. Calculul distanței se învârte în jurul operațiilor de la distanță Levenshtein, care sunt îndepărtarea, inserția sau înlocuirea unui caracter în șir. Această tehnică particulară vede utilizarea în interfețe de limbaj natural, cuantificarea secvențelor ADN și tot felul de alte locuri unde puteți avea două șiruri similare care necesită un fel de comparație sau modificare.

În prezent există o serie de soluții pentru această problemă, toate fiind destul de lente. De fapt, majoritatea dintre ei iau timp exponențial, astfel încât timpul necesar pentru a efectua o transformare se adaugă rapid până la punctul în care oamenii pot vedea pauze în procesarea datelor de intrare. Pauza nu este destul de rea atunci când se utilizează un procesor de text care efectuează verificări automate ale cuvintelor și modifică un cuvânt greșit în cel corect. Cu toate acestea, atunci când se utilizează interfețe vocale, pauza poate deveni destul de vizibilă și poate determina operatorul uman să facă greșeli.

Rezolvarea rapidă a problemelor

În timp ce învățarea de mașină decolează și noi contează tot mai mult pe computere pentru a rezolva probleme, problema cât de rapid poate rezolva o problemă un computer devine critică. Problema P versus NP întreabă pur și simplu dacă un computer poate rezolva rapid o problemă atunci când poate verifica rapid soluția la problemă. Cu alte cuvinte, dacă computerul poate să stabilească în mod rezonabil că răspunsul uman la o problemă este corect în timp polinomial sau mai puțin, poate rezolva problema însăși în timp polinomial sau mai puțin?

Această întrebare a fost discutată inițial în anii 1950 de către John Nash în scrisorile către Agenția Națională de Securitate (NSA) și din nou în scrisorile dintre Kurt Gödel și John von Neumann. În plus față de învățarea în mașină (și AI în general), această problemă particulară este o preocupare pentru multe alte domenii, inclusiv matematică, criptografie, cercetare algoritmică, teorie joc, procesare multimedia, filosofie și economie.

Redarea jocului de paritate

La început, rezolvarea unui joc ar putea să nu pară folositoare în viața reală. Da, jocurile sunt distractive și interesante, dar nu oferă într-adevăr un fundal pentru a face ceva util - cel puțin, aceasta este teoria generală. Cu toate acestea, teoria jocurilor intră în joc într-un număr mare de scenarii de viață reală, multe dintre acestea implicând procese complexe pe care cineva le poate înțelege mai ușor ca jocuri decât procese reale. În acest caz, jocul ajută oamenii să înțeleagă automatizarea verificării și sinteza controlorilor, printre altele. Puteți citi mai multe despre jocul de paritate. De fapt, o puteți juca.

Înțelegerea problemelor spațiale

Pentru a pune această problemă în context, gândiți-vă la mutarea cutiilor într-un depozit sau în alte situații în care trebuie să luați în considerare spațiul în care se mișcă lucrurile. Evident, dacă aveți multe cutii într-un depozit mare și toate au nevoie de un stivuitor pentru a ridica, nu doriți să încercați să dați seama cum să le stocați în mod optim prin rearanjarea fizică a acestora. Aici trebuie să rezolvați problema prin vizualizarea unei soluții.

Totuși, întrebarea este dacă toate problemele spațiale au o soluție. În acest caz, gândiți-vă la unul dintre acele puzzle-uri ale copiilor, care vă pune împreună o imagine prin alunecarea plăcilor mici. Se pare că ar trebui să existe o soluție în toate cazurile, dar în unele situații, un punct de plecare rău poate duce la o situație care nu are nici o soluție.

Matematicienii, cum ar fi Sam Loyd, folosesc adesea puzzle-uri pentru a demonstra probleme matematice complexe, dintre care unele nu au soluție astăzi. Vizitarea acestor site-uri este distractivă, deoarece nu numai că beneficiați de divertisment gratuit, dar și de hrană pentru gândire. Problemele pe care le ridică aceste puzzle-uri au aplicații practice, dar ele sunt prezentate într-un mod distractiv.