Algoritmisointi, algoritmit, kielet ja ohjelmat. Algoritmisointi ja ohjelmointi Esimerkkejä algoritmien ohjelmoinnista

Usein ilmestyy artikkeleita, kuten "tarvitsiko ohjelmoijat algoritmeja", ja niillä kaikilla on suunnilleen sama malli. Artikkelin kirjoittaja kirjoittaa yleensä: ”Olen kirjoittanut verkkosivustoja/skriptejä 1C:ssä N vuoden ajan, enkä ole koskaan käyttänyt algoritmeja tai tietorakenteita. He antavat esimerkkejä myös punamustista puista tai muista eksoottisista rakenteista, joita tekijän työskentelyalueella ei useinkaan nähdä, jos ollenkaan. Tällaiset artikkelit tiivistyvät siihen tosiasiaan, että ohjelmoijat eivät käytä tietyllä alueella monimutkaiset rakenteet dataa eivätkä ratkaise NP-ongelmia.

Tällaisen kysymyksen muotoilu on pohjimmiltaan virheellinen. Alan erikoisalojen määrä kasvaa jatkuvasti, ja .net-verkkosivuja kirjoittava henkilö tekee täysin eri asioita kuin antureiden ohjaimia kirjoittava henkilö. ARM-arkkitehtuuri eksoottisen käyttöjärjestelmän alla. Määritetään ensin mikä algoritmi on. Epävirallisesti Cormen määrittelee algoritmin hyvin määritellyksi menettelyksi, joka ottaa yhden tai useamman arvon syötteenä ja palauttaa tuloksena yhden tai useamman arvon. Muodollisesti algoritmi on määritelty erilaisia ​​malleja laskenta: operaatioita, jotka voidaan suorittaa Turingin koneella tai lambda-laskennan avulla. Joten käytännössä mikä tahansa koodi, joka tekee jotain, on algoritmi. Osoittautuu, että kysymys "tarvitseeko ohjelmoija algoritmeja" voidaan kääntää "pitääkö ohjelmoijan osata kirjoittaa koodia?" Oikean kysymyksen pitäisi olla jotain tällaista: "Tarvitseeko ohjelmoijan alalla X tietää edistyneitä algoritmeja ja laskennan teorian yksityiskohtia."

Jos katsot kaikkia näitä artikkeleita, huomaat, että yliopistot loukkaavat niitä kirjoittavia ihmisiä, koska heidän oli pakko oppia paljon monimutkaista materiaalia - algoritmisen analyysin, monimutkaisten algoritmien ja tietorakenteiden muodossa - mikä ei näyttävät olevan heille hyödyllisiä. Itse asiassa artikkeleiden kirjoittajat ovat loukkaantuneet yliopistoista, koska ne eivät kyenneet ennustamaan tekijöiden tulevaa työalaa ja antamaan heille vain vaadittua vähimmäistaitoa. Todellakin, jotta voit kirjoittaa yksinkertaisia ​​verkkosivustoja ja skriptejä, et tarvitse erityistä tietoa algoritmeista ja tietorakenteista. Vai onko se silti tarpeellista?

Mietitään, mitä ohjelmoijan tulee opiskella yliopistossa saadakseen tarvittavat taidot menestyksekkääseen uraan. Kirjastot? Kehyksiä? Ne vanhentuvat, niiden käyttöliittymät muuttuvat, ne kaikki on kirjoitettu useimmiten yhdellä kielellä, jota opiskelijat eivät ehkä koskaan käytä alalla. Pitäisikö meidän opettaa kaikille verkkosivustojen kirjoittamiseen? Tai opettaa kaikille kirjoittamaan käyttöjärjestelmä? Koulutuksen tulee tavoittaa mahdollisimman laaja yleisö ja tarjota mahdollisimman laaja valikoima taitoja. Ohjelmoijan on ensinnäkin kyettävä analysoimaan ja ratkaisemaan ongelmia - tämä on tärkein taito, joka tietojenkäsittelytieteen valmistuneiden tulisi hankkia. Koodin kirjoittaminen on helppoa tarvittava työkalu, jota käytetään ongelmien ratkaisemiseen. Kuka tietää, mitä taitoja tarvitset tulevaisuudessa? Oppimisteoria on siis koulutuksen kannalta optimaalisin. Hankittuja taitoja voidaan soveltaa millä tahansa alalla, eikä kirjaston tai viitekehyksen oppiminen hyvällä tietopohjalla ole vaikeaa. Paradoksi on, että ihmisillä, jotka kysyvät algoritmien tarpeesta, on yleensä jonkin verran tietoa tällä alalla. En muista ainuttakaan henkilöä, jolla ei olisi ollut tietoa laskennallisen teorian alalla ja joka ylpeänä huusi siitä väittäen, ettei hän sitä tarvinnut.

Olet siis abstrakti ohjelmoija tyhjiössä, olet työskennellyt yli kymmenen vuoden ajan kotisivujen kokoamisessa ja yksinkertaisten, samankaltaisten asiakkaiden/yritysten ongelmien ratkaisemisessa. Tunnet olosi hyväksi ja mukavaksi omassa markkinarakossasi ja tunnet vain tuskallista tuskaa hukatusta ajasta laskennallisen teorian ja algoritmisen analyysin luokassa, joka ei antanut sinulle mitään. Aamulla, kun sytytät tupakkaa kahvikupin ääressä, filosofisten pohdiskelujen syvyydessä olemassaolon heikkoudesta ihmettelet: miksi ohjelmoijien, jotka eivät ratkaise monimutkaisia ​​ongelmia, tarvitsee tuntea algoritmit ja analyysin perusteet. Lyhyt vastaus on olla taitava ja käyttää tehokkaasti käytettävissä olevia työkaluja, mukaan lukien kieli, jolla kirjoitat. Algoritmien ja analyysin teoria ei opeta vain eksoottisia algoritmeja ja tietorakenteita AVL:iden ja punamustien puiden muodossa. Se antaa myös ideoita tiedon tehokkaaseen järjestämiseen ja koodin kirjoittamiseen maksimi suorituskyky, missä pullonkaula järjestelmässä on mahdollinen ja miten sitä käsitellään. Sinut tutustutaan valmiisiin ratkaisuihin, jotta et kirjoita polkupyöriä etkä juokse Googleen joka kerta, kun sinun täytyy tehdä jotain ei-triviaalia.

