Wikipedia tietää sanoa, että algoritmi tarkoittaa äärellistä joukkoa täsmällisiä, suoritettavissa olevia ohjeita, jotka ohjaavat päättyvää tehtävän suoritusta.
Oikeastaan se ei ole mitään muuta kuin systemaattinen esitys sille miten jokin ongelma ratkaistaan.
13 kommenttia:
Tuon määritelmän mukaan vaikkapa reaktiivista järjestelmää, jonka on tarkoitus toimia tarvittaessa miten kauan tahansa, ohjaavan ohjelman on koostuttava vähintään kahdesta algoritmista. Tai että esimerkiksi Mandelbrotin joukkoa ei voi generoida algoritmilla.
Mandelbrotin joukkoa ei voikaan generoida algoritmilla, koska se on ääretön. Yksittäisestä joukon pisteestäkään ei voi sanoa algoritmilla varmaksi kuuluuko se joukkoon vai ei. Voin olla väärässä, mutta käsittääkseni löytyy sellainen numeroituva joukko kompleksilukuja {x_i}, että kullakin i:n arvolla sen selvittäminen, onko x_i M-joukossa vai ei, vaatii vähintään i kierrosta. (Siis sillä perinteisellä algoritmilla) Voin toki olla väärässä tässä.
Mutta siis, algoritmi tarkoittaa menetelmää, joka antaa vastauksen. Mandelbrotin joukon tietyille osajoukoille on tietenkin algoritmeja.
Vaikka käytän ehkä vakiintuneita termejä väärin, minusta voisi sanoa, että ideaalisesti jokin numeroituvasti ääretön joukko voidaan generoida algoritmilla, jos tällä tarkoitetaan sitä että generaatioksi lasketaaan algoritmin suorittamista numeroituvan äärettömän monta kertaa.
Mandelbrotin joukkoa ei voi generoida kuitenkaan tässä mielessä, koska kyseinen joukko on ylinumeroituva.
Tunnetaankohan _mitään_ metodia jolla voidaan selvittää, kuuluuko annettu kompleksiluku c Mandelbrotin joukkoon? Minusta näyttää, että vastaus voi hyvinkin olla kieltävä.
Ei ole menetelmää, jolla M-joukkoon kuuluminen voidaan yleisessä tapauksessa selvittää. Osasta pisteistä toki tiedetään, että ne kuuluvat M-joukkoon, joten kun se perinteinen iterointi päätyy tähän joukkoon, tiedetään, että alkuperäinen piste oli siinä.
Kiitos. Tuota yleistä tapausta tietysti tarkoitinkin.
Äärellinen joukko ohjeita ei tarkoita, ettei sillä voisi generoida numeroituvasti äärettömiä tuloksia. Osa ohjeista voi näet olla "jos X, niin Y", tai "palaa kohtaan Z". Lopputulos on siis Turing-täydellinen.
Tai ainakin noin minä olen aina algoritmin käsittänyt, enkä ihan hahmota mitä järkeä sitä olisi käsitteellistää niin, että mahdollisia askeleitakin olisi vain äärellinen määrä.
Enkkuwiki sanoo muutaman sadan rivin jälkeen "Some writers restrict the definition of algorithm to procedures that eventually finish", käsiteltyään sitä aiemmin käsitettä merkityksessä jossa moista rajausta ei ole. Suomiwiki näyttää lyövän rajauksen kummemmin selittämättä faktana pöytään.
Oikeastaan tuo pitäisi korjata, selvä virhe. Palaan aiheeseen huomenna selvin päin, jos muistan.
Algoritmiksi mielletään yleensä kaikki laskenta, jota koneella voi tehdä, mutta ei ole ollenkaan tavatonta, että "algoritmi" nimitys on varattu jollekin, mikä takuulla pysähtyy riippumatta syötteestä.
Itse en samasta turingin konetta ja algoritmia, vaan yleensä miellän algoritmin tällä rajoitetummalla tavalla. Ainakin opetuksessa käytän sellaista käsitettä; monimutkaisemmat, joitain RE tai coRE -päätöstehtäviä "ratkaisevat" turingin koneet/tietokoneohjelmat ovat sitten jotain muuta, en yleensä nimitä niitä "algoritmeiksi".
Algoritmin voi tietysti rajata tarkoittamaan vain pysähtyviksi tiedettyjä laskennan kuvauksia. Ja usiemmissa tilanteissa, joissa käsitettä käytetään, sen merkitys ei tällöin itse asiassa eroa mitenkään sellaisesta, jossa se kattaisi mahdollisesti pysähtymättömänkin laskennan.
Mutta sitten meillä on joukko lasketakuvauksia, joista emme pysty sanomaan ovatko ne algoritmeja vai eivät, koska emme ole osoittaneet niiden pysähtyvyyttä. Jos pysähtyvyyden vaatimusta lähte vetämään tiukalla linjalla, se muuttuu hiukan epäkäytännölliseksi. Ja hömppäesimerkkinä random-sort ei ole algoritmi (vai riittääkö tilastollinen pysähtyvyys?), vaikka normaalit sorttaus-algoritmit ovat.
No tuo on pientä sivuharmia, jonka kyllä kestää, jos rajauksesta on jotain hyötyä. Minulle ei aivan auennut miksi algoritmi-käsite olisi syytä rajata vain pysähtyviin laskennan kuvauksiin? Tuoko se jotain käytännöllistä tai esteettistä etua verrattuna laveampaan käsitteeseen?
Matematiikassa algoritmi tietysti aina pysähtyy, sillä informaalisesti tietysti niin kuin TM sanoo algoritmi ratkaisee aina jonkun ongelman. Ei ole järkeä esimerkiksi sanoa, että algoritmilla voidaan ratkaista esimerkiksi jonkun sarjan raja-arvo, jos vain tiedetään että n:n osasumman laskemisen jälkeen tiedämme raja-arvon k_n ensimmäistä desimaalia (elleivät nämä ehdot ole sitten ekvivalentteja raja-arvon ratkaisun kanssa).
Gc: mutta voidaan sanoa, että algoritmilla saadaan raja-arvoa rajatta lähestyvä aproximaatio.
Tai siis ei voida, jos tuo ei ole algoritmi, kun se ei pysähdy eikä ratkaise ongelmaa.
Tietysti kyse on semantiikasta. Algoritmi-sanaa voidaan käyttää mistä tahansa laskentaprosessista, tai sitten ei.
Etu, joka rajauksesta saadaan, on marginaalinen. Esimerkiksi pahimman tapauksen suoritusaika on mielekäs luokittelukriteeri kaikille algoritmeille. Voidaanhan tietysti äärettömätkin suoritukset ottaa mukaan, mutta...
"Gc: mutta voidaan sanoa, että algoritmilla saadaan raja-arvoa rajatta lähestyvä aproximaatio."
Niin voidaan mutta siinä minusta tarkastellaan algoritmia metatasolla, ei varsinaisena vastauksena johonkin konkreettiseen kysymykseen jonka algoritmi konkreettisesti ratkaisee, sillä joskus pitää voida sanoa, että vastaus on nyt annettu, jos vastaus ylipäätänsä aiotaan saada.
Tietenkin TM on oikeassa siinä, että tämä on pelkkää semantiikkaa, koska käytännössä jokaisessa yksittäistapauksessa tiedetään miten toimia kulloinkin.
Lähetä kommentti