Legjobb válasz
Erre nincs válasz.
Keressük meg a választ erre a problémára:
Q. Hogyan lehet megtalálni, hogy egy algoritmus jobban teljesít?
A. Az algoritmusok összehasonlításának leggyakoribb módjai:
1) Időkomplexitás
2) Térbonyolultság
3) A megoldás minősége (lehet, hogy nem alkalmazható, ha egy probléma pontos megoldását javasolja). Ez óriási tényező lehet, ha közelítő algoritmusokról beszélünk.
4) Az algoritmus egyszerű megvalósítása / adaptálása. Egyes algoritmusok sok rezsivel járhatnak a helyes megvalósításhoz. Van néha megfelelőbb algoritmus az alkalmazásához. Például párhuzamosan történő számítással a Bellman-Ford többsége hasznosabbnak találja a Dijkstra algoritmusánál, a Bellman-Ford működésének köszönhetően.
Az idő és a komplexitás azonban nem * mindig * a kívánt tulajdonság a maximalizáláshoz; Két példát hozok fel.
Az egyik a “numerikus stabilitás” , az algoritmusok jellemzője mind a lineáris algebrában, mind a differenciálegyenletekben. Több algoritmikus időt és nagyobb algoritmikus bonyolultságot fordítunk számszerűen stabilabb algoritmusokra. A lineáris algebrában az instabilitás általában akkor fordul elő, ha egy algoritmus a nullához vagy a végtelenhez vagy mindkettőhöz túl közel eső számokkal találkozik, mivel a számok véges ábrázolása miatt a felbontás elveszhet. Általában ez nagyon kissé eltérő számokat okoz, csak néhány epsilon különbözik egymástól (ahol az epsilon a legkisebb szám, amelyet hozzá lehet adni az egyikhez, egy gépen, és eredményt kapunk! = 1), hogy nagy különbségeket produkáljon a válasz. Tehát például sok időt és helyet bonyolítunk azzal, hogy “elfordulunk” az LU-faktorizációban, hogy stabil algoritmust kapjunk; forgatás nélkül az LU nem stabil. Hasonlóképpen, vannak olyan algoritmusaink, amelyek az instabilitás elkerülése érdekében nem mást csinálnak, csak “feltétel” mátrixokat.
A második példa a “robusztusság” technikai statisztikai értelme. A robusztusság olyan mértéket vagy algoritmust jelent, amely * nem * érzékeny a kiugró értékekre. Tehát például, amikor a legkisebb négyzetes vonalat illesztem egy pontkészletbe, akkor a vonal erősen torzulhat egyetlen rendkívül nagy értékkel. Még akkor is, ha van 99 számpárom, amelyek tökéletes 45 fokos vonalat alkotnak, ha egyetlen olyan kiugró párot adok hozzá, amelynek az Y értéke százszorosa annak, aminek “kellene” lennie, ugyanarra a vonalra esik, akkor az illesztett vonal súlyosan ferde a 45 fokos vonaltól. Az algoritmus “feladja” a 99 pontra való tökéletes illeszkedést annak érdekében, hogy jobban képviselje az egy kiugró pontot. Ez * nem * robusztus.
A robusztus legkisebb négyzetek megközelítés helyett az a vonal keresése, amely minimalizálja az adott vonal használatával létrehozott négyzetes hibák összegét, megtalálja azt a vonalat, amely minimalizálja a az adott vonal használatával létrehozott négyzetes hibák. A példában ez a vonal a 45 fokos vonal, és a négyzetes hibák mediánja nulla, és a kiugró pontot (és akár 98 további őrült kiugró értéket) teljesen figyelmen kívül hagynánk. Megtalálható lenne a 45 fokos vonal.
Hasonló robusztus algoritmusok léteznek statisztikai görbék illesztésére, alakzatok keresésére stb. Ezek azonban időben költségesek, néha súlyosan. De az időköltség megéri, mert a megbízható statisztikák hatékonyan védettek a jelek “zajától”, ahol a legkevesebb négyzetes hiba megközelítések nem. A való világ tele van zajjal és szélsőségekkel, amelyek közül néhányat emberi vagy gépi hibák okoznak, különösen pixeles képekben vagy mintavételezett hangban. Ilyen körülmények között egy időigényesebb robusztus algoritmus olyan zajos környezetben talál jeleket, ahol a gyorsabb algoritmusok a zaj által annyira elrontott válaszokat eredményezik, amelyek haszontalanok, vagy elfogadhatóak is veszélyesek.
Bizonyos esetekben az idő és a tér komplexitása közel sem olyan fontos, mint a zaj és a jel romlása ellenére a tényleges jel modellezésére legvalószínűbb választ találni.
Válasz
A matematikából eredő algoritmusok „receptek” függvényalapú számítás elvégzéséhez, amely mechanikusan követhető. A függvényalapú matematikai világnézetben az összes bemenetet meg kell adni a számítás elején, amely zárt dobozban halad. Az algoritmus fogalma eleve informális, mivel az algoritmikus leírás nem korlátozódik egyetlen nyelvre vagy formalizmusra sem.
Talán a legrégebbi példa Euclid algoritmusa a közös osztók megtalálásához. Az algoritmusok megragadják, hogy mit jelent egy számítás “hatékony”. A matematikai képletekhez hasonlóan az algoritmusok megmondják, hogyan kell kiszámítani az értéket; velük ellentétben az algoritmusok magukban foglalhatják azt, amit most hurkoknak vagy elágazásoknak nevezünk.
Az algoritmus szerepe: Adva néhány véges x bemeneti értéket, egy algoritmus leírja az y kimeneti értékre való hatékony átalakítás lépéseit, ahol y f (x) néhány rekurzív f függvényhez.
Az algoritmusokat a korai informatikusok az 1950-es években fogadták el, és megalkották az algoritmusok és a Turing Machines (TM, az 1936-ból származó formális számítási modell) közötti kapcsolatot, egyenlővé téve azok expresszivitását.
Knuth híres és befolyásos tankönyve, a „The Computer of Computer Programming, Vol. 1” az 1960-as évek végén népszerűsítette az algoritmusok központi jelentőségét a számítástechnikában. Az algoritmusok meghatározásában Knuth összhangban állt a számításelmélet matematikai függvényalapú alapjaival. “A hatékony számítási módszer koncepciójának megfogalmazására számos más, lényegében egyenértékű módszer létezik (például TM használatával).”
Knuth kifejezetten meghatározta, hogy az algoritmusok zárva vannak; a számítás megkezdése után nem fogadunk el új bevitelt: “Egy algoritmusnak nulla vagy több bemenete van, azaz olyan mennyiségek, amelyeket kezdetben az algoritmus megkezdése előtt adtak meg neki.” Megkülönböztette az algoritmusokat az önkényes számítástól, amely I / O-t is magában foglalhat. Az egyik, nem algoritmikus problémára adott példa a következő utasítás egy receptből: „könnyedén dobáljuk, amíg a keverék össze nem omlik”. Ez a probléma nem algoritmikus, mert lehetetlen, hogy a számítógép tudja, meddig keverhető; ez függhet egy olyan dinamikusan változó külső körülménytől, mint például a páratartalom, amelyet nem lehet előre megjósolni idő előtt.
Bár nincs egyetértés az algoritmusok pontos fogalmáról, Knuth algoritmusainak tárgyalása továbbra is meghatározó. p>
Az első magas szintű programozási nyelv, amelyet kifejezetten az algoritmusok meghatározására fejlesztettek ki, az ALGOL (ALGOrithmic Language) volt. Az 50-es évek végén bemutatták és az 1960-as évekig finomították, és ez szolgált az algoritmusok publikálásának mércéjeként. Az algoritmusok függvényalapú konceptualizálásához hűen az ALGOL nem adott konstrukciót a bemenetre és a kimenetre, figyelembe véve ezeket a műveleteket az algoritmusok gondjain kívül. (Nem meglepő, hogy ez a hiány megakadályozta az ALGOL ipar általi alkalmazását a kereskedelmi alkalmazások területén.)
Az 1960-as években megszaporodtak az egyetemi informatikai (CS) programok. A Association for Computing Machinery (ACM) szerint az USA-ban a CS-programok száma 1964-ben 11-ről 1968-ra 92-re nőtt. Ezt a növekedést intenzív tevékenység kísérte ezen új tudományág legitimitásának megalapozása érdekében az akadémikusok szemében. közösség. Az ACM központi szerepet játszott ebben a tevékenységben. 1965-ben a CS mint diszciplína igazolását és leírását fogalmazta meg, amely az egyetemi CS programokra vonatkozó 1968-as ajánlásainak alapjául szolgált.
Az ACM CS leírása központi kérdésként határozta meg az információ hatékony átalakítását: „ A számítástechnika nagyjából ugyanabban az értelemben foglalkozik az információkkal, mint a fizika az energiával … A számítógépes tudós érdekelt abban, hogy felfedezze azokat a pragmatikus eszközöket, amelyek segítségével az információ átalakítható. ” Ez a leírás az algoritmusokat a számítástechnika középpontjába helyezi, mivel ezek a “receptek” a bemenetek és a kimenetek effektív transzformációinak végrehajtására. Valójában az ACM a jelentésük következő mondatában kifejezetten az algoritmusokra helyezte a hangsúlyt:
„Ez az érdeklődés felveti az információ képviseletének hatékony módszereit, az információ átalakítására szolgáló hatékony algoritmusokat, a hatékony kifejezésnyelveket. algoritmusok … és hatékony módszerek ezek ésszerű költségekkel történő megvalósítására. ”
Ha egy központi algoritmikus aggodalomra volt szükségem, hasonlóan a fizikai energiával kapcsolatos aggodalmakhoz, akkor ez segített abban, hogy a CS mint legitim tudományos fegyelem megalapozzuk a fizika. Az algoritmusok a mai napig központi szerepet töltenek be a számítástechnikában.
A megoldható problémák meghatározásának informális (algoritmus-alapú) és formális (TM-alapú) megközelítésének együttélése a mai napig fennáll, és megtalálható itt: az összes modern tankönyv algoritmusokról vagy számíthatóságról. Ez nagyon kényelmesnek bizonyult a számítástechnikusok számára, mivel lehetővé tette számunkra az algoritmikus számítás informális leírását „pszeudokód” segítségével, azzal a tudattal, hogy ekvivalens Turing Machine is felépíthető.
– A probléma megoldható, ha megoldható algoritmus határozza meg. – Egy probléma megoldható, ha létezik rá egy Turing-gép.
A teoretikusok és oktatók 1960-as döntése, miszerint az algoritmusokat a CS középpontjába helyezik, egyértelműen tükröződött a korai egyetemista tankönyvekben. Az algoritmusnak azonban nem volt kifejezetten szabványos meghatározása, és a különféle tankönyvek úgy döntöttek, hogy ezt a kifejezést eltérően definiálják. Míg egyes tankönyvek, mint például a Knuth által írtak, ügyeltek arra, hogy az algoritmusokat kifejezetten azokra szűkítsék, amelyek kiszámítják a függvényeket, és ezért egyenértékűek a Turing Machines-szel, a legtöbb elméleti könyv ezt a korlátozást hallgatólagosan, de kijelentés nélkül hagyta. Hopcroft és Ullman 1969-es tankönyve, amelynek későbbi kiadásait a mai napig használják: „Az eljárás véges utasítássorozat, amelyet mechanikusan végre lehet hajtani, például egy számítógépes programot …A mindig befejeződő eljárást algoritmusnak nevezzük. ”
Az algoritmusok ez a leírása nem zárja ki kifejezetten a nem funkcionális számítást, például az ételkészítést. Különböző problémákra vonatkozó példáik azonban világossá teszik, hogy csak a függvényalapú számítást vették figyelembe. Valójában az ALGOL-t alkalmazták példáikra, amelyek nem is kínáltak semmilyen konstrukciót be- és kimenetre.
A 60-as évek vége óta a gyakorlatban használt és CS programokban tanított magas szintű programozási nyelvek már nem voltak a korai ALGOL algoritmikus korlátai kötik. Írhat olyan programokat, amelyek a számítás során folyamatosan kölcsönhatásba lépnek a környezetével, például operációs rendszerek, grafikus felhasználói felületek, vagy automatikus járművek és más robotok.
Válaszul válaszul olyan kortárs programozási tankönyvek, mint a Rice és a Rice (1969) kifejezetten kibővítette az algoritmusok fogalmát a nem funkcionális problémákra is. Ez a megközelítés, amely az algoritmusok központi jellegét tükrözi anélkül, hogy korlátozná őket a függvények kiszámítására, a nem elméleti tankönyvekre vált jellemzővé. Ezeknek a tankönyveknek a témája a programozás módszertana, nem pedig a számítás elmélete, és a számítási modelljeinket alátámasztó matematikai elveket a praktikum érdekében félretették.
A felszínen az algoritmus meghatározása A Rice and Rice és más hasonló tankönyvek nem különböznek Hopcrofttól és Ullmantól: „Az algoritmus recept, utasítások halmaza vagy valamilyen művelethez szükséges folyamat specifikációja. Ez valami általában valamilyen problémát megold. ” A kiszámítható problémákra vonatkozó példáik azonban már nem függvényalapúak, csak azt a fajta számítást ismerik el, amelyet Knuth elutasított. Két ilyen, állítólag algoritmussal megoldható példa: burgonyavodka készítése és árok homokkal való megtöltése; Knuth mindkettőjüket elutasította volna.
Ezek a tankönyvek nem állítottak TM-ekvivalenciát „algoritmusaik” vonatkozásában. A hallgatók azonban nem lettek tisztában azzal, hogy az algoritmusok ez a fogalma eltér Knuthétól, és hogy a kiszámíthatónak tekintett problémák összessége így bővült. Az algoritmusok (és ennélfogva a kiszámítható problémák) tágabb, praktikusabb koncepciójának összekapcsolásával olyan elméletekkel, amelyek azt állítják, hogy a nagyon kiszámítható problémát a TM-ek kiszámíthatják, az algoritmus-központú CS tanterv hibás benyomást tett a hallgatókra, hogy ez a tágabb probléma a TM-ek is megoldják.
Míg a gyakorlati informatikusok már régóta követik Rice és Rice vezetését, és az algoritmusok fogalmát kiszélesítik a függvények kiszámításán túl, az elméleti számítástechnika megtartotta a matematikai világképet, a számítást függvényalapúnak, és ennek megfelelően határolja be a számítási probléma fogalmát. Ez legalább egyetemi szinten igaz. Az eredmény egy kettősség, ahol a számítástechnikai közösség az algoritmusokat a számítás általános fogalmának („a számítógépek mit csinálják”) szinonimájának gondolja, ugyanakkor egyenértékű a Turing Machines-szal.
Úgy gondoltam Meg kellett írnom ezt a hosszú választ, hogy tudatosítsam az emberekben ezt a kettősséget. Mint az elején mondtam, az algoritmus fogalma informális. Úgy gondolhatjuk, hogy egyenértékű a funkciók (vagy a Turing Machines) kiszámításával, vagy felfoghatjuk úgy, mint bármi, amire programot írhat, beleértve a valós idejű interaktív programokat, például az operációs rendszereket vagy az automatikus autókat. De a két definíció nem egyenértékű, annak ellenére, hogy az ellenkezőjében gyakran zűrzavar van.