Analyysiteorian ja algoritmien tietämystä käyttävät itse asiassa kaikki ohjelmoijat päivittäin, olemme vain niin tottuneet näihin asioihin, että emme edes ajattele sitä. Riippumatta siitä, minkä ongelman ratkaiset - olipa kyseessä yksinkertainen verkkosivusto, jossa tietoja haetaan tietokannasta, tai bash-skripti palvelimella, käytät jonkinlaisia ​​tietorakenteita. Ainakin primitiivinen taulukko ja todennäköisesti jotain monimutkaisempaa. Kielet antavat meille monia erilaisia ​​rakenteita, joista monia käytetään vaihtokelpoisina. Usein meillä on useita saman abstraktin tyypin muunnelmia erilaisilla toteutuksilla. Esimerkiksi C++:ssa on vektori- ja listatietorakenteet. Miten ne eroavat toisistaan, ja mitä etuja ja haittoja jommankumman käytöstä olisi? Miten kartta toteutetaan C++:ssa ja miten se eroaa multimapista? Miten lista toteutetaan Pythonissa - taulukon tai linkitetyn listan kautta ja mikä on paras tapa työskennellä sen kanssa? Miksi ei ole suositeltavaa käyttää ArrayList-luetteloa C#:ssa ja sen sijaan käyttää Listaa? Miten SortedDictionary toteutetaan ja miten se vaikuttaa ohjelman suorittamiseen, jos sitä käytetään sanakirjan sijaan? Miten jatkaminen toimii, milloin sitä pitäisi käyttää ja onko sen käytössä sivuvaikutuksia? Milloin viimeksi käytit curry-funktioita, joita löytyy melkein kaikilla kielillä? Jos luulet, että kartta C++:ssa on toteutettu hash-taulukona, olet väärässä. Se on toteutettu punamustissa puissa ja hash-taulukon toteuttaa unordered_map. Erikseen mainitsemisen arvoinen dynaaminen ohjelmointi. Sen ymmärtäminen, mitä se on, kuinka rekursiiviset funktiot voidaan kirjoittaa uudelleen optimaalisesti ja mitä memoisointi on, auttaa usein välttämään ampumisen itseäsi jalkaan. Täten voidaksesi käyttää täysin ja tehokkaasti kirjoittamaasi kieltä, sinulla on jo oltava ainakin pintapuolinen tieto tietorakenteista, mitä ne ovat ja miten ne voivat vaikuttaa ohjelman suorittamiseen.

Entä kirjastot? Loppujen lopuksi ne ratkaisevat niin monia ongelmia! Jotta voit käyttää kirjastoja tehokkaasti, sinun on myös ymmärrettävä ne. Ensinnäkin kirjastojen funktioilla voi olla sivuvaikutuksia tai käyttäytymistä, jota et tietäisi ymmärtämättä algoritmeja. Saatuasi virheen tässä tapauksessa voit yrittää pitkään ja lujasti saada se kiinni ja päättää, milloin se olisi voitu välttää. Toiseksi, erilaisia ​​työkaluja ja kirjastoja on usein ”räätälöitävä” – kerrottava, mitä algoritmeja, tietorakenteita ja teknologioita tulee käyttää sisäisesti. Ilman perustietoja joudut joko lukemaan manaa tai valitsemaan satunnaisesti. Kolmanneksi on monia ongelmia, joita ei voida ratkaista yksinkertaisesti kutsumalla kirjaston tai kehyksen API:ta. Mitä aiot tehdä tässä tapauksessa? Vietä tunteja etsimiseen mahdolliset ratkaisut ja pyydä ystävältä apua? Neljänneksi monet ongelmat voidaan ratkaista hyvin yksinkertaisesti muutamalla koodirivillä tai sisäänrakennetuilla kielityökaluilla. Jos vedät kirjaston jokaisen ongelman ratkaisemiseksi, ohjelmasi ovat jättimäisiä hirviöitä, jotka vievät satoja megatavuja tai enemmän levyllä, syövät kaiken palvelimen muistin ja samalla niillä on melko niukka toiminnallisuus. Lisäksi mukana olevien kirjastojen joukon läsnäolo aiheuttaa yhteensopivuusongelmia, ja ohjelma voi kaatua satunnaisesti useiden kirjastojen oudon käytöksen vuoksi yhdessä projektissa. Kirjastojen harkitsematon käyttö voi johtaa varsin tuhoisiin seurauksiin, ja kehittäjiä, jotka vain osaavat käyttää kirjastoja, mutta eivät pysty ratkaisemaan yksinkertaistakaan ongelmaa yksin, ei koskaan arvosteta, koska heidän ratkaisunsa eivät ole kilpailukykyisiä.

Yksi ohjelmoija, jolla on yli kymmenen vuoden kokemus, työskenteli kanssani. Eräänä päivänä tarvitsimme toiminnon, jota käyttämämme kirjasto ei tuolloin tukenut: primitiivisen tekstin rivityksen johonkin visuaalisista komponenteista. Tämä "ohjelmoija" katsoi mitä standardi tarkoittaa tätä ei voida tehdä, ja totesi välittömästi, että tällaisen toiminnon toteuttaminen on mahdotonta. Ongelman ratkaisi kolmannen vuoden harjoittelija analyyttisillä aivoilla, joka kirjoitti yksinkertaisen algoritmin kahdessa tunnissa ja toteutti sen tarvittavaan komponenttiin. Perin toisen projektin .net-sivuston muodossa. Pääsivu koostui useista pienistä kaavioista ja latautui lähes 10 sekuntia. Kävi ilmi, että henkilö, joka alun perin teki tämän projektin, kasasi kauheita suunnitelmia kolminkertaisista sisäkkäisistä silmukoista, joiden ottaminen tietokannasta ja sitten sidominen kaavioihin kesti kauan ja surullista aikaa. Pienen refaktoroinnin jälkeen sivu latautui lähes välittömästi.

