Cel mai bun răspuns
Nu există un răspuns la acest lucru.
Să găsim răspuns la această afirmație de problemă:
Î. Cum se găsește un algoritm care funcționează mai bine?
A. Cele mai frecvente moduri de a compara algoritmii:
1) Complexitatea timpului
2) Complexitatea spațiului
3) Calitatea soluției (nu poate să fie aplicabil dacă propune rezolvarea exactă a unei probleme). Acesta poate fi un factor imens dacă vorbim despre algoritmi de aproximare.
4) Ușurința implementării / adaptării algoritmului. Unii algoritmi pot avea o mulțime de cheltuieli generale pentru a fi implementate corect. Uneori există algoritmi mai adecvați. pentru aplicația dvs. De exemplu, în calcul paralel, majoritatea vor găsi Bellman-Ford mai util decât algoritmul lui Dijkstra datorită modului în care funcționează Bellman-Ford.
Cu toate acestea, timpul și complexitatea nu sunt * întotdeauna * caracteristica dorită de maximizat; Voi oferi două exemple.
Unul este „stabilitate numerică” , o caracteristică a algoritmilor atât în algebră liniară, cât și în ecuații diferențiale. Vom cheltui atât mai mult timp algoritmic, cât și mai multă complexitate algoritmică pe algoritmi care sunt mai stabili numeric. În algebra liniară instabilitatea este cauzată în general atunci când un algoritm întâlnește numere prea apropiate de zero sau infinit sau ambele, din cauza reprezentării finite a numerelor rezoluția poate fi pierdută. În general, acest lucru determină numere foarte ușor diferite, doar câteva epsilon diferite între ele (unde epsilon este cel mai mic număr care poate fi adăugat la unul, pe o mașină și obține un rezultat! = 1), pentru a produce diferențe mari în răspunsul. Deci, de exemplu, cheltuim mult timp și complexitate spațială „pivotând” în factorizarea LU pentru a obține un algoritm stabil; fără pivotarea LU nu este stabilă. La fel, avem algoritmi care nu fac altceva decât să „condiționeze” matricele pentru a evita instabilitatea.
Un al doilea exemplu este „robustețe” în simțul său statistic tehnic. Robustețe înseamnă o măsură sau algoritm care nu este * sensibil * la valori anormale. De exemplu, atunci când potrivesc o linie de cel puțin pătrate la un set de puncte, linia poate fi puternic distorsionată de o singură valoare extrem de mare. Chiar dacă am 99 de perechi de numere care formează o linie perfectă de 45 de grade, dacă adaug o singură pereche exterioară pentru care valoarea Y este de sută de ori mai mare decât ar trebui să cadă pe aceeași linie, linia potrivită va fi severă a înclinat linia de 45 de grade. Algoritmul va „renunța” la potrivirea perfectă pentru 99 de puncte, pentru a reprezenta mai bine punctul unic outlier. Aceasta este * nu * robustă.
O abordare robustă a celor mai mici pătrate este, în loc să găsești linia care minimizează suma erorilor pătrate create prin utilizarea acelei linii, să găsești linia care minimizează * mediana * a erorile pătrate create prin utilizarea acelei linii. În exemplu, acea linie este linia de 45 de grade, iar mediana erorilor pătrate este zero, iar punctul exterior (și într-adevăr până la 98 de alte valori nebunești) ar fi ignorat complet. Linia de 45 de grade ar fi găsită.
Există algoritmi robusti similari pentru potrivirea curbelor statistice, găsirea formelor etc. Cu toate acestea, acestea sunt costisitoare în timp, uneori sever. Dar costul timpului merită, deoarece statisticile robuste sunt efectiv imune la „zgomot” în semnale, unde abordările de eroare cel puțin pătrate nu sunt. Lumea reală este plină atât de zgomot, cât și de valori aberante, unele dintre ele cauzate de erori umane sau de mașini, în special în imagini pixelate sau sunete eșantionate. În astfel de circumstanțe, un algoritm robust mai costisitor poate găsi semnale într-un mediu zgomotos, în care algoritmi mai rapizi produc răspunsuri atât de corupte de zgomot încât sunt inutile sau chiar periculoase dacă sunt acceptate.
În unele cazuri, timpul iar complexitatea spațiului nu este la fel de importantă ca găsirea unui răspuns cel mai probabil pentru a modela semnalul real, în ciuda zgomotului și degradării semnalului.
Răspuns
Algoritmi originari în matematică ca „rețete” pentru efectuarea calculelor bazate pe funcții, care pot fi urmărite mecanic. În viziunea matematică bazată pe funcții, toate intrările trebuie specificate la începutul calculului, care se desfășoară într-un cadru închis. Noțiunea de algoritm este inerent informală, deoarece o descriere algoritmică nu este limitată la un singur limbaj sau formalism.
Poate că cel mai vechi exemplu este algoritmul lui Euclid pentru găsirea divizorilor comuni. Algoritmii surprind ceea ce înseamnă că un calcul este „eficient”. La fel ca formulele matematice, algoritmii ne spun cum să calculăm o valoare; spre deosebire de ei, algoritmii pot implica ceea ce numim acum bucle sau ramuri.
Rolul algoritmului: Având în vedere o valoare de intrare finită x, un algoritm descrie pașii pentru transformarea sa efectivă într-o valoare de ieșire y, unde f (x) pentru unele funcții recursive f.
Algoritmii au fost adoptați de informaticienii din anii 1950, care au făcut legătura dintre algoritmi și mașinile Turing (TM, un model formal de calcul datând din 1936), echivalând expresivitatea lor.
Celebrul și influentul manual al lui Knuth, „The Art of Computer Programming, Vol. 1”, la sfârșitul anilor 1960, a popularizat centralitatea algoritmilor în informatică. În definiția algoritmilor, Knuth a fost în concordanță cu fundamentele matematice bazate pe funcția teoriei calculului. „Există multe alte modalități esențial echivalente de a formula conceptul unei metode de calcul eficiente (de exemplu, folosind TM-uri).”
Knuth a specificat în mod explicit că algoritmii sunt închisi; nu este acceptată nicio intrare nouă odată ce calculul a început: „Un algoritm are zero sau mai multe intrări, adică cantități care îi sunt date inițial înainte de începerea algoritmului.” El a distins algoritmii de calculul arbitrar care ar putea implica I / O. Un exemplu pe care l-a dat despre o problemă care nu este algoritmică este următoarea instrucțiune dintr-o rețetă: „aruncați ușor până când amestecul este sfărâmicios”. Această problemă nu este algoritmică, deoarece este imposibil pentru un computer să știe cât timp se amestecă; aceasta poate depinde de condițiile externe dinamice, precum umiditatea, care nu pot fi prezise cu certitudine înainte de timp.
Deși nu există un acord cu privire la noțiunea exactă de algoritmi, discuția lui Knuth despre algoritmi rămâne definitivă.
Primul limbaj de programare la nivel înalt dezvoltat expres pentru a specifica algoritmi a fost ALGOL (ALGOrithmic Language). Introdus la sfârșitul anilor 50 și rafinat până în anii 1960, a servit drept standard pentru publicarea algoritmilor. Fidel conceptualizării bazate pe funcții a algoritmilor, ALGOL nu a furnizat construcții pentru intrare și ieșire, având în vedere aceste operațiuni în afara preocupării algoritmilor. (Nu este surprinzător, această absență a împiedicat adoptarea ALGOL de către industrie pentru aplicații comerciale.)
Anii 1960 au văzut o proliferare a programelor universitare de informatică (CS). Potrivit Asociației pentru Mașini de Calculat (ACM), numărul programelor CS din SUA a crescut de la 11 în 1964 la 92 în 1968. Această creștere a fost însoțită de o activitate intensă în vederea stabilirii legitimității acestei noi discipline în ochii academicienilor comunitate. ACM a jucat un rol central în această activitate. În 1965, a enunțat justificarea și descrierea CS ca disciplină, care a servit ca bază a recomandărilor sale din 1968 pentru programele CS de licență
Descrierea ACM a CS a identificat transformarea efectivă a informațiilor ca o preocupare centrală: „ Informatica este preocupată de informații în același sens în care fizica este preocupată de energie … Informaticianul este interesat să descopere mijloacele pragmatice prin care informațiile pot fi transformate. ” Această descriere plasează algoritmii în centrul informaticii, deoarece acestea sunt „rețetele” pentru efectuarea acestor transformări eficiente ale intrărilor în ieșiri. De fapt, ACM a făcut ca această concentrare pe algoritmi să fie explicită în următoarea propoziție a raportului lor:
„Acest interes duce la investigarea unor modalități eficiente de reprezentare a informațiilor, algoritmi eficienți de transformare a informațiilor, limbaje eficiente cu care să se exprime algoritmi … și modalități eficiente de a le realiza la un cost rezonabil. ”
Având o preocupare algoritmică centrală, analogă preocupării cu energia din fizică, a contribuit la stabilirea CS ca o disciplină academică legitimă, la fel ca fizică. Algoritmii au rămas centrale în domeniul informaticii până în prezent.
Coexistența abordărilor informale (bazate pe algoritmi) și formale (bazate pe TM) pentru definirea problemelor rezolvabile persistă până în prezent și poate fi găsită în toate manualele moderne despre algoritmi sau calculabilitate. Acest lucru s-a dovedit foarte convenabil pentru informaticieni, permițându-ne să descriem calculul algoritmic în mod informal folosind „pseudocod”, știind că se poate construi o mașină Turing echivalentă.
– O problemă este rezolvabilă dacă poate fi rezolvată. specificat de un algoritm. – O problemă este rezolvabilă dacă există o Mașină Turing pentru aceasta.
Decizia anilor 1960 a teoreticienilor și a educatorilor de a plasa algoritmi în centrul CS a fost reflectată în mod clar în manualele de la începutul ciclului universitar. Cu toate acestea, nu a existat o definiție standard explicită a unui algoritm și diverse manuale au ales să definească acest termen în mod diferit. În timp ce unele manuale precum cel de Knuth au avut grijă să limiteze în mod explicit algoritmii la cei care calculează funcții și, prin urmare, sunt echivalente cu Mașinile Turing, majoritatea cărților de teorie au lăsat această restricție implicită, dar nedeclarată.
Un prim exemplu este un manual de Hopcroft și Ullman din 1969, ale cărui ediții ulterioare sunt folosite până în prezent: „O procedură este o secvență finită de instrucțiuni care poate fi efectuată mecanic, cum ar fi un program de computer …O procedură care se termină întotdeauna se numește algoritm. ”
Această descriere a algoritmilor nu exclude în mod explicit calculele nefuncționale, cum ar fi pregătirea alimentelor. Cu toate acestea, exemplele lor de diverse probleme arată clar că au luat în considerare doar calculul bazat pe funcții. De fapt, au folosit ALGOL pentru exemplele lor, care nici măcar nu au oferit construcții pentru intrare și ieșire.
De la sfârșitul anilor 60, limbajele de programare la nivel înalt utilizate în practică și predate în programele CS nu mai erau legat de restricțiile algoritmice ale ALGOL timpuriu. Puteți scrie programe care interacționează cu mediul lor într-un mod continuu pe tot parcursul calculului, cum ar fi sistemele de operare, interfețele grafice ale utilizatorului sau vehiculele automate și alți roboți.
Ca răspuns, manuale de programare contemporane precum Rice și Rice (1969) a extins în mod explicit noțiunea de algoritmi pentru a include probleme nefuncționale. Această abordare, reflectând centralitatea algoritmilor fără a le restrânge la calculul funcțiilor, a devenit tipică manualelor non-teoretice. Subiectul acestor manuale este mai degrabă metodologia de programare decât teoria calculului, iar principiile matematice care stau la baza modelelor noastre de calcul au fost aruncate deoparte din motive de practicitate.
La suprafață, definiția unui algoritm în Rice and Rice și alte astfel de manuale nu diferă de Hopcroft și Ullman: „Un algoritm este o rețetă, un set de instrucțiuni sau specificațiile unui proces pentru a face ceva. Că ceva rezolvă de obicei o problemă de vreun fel ”. Cu toate acestea, exemplele lor de probleme calculabile nu mai sunt bazate pe funcții, admisând doar tipul de calcul pe care Knuth îl respinsese. Două astfel de exemple, care se presupune că pot fi rezolvate printr-un algoritm, sunt fabricarea de vodcă de cartofi și umplerea unui șanț cu nisip; Knuth i-ar fi respins pe amândoi.
Aceste manuale nu au făcut nicio pretenție de echivalență TM pentru „algoritmii” lor. Cu toate acestea, studenții nu au fost conștienți de faptul că această noțiune de algoritmi este diferită de cea a lui Knuth și că setul de probleme considerate computabile a fost astfel extins. Prin asocierea unei conceptualizări mai largi, mai practice, a algoritmilor (și, prin urmare, a problemelor calculabile) cu teoriile care susțin că o problemă foarte calculabilă poate fi calculată prin TM-uri, programa CS axată pe algoritmi a lăsat studenții cu impresia eronată că acest set mai larg de probleme ar putea de asemenea, să fie rezolvate de TM-uri.
În timp ce oamenii de știință practici în informatică au urmat demult conducerea Rice și Rice și au lărgit conceptul de algoritmi dincolo de calculul funcțiilor, informatica teoretică a păstrat viziunea matematică asupra lumii care încadrează de calcul ca fiind bazat pe funcție și ne delimitează noțiunea de problemă de calcul în consecință. Acest lucru este valabil cel puțin la nivel de licență. Rezultatul este o dihotomie, în care comunitatea informatică consideră algoritmii ca fiind sinonimi cu noțiunea generală de calcul („ceea ce fac computerele”), dar în același timp echivalează cu Mașinile Turing.
A trebuit să scriu acest răspuns lung, pentru a-i face pe oameni conștienți de această dihotomie. După cum am spus la început, noțiunea de algoritm este informală. Ne putem gândi la acesta ca fiind echivalent cu calculul funcțiilor (sau la Mașinile Turing) sau ne putem gândi la el ca la orice lucru pentru care puteți scrie un program, inclusiv programe interactive în timp real, cum ar fi sistemele de operare sau mașinile automate. Dar cele două definiții nu sunt echivalente, în ciuda confuziei comune contrare.