Paras vastaus
Tähän ei ole vastausta.
Etsitään vastausta tähän ongelmalausekkeeseen:
Q. Kuinka löytää mikä tahansa algoritmi toimii paremmin?
A. Yleisimmät algoritmien vertailutavat:
1) Ajan monimutkaisuus
2) Avaruuden monimutkaisuus
3) Ratkaisun laatu (ei välttämättä voidaan soveltaa, jos se ehdottaa ongelman ratkaisemista tarkasti) Tämä voi olla valtava tekijä, jos puhumme approksimaatioalgoritmeista.
4) Helppo käyttöönotto / algoritmin mukauttaminen. Joillakin algoritmeilla voi olla paljon yleiskustannuksia, jotta ne voidaan toteuttaa oikein. Joskus on sopivampia algoritmeja Esimerkiksi rinnakkaislaskennassa useimmat pitävät Bellman-Fordia hyödyllisempänä kuin Dijkstran algoritmi Bellman-Fordin toimintatavan vuoksi.
Aika ja monimutkaisuus eivät kuitenkaan ole * aina * haluttu ominaisuus maksimoimiseksi; Annan kaksi esimerkkiä.
Yksi on ”numeerinen vakaus” , algoritmien ominaisuus sekä lineaarisessa algebrassa että differentiaaliyhtälöissä. Kulutamme sekä enemmän algoritmiaikaa että enemmän algoritmeja monimutkaisemmiksi algoritmeille, jotka ovat numeerisesti vakaampia. Lineaarisessa algebrassa epävakaus aiheutuu yleensä, kun algoritmi kohtaa numeroita, jotka ovat liian lähellä nollaa tai ääretöntä tai molempia, koska numeroiden rajallinen esitys voi menetää. Yleensä tämä aiheuttaa hyvin vähän erilaisia lukuja, vain muutaman epsilonin, jotka eroavat toisistaan (missä epsilon on pienin luku, joka voidaan lisätä yhteen, koneella ja saada tulos! = 1) tuottaa suuria eroja vastaus. Joten esimerkiksi vietämme paljon aikaa ja tilaa monimutkaisemmin ”kääntymällä” LU-kertoimeen vakaan algoritmin saamiseksi; ilman kääntöä LU ei ole vakaa. Samoin meillä on algoritmeja, jotka eivät tee muuta kuin ”ehto” -matriisit epävakauden välttämiseksi.
Toinen esimerkki on ”kestävyys” sen tekninen tilastollinen merkitys. Vankkuudella tarkoitetaan mittaa tai algoritmia, joka * ei * ole herkkä poikkeamille. Joten esimerkiksi kun sovitan pienimmän neliösumman linjan pistejoukkoon, viiva voi olla voimakkaasti vinossa yhdellä erittäin suurella arvolla. Vaikka minulla on 99 numeroparia, jotka muodostavat täydellisen 45 asteen viivan, jos lisäät yhden outlier-parin, jonka Y-arvo on sata kertaa suurempi kuin sen ”pitäisi” pudota samalle linjalle, sovitettu viiva on vakavasti vinossa 45 asteen viivasta. Algoritmi ”luopuu” täydellisestä sopivuudesta 99 pisteeseen edustamaan paremmin yhtä syrjäytyvää pistettä. Tämä ei ole * vankka.
Vankka pienimmän neliösumman lähestymistapa on sen sijaan, että löydettäisiin viiva, joka minimoi kyseisen rivin avulla luotujen neliövirheiden summan, löytääksesi viivan, joka minimoi arvon * mediaanin kyseisen rivin avulla luodut neliövirheet. Esimerkissä tuo viiva on 45 asteen viiva ja neliövirheiden mediaani on nolla, ja ulompi piste (ja jopa 98 muuta hullua poikkeamaa) jätettäisiin huomiotta. Löydettäisiin 45 asteen viiva.
Vastaavia vankkoja algoritmeja on olemassa tilastokäyrien sovittamiseen, muotojen löytämiseen jne. Ne ovat kuitenkin ajallisesti kalliita, toisinaan ankarasti. Mutta aikakustannukset ovat sen arvoisia, koska vankat tilastot ovat tehokkaasti immuuneja signaalien ”melulle”, missä pienimmän neliösumman lähestymistavat eivät ole. Todellinen maailma on täynnä sekä kohinaa että poikkeamia, joista osa johtuu ihmisen tai koneen virheistä, erityisesti pikseloiduissa kuvissa tai näytteistetyssä äänessä. Tällaisissa olosuhteissa ajallisesti kalliimpi ja vankempi algoritmi voi löytää signaaleja meluisasta ympäristöstä, jossa nopeammat algoritmit tuottavat melun niin korruptoimat vastaukset, että ne ovat hyödyttömiä tai jopa vaarallisia, jos ne hyväksytään.
Joissakin tapauksissa aika ja avaruuden monimutkaisuus eivät ole läheskään yhtä tärkeitä kuin vastauksen löytäminen, joka todennäköisimmin mallintaa todellisen signaalin melusta ja signaalin heikentymisestä huolimatta.
Vastaus
Matematiikasta peräisin olevat algoritmit ovat ”reseptejä”. toimintoperusteisen laskennan suorittamiseksi, jota voidaan seurata mekaanisesti. Funktioperusteisessa matemaattisessa maailmankatsomuksessa kaikki syötteet on määriteltävä laskennan alussa, mikä etenee suljetun laatikon tapaan. Algoritmin käsite on luonnostaan epävirallinen, koska algoritminen kuvaus ei rajoitu mihinkään yksittäiseen kieleen tai formalismiin.
Ehkä vanhin esimerkki on Euclidesin algoritmi yhteisten jakajien löytämiseksi. Algoritmit ottavat huomioon, mitä tarkoittaa, että laskenta on ”tehokasta”. Kuten matemaattiset kaavat, algoritmit kertovat meille, kuinka arvo lasketaan; toisin kuin ne, algoritmeihin voi liittyä niin sanottuja silmukoita tai haaroja.
Algoritmin rooli: Annettaessa rajallinen tuloarvo x, algoritmi kuvaa vaiheet, joilla se voidaan tehokkaasti muuntaa lähtöarvoksi y, missä y on f (x) joillekin rekursiivisille funktioille f.
Varhaiset tietojenkäsittelytieteen tutkijat hyväksyivät algoritmit 1950-luvulla, jotka tekivät yhteyden algoritmien ja Turing Machinesin välille (TM, muodollinen laskentamalli vuodelta 1936) tasaamalla niiden ilmeikkyyden.
Knuthin kuuluisa ja vaikutusvaltainen oppikirja ”The Art of Computer Programming, Vol. 1” 1960-luvun lopulla popularisoi algoritmien keskeisyyttä tietojenkäsittelytieteessä. Algoritmien määrittelyssä Knuth oli johdonmukainen laskennateorian matemaattisten funktioperusteisten perusteiden kanssa. ”On monia muita olennaisesti vastaavia tapoja muotoilla tehokkaan laskennallisen menetelmän käsite (esimerkiksi käyttämällä TM: itä).”
Knuth tarkensi, että algoritmit on suljettu; mitään uutta syötettä ei hyväksytä, kun laskenta on aloitettu: ”Algoritmilla on nolla tai enemmän syötteitä, ts. määrät, jotka annetaan sille alun perin ennen algoritmin alkua.” Hän erotti algoritmit mielivaltaisesta laskennasta, johon voi liittyä I / O. Yksi esimerkki ongelmasta, joka ei ole algoritminen, on seuraava reseptin ohje: ”heittää kevyesti, kunnes seos on murenevaa”. Tämä ongelma ei ole algoritminen, koska tietokoneen on mahdotonta tietää, kuinka kauan sekoitetaan; tämä voi riippua yhdestä ulkoisesta dynaamisesti muuttuvasta olosuhteesta, kuten kosteudesta, jota ei voida ennustaa varmuudella etuajassa.
Vaikka algoritmien tarkasta käsitteestä ei ole sovittu, Knuthin keskustelu algoritmeista pysyy lopullisena.
Ensimmäinen korkean tason ohjelmointikieli, joka kehitettiin nimenomaisesti algoritmien määrittämiseksi, oli ALGOL (ALGOrithmic Language). Se otettiin käyttöön 50-luvun lopulla ja puhdistettiin 1960-luvulla, ja se toimi standardina algoritmien julkaisemisessa. Algoritmien toimintoperusteisen käsitteellistämisen lisäksi ALGOL ei tarjonnut mitään tulo- ja lähtörakenteita, kun otetaan huomioon nämä toiminnot algoritmien ulkopuolella. (Ei ole yllättävää, että tämä poissaolo vaikeutti ALGOLin käyttöönottoa teollisuudessa kaupallisiin sovelluksiin.)
1960-luvulla tietojenkäsittelytieteen (CS) ohjelmat lisääntyivät. Association for Computing Machinery (ACM): n mukaan Yhdysvaltojen CS-ohjelmien määrä kasvoi 11: stä 1964: stä 92: een vuonna 1968. Tähän kasvuun liittyi intensiivistä toimintaa kohti uuden tieteenalan legitiimiyden vahvistamista akateemisten silmissä. Yhteisö. ACM: llä oli keskeinen rooli tässä toiminnassa. Vuonna 1965 se esitti CS: n perustelut ja kuvauksen tieteenalana, joka toimi perustana vuoden 1968 suosituksille perustutkinto-ohjelmille.
ACM: n CS-kuvauksessa yksilöitiin tiedon tehokas muuntaminen keskeiseksi huolenaiheeksi: ” Tietojenkäsittelytiede käsittelee tietoa samassa mielessä kuin fysiikka energiaa … Tietojenkäsittelytieteen tutkija on kiinnostunut löytämään käytännön keinot, joilla tietoa voidaan muuttaa. ” Tämä kuvaus asettaa algoritmit tietojenkäsittelytieteen keskelle, koska ne ovat ”reseptejä” näiden tulojen ja lähtöjen tehokkaiden muunnosten suorittamiseksi. Itse asiassa ACM keskittyi algoritmeihin nimenomaisesti raportin seuraavassa virkkeessä:
”Tämä kiinnostus johtaa tutkimukseen tehokkaista tavoista edustaa tietoa, tehokkaista algoritmeista tiedon muuntamiseksi, tehokkaista kielistä, joilla ilmaista algoritmeja … ja tehokkaita tapoja saavuttaa nämä kohtuullisin kustannuksin. ”
Keskitetyn algoritmisen huolenaihe, joka on analoginen fysiikan energiahuolen kanssa, auttoi vakiinnuttamaan CS: n laillisena akateemisena tieteenalana, joka on samanlainen kuin fysiikka. Algoritmit ovat pysyneet keskeisenä tietojenkäsittelytieteessä tähän päivään asti.
Epävirallisten (algoritmipohjaisten) ja muodollisten (TM-pohjaisten) lähestymistapojen rinnakkaiselo ratkaistavien ongelmien määrittelemisessä jatkuu tähän päivään saakka, ja ne löytyvät kaikki modernit algoritmeja tai laskettavuutta käsittelevät oppikirjat. Tämä on osoittautunut erittäin käteväksi tietojenkäsittelytieteen tutkijoille, koska voimme kuvata algoritmisen laskennan epävirallisesti ”pseudokoodilla” tietäen, että vastaava Turingin kone voidaan rakentaa.
– Ongelma on ratkaistavissa, jos se voidaan ratkaista algoritmi. – Ongelma on ratkaistavissa, jos sille on olemassa Turingin kone.
Teoreetikkojen ja kouluttajien vuonna 1960 tekemä päätös sijoittaa algoritmit CS: n keskelle heijastui selvästi varhaisopiskelijoiden oppikirjoihin. Algoritmin nimenomaista vakiomääritelmää ei kuitenkaan ollut, ja erilaiset oppikirjat päättivät määritellä tämän termin eri tavalla. Jotkut Knuthin kaltaiset oppikirjat varoivat rajoittaa algoritmeja nimenomaisesti niihin, jotka laskevat toiminnot ja vastaavat siis Turingin koneita, mutta useimmat teoreettiset kirjat jättivät tämän rajoituksen implisiittiseksi mutta ilmoittamatta.
Varhainen esimerkki on Hopcroftin ja Ullmanin oppikirja vuodelta 1969, jonka myöhempiä painoksia käytetään tähän päivään asti: ”Menettely on rajallinen sekvenssi ohjeista, jotka voidaan suorittaa mekaanisesti, kuten tietokoneohjelma …Aina päättyvää menettelyä kutsutaan algoritmiksi. ”
Tämä algoritmien kuvaus ei nimenomaisesti sulje pois ei-toiminnallista laskentaa, kuten ruoan valmistamista. Niiden esimerkit erilaisista ongelmista tekevät kuitenkin selväksi, että he harkitsivat vain toimintoperusteista laskentaa. Itse asiassa he käyttivät esimerkkeihinsä ALGOLia, joka ei edes tarjonnut mitään konstruktioita syötteille ja tuotoksille.
60-luvun lopusta lähtien käytännössä käytetyt ja CS-ohjelmissa opetetut korkean tason ohjelmointikielet eivät enää olleet. varhaisen ALGOLin algoritmiset rajoitukset sitovat. Voit kirjoittaa ohjelmia, jotka ovat vuorovaikutuksessa ympäristönsä kanssa jatkuvasti laskennan aikana, kuten käyttöjärjestelmät, graafiset käyttöliittymät tai automaattiset ajoneuvot ja muut robotit.
Vastauksena nykyaikaiset ohjelmointikirjat, kuten Rice ja Rice (1969) laajensi nimenomaisesti algoritmien käsitettä sisältämään ei-toiminnalliset ongelmat. Tämä lähestymistapa, joka heijastaa algoritmien keskeisyyttä rajoittamatta niitä toimintojen laskemiseen, tuli tyypilliseksi ei-teoreettisille oppikirjoille. Näiden oppikirjojen aihe on pikemminkin ohjelmointimenetelmä kuin laskentateoria, ja matemaattiset periaatteet, jotka tukevat laskentamalliamme, jätettiin käytännöllisyyden vuoksi sivuun.
Pinnalla algoritmin määrittely Rice and Rice -kirjassa ja muissa vastaavissa oppikirjoissa ei ole eroa Hopcroftista ja Ullmanista: ”Algoritmi on resepti, joukko ohjeita tai prosessin määrittely jotain tekemistä varten. Se jotain yleensä ratkaisee jonkinlaisen ongelman. ” Heidän esimerkkinsä laskettavista ongelmista eivät kuitenkaan enää ole toimintoperusteisia, vaan tunnustavat juuri sellaiset laskelmat, jotka Knuth oli hylännyt. Kaksi tällaista esimerkkiä, jotka oletettavasti voidaan ratkaista algoritmilla, ovat perunavodkan valmistus ja ojan täyttäminen hiekalla; Knuth olisi hylännyt molemmat.
Nämä oppikirjat eivät väittäneet TM-vastaavuutta ”algoritmeistaan”. Opiskelijoille ei kuitenkaan annettu tietoa siitä, että tämä algoritmien käsite eroaa Knuthin käsityksestä ja että laskettavana pidettyjen ongelmien joukkoa oli siten laajennettu. Yhdistämällä algoritmien (ja siten laskettavissa olevien ongelmien) laajempi, käytännöllisempi käsitteellistäminen teorioihin, jotka väittävät, että TM: t voivat laskea hyvin laskettavissa olevan ongelman, algoritmeihin keskittynyt CS-opetussuunnitelma jätti opiskelijoille virheellisen vaikutelman, että tämä laajempi ongelmakokonaisuus voisi ratkaisee myös TM: t.
Vaikka käytännön tietojenkäsittelytieteen tutkijat ovat jo kauan sitten seuranneet Rice and Rice -näytettä ja laajentaneet algoritmien käsitettä toimintojen laskennan ulkopuolelle, teoreettinen tietojenkäsittelytiede on säilyttänyt matemaattisen maailmankuvan, laskenta toimintoperusteisena ja rajaa käsityksemme laskennallisesta ongelmasta sen mukaisesti. Tämä pätee ainakin perustutkintotasolla. Tuloksena on kahtiajako, jossa tietojenkäsittelytieteellinen yhteisö ajattelee algoritmeja olevan synonyymi yleisen laskennan käsitteelle (”mitä tietokoneet tekevät”), mutta ovat samalla vastaavia kuin Turing Machines.
Ajattelin Minun oli kirjoitettava tämä pitkä vastaus saadakseni ihmiset tietämään tämän kahtiajaon. Kuten sanoin alussa, algoritmin käsite on epävirallinen. Voimme ajatella sen vastaavan funktioiden (tai Turingin koneiden) laskemista tai voimme ajatella sitä kaikesta, mihin voit kirjoittaa ohjelman, mukaan lukien reaaliaikaiset interaktiiviset ohjelmat, kuten käyttöjärjestelmät tai automaattiset autot. Nämä kaksi määritelmää eivät kuitenkaan ole samanlaisia, vaikka päinvastaiset sekaannukset ovatkin yleisiä.