Voiko ohjelmoija pärjätä ilman algoritmien ja analyysiteorian tuntemusta? Ehkä tällaisia ​​"ohjelmoijia" on paljon. Olisi venyvää kutsua heitä ohjelmoijoiksi. Monet ohjelmoijat tulevat luokseni haastatteluihin, heillä on 10–15 vuoden kokemus, eivätkä he todella ymmärrä mitä tekevät ja miksi. Heillä on oma markkinarako, he kulkevat yrityksestä toiseen ilman, että he ovat niissä yli vuoden. Heillä on yleensä pieni joukko tehtäviä, jotka he voivat ratkaista, ja jos otat askeleen sivulle, henkilö on eksyksissä ja hänen on opetettava itselleen uusia taitoja. Tällaiset ihmiset kutsutaan projektiin, ja he pääsevät eroon mahdollisimman nopeasti, koska he tuhlaavat paljon aikaa pyörien uudelleen keksimiseen ja manan lukemiseen oppiakseen, mitä heidän olisi pitänyt tietää jo yliopistosta. Yleensä heillä ei ole erityistä uraa ja epävakaita tuloja.

Loppujen lopuksi, miksi sinun täytyy tietää algoritmit ja analyysiteoria, jos voit tehdä työn ilman tätä tietoa? Jotta olet ammattisi pätevä asiantuntija, hanki urakehitystä ja kunnioitusta kollegoilta. Ratkaistaksesi ongelmia tehokkaasti eikä keksiä pyörää uudelleen. Jotta ei kirjoitettaisi hirviöitä, joissa on valtava määrä kolmannen osapuolen kirjastoja, jotka vievät satoja megatavuja levyllä, syövät paljon palvelimen muistia ja kaatuvat säännöllisesti satunnaisesta syystä kuun vaiheesta riippuen. Käyttääksesi kirjoittamaasi kieltä tehokkaasti ja mahdollisimman laajasti. Tehdä tietoisia ja mielekkäitä päätöksiä kirjaston ja tekniikan valinnasta ongelman ratkaisemiseksi. Jos tehtäväsi on kirjoittaa SQL-kysely ja kirjoitat komennon konsoliin, niin haluan tuottaa sinulle pettymyksen: et ole ohjelmoija, olet käyttäjä, et todellakaan tarvitse algoritmeja ja muuta ja tuhlasit aikaasi yliopistossa, koska sellaiseen työhön se riittää kurssien suorittamiseen tai muutaman esittelykirjan lukemiseen itse.

Huomautus: Ohjelmointitieteen aine. Esimerkki ja algoritmin ominaisuudet. Ohjelmointiparadigmat (direktiivinen, olio- ja toiminnallinen logiikkaohjelmointi).

Tämä luku, joka aloittaa kurssin, palvelee kahta päätarkoitusta:

• valmistaa tarvittava teoreettinen perusta myöhempää hallintaa varten erilaisia ​​menetelmiä tietojenkäsittely, pienimuotoiset ohjelmointitaidot ja oikeiden, tehokkaiden ohjelmien rakentaminen;
• antaa käytännön ohjelmointiin tarvittavat vähimmäistiedot Java-kielestä ja näytteitä pienistä tyypillisistä ohjelmista.

Luvun teoreettiseen aineistoon tutustuessa saattaa tuntua, että se on irti käytännön tarpeista - Java-kielen erityisongelmien ratkaisemisesta. Toisaalta ohjelmointiongelmien ratkaisun pitäisi johtaa tietoiseen ymmärrykseen siitä, että oikean ja tehokkaan ohjelman kirjoittaminen ei ole ollenkaan niin yksinkertaista kuin miltä ensi silmäyksellä näyttää.

Tarvittavien teoreettisten perusteiden tunteminen mahdollistaa toisessa luvussa siirtymisen ohjelmien rakentamismenetelmien ja niiden oikeellisuuden osoittamisen menetelmien tutkimiseen - teoriaan, jota käytetään ohjelmien käytännön kirjoittamiseen rinnakkain siihen tutustumisen kanssa. Näin ollen kaksi näennäisesti täysin toisiinsa liittymätöntä materiaalin tutkimisen virtaa - teoreettinen ja käytännöllinen - sulautuvat yhdeksi seuraavassa luvussa. Toistaiseksi lukija voi vain uskoa tähän tietoon Kaikki yhteensä ensimmäisen luvun materiaali on välttämätön edellytys onnistuneelle siirtymiselle seuraavan luvun opiskeluun.

Ja viimeinen huomautus on puhtaasti tekninen. Java-kielen oppimisen ensimmäisessä vaiheessa on hyödyllistä kääntää huomio pois siitä tosiasiasta, että se on oliosuuntautunut, ja keskittyä algoritmin oikean toteutuksen oleellisiin ongelmiin. Tämä ei kuitenkaan ole niin helppoa - kirjoittaminen jopa kaikkein yksinkertaisin ohjelma se on mahdotonta ymmärtämättä OOP:n peruskäsitteitä. Tämän ongelman osittaiseen ratkaisemiseen käytetään erityisesti näihin tarkoituksiin luotua luokkaa Xterm, joka suojaa aloittelevaa ohjelmoijaa Java-kielen todellisen maailman monimutkaisuuksilta.

Ohjelmointitieteen aine

Ihmisten on jo pitkään täytynyt luoda kuvauksia toimenpiteistä, joita tarvitaan jonkin tavoitteen saavuttamiseksi. Sellaiset kuvaukset voidaan suunnitella ihmisten tai automaattisten laitteiden suoritettaviksi. Ihmisille kirjoitetut tekstit ovat yleensä jonkin verran epämääräisiä ja epämuodollisia. Esimerkkinä voisi olla lause kulinaarisesta reseptistä nipistys suola. Vain erittäin kokenut henkilö pystyy suolaamaan astian oikein tällaisen suosituksen mukaisesti.

Tämä esimerkki selittää, miksi sekvenssikuvaukset on tarkoitettu automaattinen laite, on oltava täysin yksiselitteinen ja määritelty jollakin muodollisella merkintäjärjestelmällä. Hyvin usein tällaisten kuvausten luomiseen liittyy merkittäviä teknisiä ja perustavanlaatuisia vaikeuksia. Tämä ongelma on tullut erittäin tärkeäksi elektronisten tietokoneiden (tietokoneiden), joita käytetään usein nimellä .

Kutsutaan kuvaus toimintosarjasta, joka on riittävän tarkka, jotta se voidaan suorittaa jollain automaattisella laitteella algoritmi. Yleensä tämä sekvenssi kirjoitetaan (koodataan) jollakin muodollisella merkinnällä. Tässä tapauksessa kutsutaan muodollista järjestelmää, joka on suunniteltu kirjoittamaan algoritmeja algoritminen kieli, itse algoritmin teksti - ohjelmoida, ja sen luomisprosessi on ohjelmointi.

Tietokone Tiede tutkii algoritmien ominaisuuksia ja kehittää menetelmiä ohjelmien rakentamiseen. Se on asemaltaan ja menetelmiltään soveltavan matematiikan ala. Kaikki yritykset lähestyä ohjelmointia teknisenä tieteenalana ja luoda ohjelmia teollisena tuotannona ovat aina epäonnistuneet.

Huomaa, että yllä olevan algoritmin "määritelmä" on melko epämääräinen eikä itse asiassa ole määritelmä. Matematiikassa algoritmille on useita hyvin selkeitä määritelmiä, jotka vastaavat toisiaan, ja useimmat niistä eivät ole liian vaikeita ymmärtää. Ne kaikki edellyttävät kuitenkin hyvää tietämystä tietyillä alueilla matematiikkaa ja siksi meitä ei aluksi häiritse (erittäin tärkeät ja mielenkiintoiset) yksityiskohdat, jotka ovat välttämättömiä algoritmin käsitteen tiukkaa esittämistä varten. Sen sijaan tarkastellaan esimerkkialgoritmia ja luetellaan sitten perusominaisuudet, jotka kaikilla algoritmilla tulisi olla.

Tieteessä on hyvin tyypillinen lähestymistapa, jossa käytetään aktiivisesti jotakin epäselvästi määriteltyä käsitettä. Esimerkiksi luonnollisten ja reaalilukujen tarkkoja määritelmiä ei oteta huomioon paitsi lukiossa, myös useimmissa yliopistoissa. Lisäksi he sanovat, että tuhatjalkainen jopa unohti kävellä, kun hän ajatteli järjestystä, jossa hän järjesti jalkansa uudelleen.

Esimerkki ja algoritmin ominaisuudet

Meidän on ratkaistava ongelma löytää pienin alkujakaja luonnolliselle luvulle, joka on suurempi kuin yksi. Muistutetaan tästä yksinkertainen on luku, jolla ei ole muita jakajia kuin yksi ja itse, ja yksi ei sisälly alkulukujen joukkoon. Näin kirjoitamme tähän kirjaan ongelmien muotoilut ja niiden ratkaisut:

Ongelma 1.1. Keksi algoritmi, joka ottaa käyttöön luonnollisen luvun, joka on suurempi kuin yksi, ja löytää tämän luvun pienimmän alkujakajan.

Algoritmi ongelman ratkaisemiseksi.

Algoritmi P:

P1: Aseta kokonaisluku kahdeksi ja siirry vaiheeseen P2.

P2: Jos jaollinen luvulla , lopeta algoritmi tuottaen ; muussa tapauksessa siirry vaiheeseen P3.

P3: Suurenna arvoa yhdellä ja siirry vaiheeseen P2.

Ymmärtääksesi tämän algoritmin, sinun on toimittava tietokoneena (tai pikemminkin jopa yleinen komennon suorittaja), suorittaa manuaalisesti siinä määritellyt toimintosarjat joillekin pienille arvoille. Tallennamme määrän arvot jokaisen algoritmin vaiheen jälkeen.

k = 3	k = 4	k = 2
P1: i = 2	P1: i = 2	P1: i = 2
P2: i = 2	P2: i = 2	P2: i = 2
P3: i = 3
P2: i = 3

Tällainen tutkimus antaa aihetta uskoa, että algoritmin valmistumisen jälkeen muuttuja todellakin sisältää alkuperäisen luvun pienimmän alkujakajan. Tässä tapauksessa sen todistaminen ei ole vaikeaa ja se on täysin tiukkaa. Muista tehdä tämä.

Perusominaisuudet Minkä tahansa algoritmin äärimmäisyys, varmuus, syöttö (input), tuotos (lähtö) ja tehokkuus. Tarkastellaan niitä peräkkäin yksityiskohtaisemmin.

Raaja. Algoritmin tulee aina päättyä, kun äärellinen määrä vaiheita on suoritettu. Algoritmi P täyttää tämän ehdon, koska arvo on aluksi pienempi kuin , sen arvo kasvaa yhdellä jokaisella vaiheen P2 peräkkäisellä suorituksella, ja siksi algoritmin suoritus päättyy vaiheessa P2, jos , jos on alkuluku, tai aikaisemmin jos .

Varmuutta. Jokaisessa vaiheessa suoritettavat toimet on määriteltävä tiukasti ja yksiselitteisesti kaikissa mahdollisissa tapauksissa. Tässä esimerkissä käytetään melko spesifistä, vaikkakaan ei täysin muodollista merkintäjärjestelmää. Useimmiten algoritmit kirjoitetaan muodollisemmin algoritmiset kielet, kutsutaan myös ohjelmointikielet, jossa jokaisella lauseella on tarkka merkitys.

Tällä hetkellä ohjelmointikieliä on useita tuhansia, joista kymmeniä käytetään aktiivisesti. Tällainen suuri määrä kieliä johtuu sovellusalueiden moninaisuudesta, eroista laitteistoissa, joille ohjelmat kirjoitetaan, ja niitä kirjoittavien ihmisten koulutustasosta sekä useista opetuksista kirjoittaa ohjelmia (ns ohjelmointiparadigmat).

Syöte. Algoritmilla on aina tietty (joskus nolla) määrä syötetietoa eli arvoja, jotka lähetetään sille ennen työn aloittamista. Esimerkiksi algoritmissa P yksi syötearvo on yhtä suurempi kokonaisluku. Esimerkki algoritmista, jossa on tyhjä syötejoukko, on algoritmi, joka laskee 1000. alkuluvun.

Lähtö. Algoritmilla on aina oltava yksi tai useampi lähtöarvo. Algoritmin P tapauksessa tämä arvo on luku . Algoritmit, joilla ei ole tulosta, ovat käytännössä hyödyttömiä, emmekä tutki niitä.

Tehokkuus. Algoritmin on oltava tehokas. Tämä tarkoittaa, että kaikkien algoritmissa suoritettavien toimintojen on oltava riittävän yksinkertaisia, jotta ne voidaan periaatteessa suorittaa tarkasti ja rajallisessa ajassa kynällä ja paperilla. Algoritmissa P suoritetaan vain seuraavat toiminnot: kahta kokonaislukua verrataan, yksi positiivinen luku jaetaan toisella, muuttujalle annetaan kokonaisluvun kaksi arvo, sen arvoa kasvatetaan yhdellä.

Kaikki nämä toiminnot ovat tehokkaita yllä olevassa mielessä, koska kokonaislukuja voidaan kirjoittaa paperille äärellisellä tavalla ja on olemassa ainakin yksi tapa jakaa ja laskea kaksi kokonaislukua. Mutta samat toiminnot eivät olisi tehokkaita, jos algoritmissa esiintyvien suureiden arvot olisivat mielivaltaisia ​​reaalilukuja, jotka ilmaistaan ​​äärettöminä desimaalimurtoina, koska sellaisia ​​suureita ei voida edes kirjoittaa paperille äärellisessä ajassa.

Yllä olevasta seuraa, että tietokoneella melkein mahdotonta työskennellä reaalilukujen kanssa, mikä ilmeisesti saattaa tuntua sinusta epätodennäköiseltä. Tämä on itse asiassa totta. Lisäksi edes todellisia kokonaislukuja ei käytetä kovin usein tietokoneessa. Yleensä kokonaislukujen ja reaalilukujen joukkojen sijaan sinun on työskenneltävä niiden korvikkeiden kanssa

Knuth-Morris-Pratt-algoritmi

Knuth-Morris-Pratt (KMP) -algoritmi vastaanottaa syötteenä sanan X=xx... x[n] ja skannaa sen kirjain kerrallaan vasemmalta oikealle ja täyttää luonnollisten lukujen joukon l... l[n ], jossa l[ i]=sanan pituus l(x...х[i]) (funktio l on määritelty edellisessä kappaleessa). Sanoilla: l[i] on sanan x...x[i] pisimmän alun pituus, joka on myös sen loppu.

Mitä tekemistä tällä kaikella on alisanahaun kanssa?

Toisin sanoen, kuinka käytät KMP-algoritmia määrittämään, onko sana A sanan B alisana?

Ratkaisu. Sovelletaan KMP-algoritmia sanaan A#B, jossa # on erityinen kirjain, jota ei löydy A:sta eikä B:stä. Sana A on sanan B alisana silloin ja vain, jos se on taulukon l numeroiden joukossa. on luku, joka on yhtä suuri kuin sanan A pituus.

Kuvaa algoritmi taulukon l...l[n] täyttämiseksi.

Ratkaisu. Oletetaan, että ensimmäiset i-arvot l...l[i] on jo löydetty. Luemme sanan seuraavan kirjaimen (eli x) ja meidän on laskettava l.

Toisin sanoen meitä kiinnostaa sanan x...x alku Z. Sana Z" on sanan x...x[i] alku ja loppu. Mikään sana, joka on sanan x...x[i] alku ja loppu, ei kuitenkaan sovellu - sitä on noudatettava x-kirjaimella.

Saamme seuraavan reseptin sanan Z löytämiseen. Tarkastellaan kaikkia sanan x...x[i] alkuja, jotka ovat myös sen loppuja. Valitsemme niistä sopivat - ne, joita seuraa kirjain x. Sopivien joukosta valitsemme pisimmän. Lisäämällä sen loppuun x, saadaan haluttu sana Z. Nyt on aika käyttää tekemiämme valmisteluja ja muistaa, että kaikki sanat, jotka ovat sekä tietyn sanan alkua että loppua, voidaan saada käyttämällä funktiota l toistuvasti edellisestä jaksosta siihen.

Tässä on mitä tapahtuu:

(taulukko l..l[i] on täytetty oikein)

sillä aikaa kun minä<>n aloita

(len on sanan x..x[i] alun pituus, mikä on

sen loppu; yhä pidemmät alkut osoittautuivat

sopimaton)

while(x<>x) ja (len>0) alkavat

jos x=x alkaa

(x..x on pisin sopiva alku)

(ei sopivia)

Osoita, että juuri annetun algoritmin toimien määrä ei ylitä Cn:tä jollain vakiolla C.

Ratkaisu. Tämä ei ole täysin ilmeistä: jokaisen peräkkäisen kirjaimen käsittely voi vaatia useita iteraatioita sisäisessä silmukassa. Jokainen tällainen iteraatio pienentää kuitenkin len:tä vähintään 1:llä, jolloin l on huomattavasti pienempi kuin l[i]. Toisaalta, kun i kasvaa yhdellä, l[i]:n arvo voi kasvaa korkeintaan 1:llä, joten se ei voi pienentyä usein tai suuresti - muutoin lisäys ei kompensoi laskua.

Tarkemmin sanottuna voimme kirjoittaa eriarvoisuuden

l

(iteraatioiden määrä i:nnessä vaiheessa)<= l[i]-l+1

On jäljellä lisätä nämä epäyhtälöt kaikkiin i-arvoihin ja saada yläraja iteraatioiden kokonaismäärälle.

Käytämme tätä algoritmia selvittääksemme, onko sana X, jonka pituus on n, alisana sanalle Y, jonka pituus on m. (Kuinka tämä tehdään erityisellä #-erottimella, on kuvattu yllä.) Tässä tapauksessa toimien määrä on enintään C(n+m), ja myös käytetty muisti käytetään. Selvitä, kuinka käyttää muistia, joka on korkeintaan Cn (joka voi olla huomattavasti pienempi, jos haettu kuvio on lyhyt ja sana, josta sitä etsitään, on pitkä).

Ratkaisu. Käytämme KMP-algoritmia sanaan A#B. Tässä tapauksessa: laskemme arvot l,...,l [n] sanalle X, jonka pituus on n, ja muistamme nämä arvot. Seuraavaksi muistamme vain l[i]:n arvon nykyiselle i:lle - sen lisäksi ja taulukon lisäksi

l...l[n], emme tarvitse mitään laskelmiin.

Käytännössä sanat X ja Y eivät välttämättä ole peräkkäin, joten on kätevää tarkastella sanaa X ja sen jälkeen sanaa Y erillisinä silmukoina. Tämä poistaa myös erottimen käytön vaivan.

Kirjoita sopiva algoritmi (tarkistaa, onko sana X=x...x[n] alisana sanasta Y=y...y[m]

Ratkaisu. Ensin lasketaan taulukko l...l[n] kuten ennenkin. Sitten kirjoitamme seuraavan ohjelman:

(len - sanan X enimmäislatauksen pituus samaan aikaan

joka on sanan y loppu..j[j])

kun (len<>n) ja (j<>m) aloita

while(x<>y) ja (len>0) alkavat

(alku ei sovi, käytä siihen l-funktiota)

(löysi sopivan tai olit vakuuttunut sen puuttumisesta)

jos x=y alkaa

(x..x on pisin sopiva aloitus)

(ei sopivia)

(jos len=n, sana X törmättiin; muuten saavuimme loppuun

sana Y tapaamatta kertaakaan X)

Boyer-Mooren algoritmi

Tämä algoritmi tekee sen, mikä ensi silmäyksellä näyttää mahdottomalta: tyypillisessä tilanteessa se lukee vain pienen osan kaikista sen sanan kirjaimista, joilla tiettyä kuviota haetaan. Miten tämä voi olla? Idea on yksinkertainen. Olkoon esimerkiksi, että etsimme mallia abcd. Katsotaanpa sanan neljättä kirjainta: jos se on esimerkiksi kirjain e, niin kolmea ensimmäistä kirjainta ei tarvitse lukea. (Itse asiassa kuviossa ei ole e-kirjainta, joten se voi alkaa vasta viidennellä kirjaimella.)

Esittelemme tämän algoritmin yksinkertaisimman version, joka ei takaa nopeaa toimintaa kaikissa tapauksissa. Olkoon x...x[n] etsittävä malli. Jokaisen merkin s kohdalla löydämme sen oikeanpuoleisimman esiintymän sanasta X, eli suurimman k:n, jolle x[k]=s. Tallennamme nämä tiedot pos [s] -taulukkoon; jos symbolia s ei esiinny ollenkaan, meidän on kätevää asettaa pos[s]=0 (näemme myöhemmin miksi).

Kuinka täyttää pos-joukko?

aseta kaikki positiot arvoon 0

i:=1 - n aloita

Hakuprosessin aikana tallennamme viimeiseen muuttujaan sen sanan kirjaimen numeron, jonka vastapäätä näytteen viimeinen kirjain esiintyy. Aluksi viimeinen = n (näytteen pituus), sitten viimeinen kasvaa vähitellen.

(kaikki aiemmat näytteen sijainnit on jo tarkistettu)

viimeksi<= m do begin {слово не кончилось}

jos x[m]<>y aloita sitten (viimeiset kirjaimet ovat erilaisia)

viimeinen:=viimeinen+(n-pos.]);

(n - pos] on pienin näytesiirto,

jossa vastapäätä y on sama

kirjain näytteessä. Jos sellaista kirjettä ei ole ollenkaan,

sitten siirrämme sitä koko näytteen pituudelta)

jos nykyinen tilanne on sopiva, ts. Jos

x[i]..х[n]=y..y,

sitten ilmoita ottelusta;

Asiantuntijat suosittelevat tarkistamaan osumat oikealta vasemmalle, ts. alkaen näytteen viimeisestä kirjaimesta (jossa on ilmeisesti vastaavuus). Voit myös säästää hieman tekemällä vähennyslasku etukäteen ja tallentamalla ei pos [s], mutta n-pos [s],

nuo. kirjainten lukumäärä kuviossa, joka on kirjaimen viimeisimmän esiintymisen oikealla puolella.. Tämän algoritmin muunnelmat ovat mahdollisia. Sinulla voi olla esimerkiksi linja

korvattu

viimeinen:=viimeinen+(n-u),

missä u on x[n]-kirjaimen toisen esiintymisen koordinaatti kuviossa oikealta.

Mikä on helpoin tapa ottaa tämä huomioon ohjelmassa?

Ratkaisu. Kun rakennat taulukkoa pos kirjoittaa

kirjoittaa

viimeinen:=viimeinen+n-pos.];

Esitetty yksinkertaistettu versio Boyer-Moore-algoritmista vaatii joissakin tapauksissa huomattavasti enemmän n toimintoa (toimintojen määrä on luokkaa mn), häviäen Knuth-Morris-Pratt-algoritmille.

Esimerkki tilanteesta, jossa kaava ei sisälly sanaan, mutta algoritmi vaatii noin mn toimenpidettä tämän vahvistamiseksi.

Ratkaisu. Olkoon näyte tältä baaa... aa, ja sana itsessään koostuu vain kirjaimista a. Sitten jokaisessa vaiheessa ristiriita selvitetään vasta viime hetkellä.

Todellinen (ei yksinkertaistettu) Boyer-Moore-algoritmi takaa, että toimien määrä ei ylitä pahimmassa tapauksessa C(m+n). Se käyttää ideoita, jotka ovat lähellä Knuth-Morris-Pratt-algoritmin ideoita. Kuvitellaan, että verrasimme näytettä syöttösanaan oikealta vasemmalle. Tässä tapauksessa jokin Z:n pala (joka on näytteen loppu) osui yhteen, ja sitten havaittiin ero: näytteen Z:tä edeltää jotain erilaista kuin syöttösanassa. Mitä tällä hetkellä voidaan sanoa syöttösanasta? Se sisältää fragmentin, joka on yhtä suuri kuin Z, ja sen edessä oleva kirjain ei ole sama kuin näytteessä. Nämä tiedot voivat mahdollistaa kuvion siirtämisen muutaman aseman oikealle ilman riskiä, ​​että se jää huomaamatta. Nämä siirtymät tulisi laskea etukäteen jokaiselle otoksemme Z-päälle. Kuten asiantuntijat sanovat, kaikki tämä (siirtotaulukon laskeminen ja sen käyttö) voidaan tehdä C(m+ n) -toiminnoilla.

Rabinin algoritmi

Tämä algoritmi perustuu yksinkertaiseen ajatukseen. Kuvitellaan, että sanasta, jonka pituus on m, etsimme mallia, jonka pituus on n. Leikataan n-kokoinen ikkuna ja siirretään sitä syöttösanaa pitkin. Olemme kiinnostuneita vastaako laatikon sana annettua mallia. Kirjeiden vertaaminen kestää kauan. Sen sijaan korjaamme jonkin funktion, joka on määritelty sanoille, joiden pituus on n. Jos tämän funktion arvot laatikon sanassa ja näytteessä ovat erilaiset, ei ole sattumaa. Vain jos arvot ovat samat, sinun tulee tarkistaa kirjain kirjaimelta vastaavuus.

Mitä hyötyä tästä lähestymistavasta on? Se ei näytä miltään - loppujen lopuksi, jotta voit laskea funktion arvon sanalle ikkunassa, sinun on silti luettava kaikki tämän sanan kirjaimet. Joten on parempi verrata niitä välittömästi otokseen. Voittaminen on kuitenkin mahdollista, ja tässä on syy. Kun siirrät ikkunaa, sana ei muutu kokonaan, vaan vain kirjain lisätään loppuun ja poistetaan alusta. Olisi mukavaa, jos näitä tietoja voitaisiin käyttää laskemaan, miten funktio muuttuu.

Anna esimerkki funktiosta, joka sopii laskemiseen.

Ratkaisu. Korvataan kaikki sanan ja kuvion kirjaimet niiden numeroilla, jotka ovat kokonaislukuja. Sitten kätevä funktio on numeroiden summa. (Kun siirrät ikkunaa, sinun on lisättävä uusi luku ja vähennettävä puuttuva luku.)

Jokaiselle funktiolle on sanoja, joihin se soveltuu huonosti. Mutta tässä tapauksessa toinen toiminto voi toimia hyvin. Syntyy idea: sinun on tallennettava paljon funktioita ja valittava niistä satunnainen algoritmin alussa. (Silloin vihollinen, joka haluaa sotkea algoritmimme, ei tiedä mitä toimintoa taistella.)

Anna esimerkki kätevien toimintojen perheestä.

Ratkaisu. Valitaan jokin luku p (mieluiten alkuluku, katso alla) ja jäännös x modulo p. Käsittelemme jokaista sanaa, jonka pituus on n, kokonaislukujen sarjana (korvaa kirjaimet koodeilla). Käsittelemme näitä lukuja n-1-asteisen polynomin kertoimina ja laskemme tämän polynomin arvon mod p pisteessä x. Tämä on yksi perheen funktioista (jokaiselle parille p ja x saadaan siis oma funktio). Ikkunan siirtäminen 1:llä vastaa päätermin vähentämistä (xn-1 tulee laskea etukäteen), kertomista x:llä ja valetermin lisäämistä.

Seuraava huomio viittaa siihen, että sattumat eivät ole kovin todennäköisiä. Olkoon luku p kiinteä ja myös alkuluku, ja X ja Y kaksi eri sanaa, joiden pituus on n. Sitten ne vastaavat erilaisia ​​polynomeja (oletamme, että kaikkien kirjainten koodit ovat erilaisia ​​- tämä on mahdollista, jos p on suurempi kuin aakkosten kirjainten lukumäärä). Funktioarvojen yhteensattuma tarkoittaa, että pisteessä x nämä kaksi eri polynomia ovat samat, eli niiden erosta tulee 0. Ero on n-1-asteinen polynomi ja sillä on enintään n-1 juuria. Siten, jos u on paljon pienempi kuin p, niin satunnaisella x:llä on vähän mahdollisuuksia osua väärään pisteeseen.

Samanlaisia ​​asiakirjoja

Teoreettista tietoa. Peruskonseptit. Merkkijono, sen pituus, osamerkkijono. Algoritmin monimutkaisuuden käsite. Jaksottaiseen hakumenetelmään perustuvat algoritmit. Algoritmit Rabin, Knuth - Morris - Pratt, Boyer - Moore.

kurssityö, lisätty 13.6.2007


Organisaatio mahdollisuudesta tarkastella tekstitiedostoja ja etsiä tarvittavia sanoja tekstistä. Tekstin muokkaus (fontti, koko). Algoritmi alimerkkijonon etsimiseen merkkijonosta (Knuth-Morris-Pratt-menetelmä). Ladataan tekstiä tiedostosta (tunniste .txt).

kurssityö, lisätty 29.5.2013


Hae taulukoista ja luetteloista, avain- ja mielivaltaisista tiedoista. Lineaarinen (peräkkäinen) haku. Binäärihaku järjestetyssä taulukossa. Rabin-Karp-algoritmi, yksinkertainen ja parannettu hash-funktio. Boyer-Moore-algoritmi, jossa on stop by stop -merkit ja -liitteet.

esitys, lisätty 19.10.2014


Algoritmin käsitteen tutkiminen, lineaaristen ja haarautuvien algoritmien ominaisuudet. Algoritmin ominaisuudet: ymmärrettävyys, tarkkuus, diskreetti, massatuotanto ja tehokkuus. Ohjelman laatiminen funktion arvon laskemiseksi ja sen graafin piirtäminen.

testi, lisätty 25.3.2013


Opiskelu funktioiden määrittelystä, kuvauksesta ja kutsusta, osoittimista ja viittauksista niihin. Funktion kirjoittaminen kaksiulotteisen taulukon mielivaltaisen sarakkeen kertomiseksi const. Kerrotaan 2 taulukon saraketta vakioilla. Lohkokaavion laatiminen algoritmista ja ohjelmatekstistä.

laboratoriotyö, lisätty 1.9.2012


Algoritmin perusominaisuudet. Algoritmin muodollinen ja epävirallinen suorittaja, sen komentojärjestelmä. Menetelmät algoritmin kirjoittamiseen. Sanallinen kuvaus, rivi riviltä tallenne, tukeva yhteenveto. Algoritmisen kielen ominaisuudet. Algoritmin suorittaminen tietokoneella.

esitys, lisätty 4.4.2014


Sovellettujen ongelmien ratkaisun teoreettiset ja käytännön näkökohdat strukturoidun (modulaarisen) ohjelmoinnin funktioiden ja menettelyjen avulla. Algoritmikaavion ja taulukon z laskentaohjelman kehittämisen piirteet Turbo Pascal 7.0 -kielellä, niiden kuvaus.

kurssityö, lisätty 11.12.2009


Matriisihaun toteutusominaisuuksien ominaisuudet lineaarisella, binääri-, Fibonace-puulla ja ekstrapolaarisilla menetelmillä Turbo Pascal -kieliohjelmalla. Rabin-Karp- ja Knuth-Morris-Pratt-algoritmien mukauttaminen rivin löytämiseksi peräkkäin.

kurssityö, lisätty 16.9.2010


Geneettisen algoritmin toimintaperiaatteen kuvaus, sen toiminnan testaus funktioille valmiiseen ohjelmaan perustuvan vaihtoehdon mukaan. Geneettisen algoritmin perusparametrit, sen rakenne ja sisältö. Algoritmin ja sen komponenttien toteutusmenetelmät.

laboratoriotyö, lisätty 12.3.2014


Ohjausalgoritmin syklistä CRC-koodia käyttävän kokoonpanokielen kehittäminen tietylle muistialueelle tallennetulle tietojoukolle. Tallennetaan koodi myöhempää määräaikaista tietotaulukon tarkistusta varten. Tietojen korruptioviesti. Algoritmin kuvaus.

2.4.1. Perusalgoritmien käsite

2.4.2. Lineaarisen rakenteen algoritmit

2.4.3. Haaroitusrakenteiden perusalgoritmit ja esimerkkejä niiden ohjelmoinnista

2.4.4. Perusalgoritmit säännöllisille syklisille rakenteille ja esimerkkejä niiden ohjelmoinnista

2.4.5. Iteratiivisten syklisten rakenteiden perusalgoritmit ja esimerkkejä niiden ohjelmoinnista

2.4.6. Perusalgoritmit yksiulotteisten taulukoiden käsittelyyn

2.4.7. Perusalgoritmit kaksiulotteisten taulukoiden käsittelyyn

2.4.8. Testikysymykset aiheesta "Perusalgoritmit ja esimerkkejä niiden toteutuksesta"

2.4.9. Testitehtävät aiheesta "Perusalgoritmit ja esimerkkejä niiden toteutuksesta"

2.4.1. Perusalgoritmien käsite

Perustiedonkäsittelyalgoritmit ovat vuosikymmenten tutkimuksen ja kehityksen tulosta. Mutta niillä on edelleen tärkeä rooli laskentaprosessien käytön lisääntymisessä.

Ohjelmoinnin perusalgoritmeja ovat:

Yksinkertaisimmat algoritmit algoritmisten perusrakenteiden toteuttaminen.

Algoritmit tietorakenteiden parissa työskenteleminen. Ne määrittelevät perusperiaatteet ja menetelmät, joita käytetään algoritmien toteuttamiseen, analysointiin ja vertailuun. Antaa käsityksen datan esitysmenetelmistä. Tällaisia ​​rakenteita ovat linkitetyt luettelot ja merkkijonot, puut ja abstraktit tietotyypit, kuten pinot ja jonot.

Algoritmit lajittelu, jotka on suunniteltu järjestämään taulukoita ja tiedostoja, ovat erityisen tärkeitä. Lajittelualgoritmeihin liittyvät prioriteettijonot, valintaongelmat ja yhdistämisongelmat.

Algoritmit Hae, suunniteltu löytämään tiettyjä elementtejä suurista elementtikokoelmista. Näitä ovat perus- ja edistyneet hakumenetelmät puiden ja digitaalisten avainmuunnosten avulla, mukaan lukien digitaaliset hakupuut, tasapainotetut puut, hajautus ja menetelmät, jotka soveltuvat erittäin suurten tiedostojen käsittelyyn.

Graafialgoritmit hyödyllinen useiden monimutkaisten ja tärkeiden ongelmien ratkaisemisessa. Yleinen kuvaajahakustrategia kehitetään ja sitä sovelletaan perustavanlaatuisiin yhteysongelmiin, mukaan lukien lyhin polku, pienin virittävä puu, verkkovirta ja täsmäytysongelmat. Näiden algoritmien yhtenäinen lähestymistapa osoittaa, että ne perustuvat samaan menettelyyn ja että tämä menettely perustuu taustalla olevaan abstraktiin prioriteettijonotietotyyppiin.

Algoritmit merkkijonojen käsittely sisältää useita menetelmiä (pitkien) merkkijonojen käsittelemiseksi. Merkkijonon etsiminen johtaa kuvioiden täsmäämiseen, joka puolestaan ​​johtaa jäsentämiseen. Tiedostojen pakkausteknologiat voidaan myös liittää tähän luokkaan.

2.4.2. Lineaarisen rakenteen algoritmit

Esimerkki 2.4.2-1.

jossa x = -1,4; y = 0,8; muuttujat k ja k ovat kokonaislukutyyppiä, loput muuttujat ovat todellisia; [n] on luvun n kokonaislukuosa.

Kaavio algoritmista ja ohjelmista kielillä QBasic, Pascal, C++ on esitetty kuvassa. 2.4.2-1.

Huomaa, että kokonaislukumuuttuja k sai pyöristetyn arvon n, ja kokonaislukumuuttuja m- katkaistu funktiolla KORJATA() koko arvon osaan n.

Esimerkki 2.4.2-2. Laske ja näytä seuraavat arvot:

jossa x = 2,9512; y = 0,098633, muuttujat i ja j ovat kokonaislukutyyppisiä; loput muuttujat ovat reaalityyppisiä.

Algoritmikaavio ja ohjelmakoodit on esitetty kuvassa. 3.2.1-2.

Riisi. 2.4.2-2.

Ohjelman suorittamisen tulokset alkutietojen yllä olevilla arvoilla ovat seuraavassa muodossa:

Esimerkki 2.4.2-3. Laske ja näytä ensimmäisen pakonopeuden arvo.

Virallistetaan se. Pienin nopeus, jolla Maan vetovoimakentässä olevasta avaruusaluksesta voi tulla keinotekoinen satelliitti, on yhtä suuri

missä on gravitaatiovakio; M – Maan massa;
– etäisyys Maan keskustasta avaruusalukseen.

Algoritmikaavio ja ohjelmakoodit on esitetty kuvassa. 3.2.1-3.

Riisi. 2.4.2-3.

Ohjelman suorittamisen tuloksilla alkutietojen yllä olevilla arvoilla on seuraava muoto.