Ohjelmoinnin filosofia

Looginen ajattelu === hyvä ohjelmisto

Ohjelmointi on uusi lukutaito. Mutta miten kirjoitamme hyviä ohjelmia? Tässä on toistuvia kysymyksiä, jotka meidän on ratkaistava:

  • Kuinka keksimme algoritmiset ratkaisut ongelmaan?
  • Mistä sitten tiedämme, että ratkaisu todella toimii?
  • Vaikka olemme varmoja, että se toimii, miten voimme käskeä tietokonetta suorittamaan se?

Hauska tosiasia - jos sinulla on vaikeuksia jauhaa mitään näistä kysymyksistä, teet itse asiassa filosofiaa.

Selvitämme miksi mielenkiintoisia yhtäläisyyksiä ohjelmoinnin ja filosofisen päättelyn välillä.

Ensimmäinen periaate: sinun on ajateltava kovasti.

Tietokoneet eivät tee mitään älykkäämpiä kuin voimme - ero on siinä, että ne tekevät sen nopeammin.

Mutta he eivät pysty ratkaisemaan todellista ongelmaa, kuten "kuinka pääsen toimistooni kotoa?"

Tehokkaan menetelmän (periaatteessa) voi suorittaa ihminen ilman koneiden apua paperia ja lyijykynää lukuun ottamatta. - Church-Turing Thesis

Ohjelmoinnin ansio on edelleen perusteluosassa. Toisin sanoen reaalimaailman ongelman kääntäminen yksinkertaisiksi ohjeiksi, jotka tietokone voi suorittaa.

Eri ohjelmointikielillä on tietysti erilaiset semanttiset abstraktit. Python-ohjelma voi olla lyhyempi kuin C-vastine. Mutta se vain muuttaa käännösten määrää. Emme voi päästä eroon käännöstyöstä. Mutta jätämme tämän keskustelun myöhemmäksi.

Ohjelmoijan päättelyvirta

Nyt tuijotamme joitain ongelman kuvauksia. Voimme ensin etsiä pienimuotoisia panos-tuotos-esimerkkejä ongelman ymmärtämiseksi:

Induktio. Tarvitsemme algoritmin, joka pystyy käsittelemään tällaisia ​​esimerkkejä. Nyt teet induktiota: yleistät periaatteita kokemuksesta.

Vähennys. Mistä tiedämme, toimiiko se muulla tuntemattomalla syötteellä? Teemme vähennyksen todistaaksemme algoritmin oikeellisuuden.

Ontologia . Meidän on pidettävä tietoja tietokoneen muistissa. Tavoitteena on tehdä niistä tehokkaita tietokoneiden prosessointia varten. Mikä tietorakenne voi sanojen järjestyksessä parhaiten kaapata tietojeni dynaamisen kulun?

Induktio uudelleen . Sitten tulee aivan viimeinen vaihe: virheenkorjaus. Indusoimme ohjelman bugisen osan analysoimalla odottamattomia tuloksia.

Esimerkki

Tarkastellaan nyt yllä olevaa prosessia seuraamalla tätä todellista esimerkkiä: löytämällä lyhin polku pisteestä A pisteeseen E.

Pienissä ongelmissa voimme ratkaista ne vaistojen avulla. Kuten meille, on erittäin suoraviivaista tunnistaa ratkaisu ACE vain katsomalla.

Mutta entä monimutkaisemmat topologiat? Entä eri reunapainot?

Tarvitsemme apua tietokoneilta. Ei kuitenkaan ole suoraviivaista kertoa tietokoneelle, mitä tehdä. Ihmisten ajattelun ja tietokoneen toiminnan välillä on kuilu.

Prosessi

1. Yleistä kokemuksen perusteella: algoritmit

Jotta voimme kertoa tietokoneelle, mitä tehdä, meidän on ensin keksittävä algoritminen menettely.

Ahne strategiat ovat luonnollinen tapa edetä. Toisin sanoen alkaen lähdepisteestä A ja kulkemalla koko tunnettua lyhintä tietä pitkin. Jatka uusien huippujen tutkimista, kunnes saavutamme määränpään E.Ja tämä lähestymistapa todellakin tyydyttää esimerkkiamme.

Intuitio on, että lyhyimmällä polulla määränpäähän jokainen välisolmu vierailee myös lyhyimmällä polulla. (Tietysti tämä intuitio olettaa, että kaikilla reunoilla on positiivinen paino. Tämä ei välttämättä pidä paikkaansa sovelluksista riippuen. Keskustelemme tästä myöhemmin yksityiskohtaisesti).

Joten tässä on algoritminen menettely:

  1. Joitakin asetuksia: (1) kirjanpito vierailemissamme pisteissä: joukko ( visited), (2) muistaa tunnetut lyhyimmät etäisyydet kuhunkin kärkeen, joka käyttää vain löydettyjä pisteitä : toinen joukko distance(u). Jokaisen kärkipisteen etäisyys on alun perin ääretön, paitsi että kärkipiste on 0.
  2. Nyt alkaa tutkia: Ensin käydä kärki, jolla on tunnetut lyhintä tietä niin pitkälle, sanovat sen u. (Aluksi se olisi lähdepiste).
  3. Kun seisomme kärjessä u, katsomme ulospäin suuntautuvia reunoja. Jokainen reuna, esimerkiksi (u,v), antaa meille polun kärkeen, vjoka käyttää kärkeä uviimeisenä mutta ainoana askeleena. Jos joku heistä on todellakin lyhyempi polku vtai ensimmäinen vlöytämämme polku , hurraa, voimme päivittää lyhyimpien polkujoukkojemme nyt. Muussa tapauksessa ohita ja jatka.
  4. Olemme suorittaneet kärjen u, joten lisäämme sen visitedsarjaan.
  5. Palaa vaiheeseen 2, jatka tutkimista, kunnes olemme käyneet kaikissa pisteissä.

distancevoi nyt kertoa meille maailman lyhyimmät etäisyydet, koska sitä käytetään pitämään lyhyimmät etäisyydet vain vierailtujen solmujen avulla. Ja kaikki pisteet käydään, kun algoritmi on valmis.

Keksimme juuri uudelleen Dijkstran algoritmin. Tietenkin on olemassa monia muita algoritmeja lyhimmän polun löytämiseksi. Mutta asia on, tarvitsemme algoritmisen menettelyn ongelman ratkaisemiseksi.

2. Vahvista yleiset periaatteet vähentämällä

Kuinka voimme varmistaa, että algoritmin periaatteet ovat oikeita? Voimme joko lisätä luottamustamme testaamalla periaatetta useampien syötesimerkkien kanssa, tai tehokkaammin voimme löytää tiukan matemaattisen todistuksen.

Kuten filosofian a priori ehdotus, algoritmin oikeellisuus on riippumaton sen suorittamisesta. Toisin sanoen testaus ei voi taata algoritmien oikeellisuutta. Meidän on todistettava se.

Tässä on todistuksen perusvirta:

1. Kaikille vierailtuille pisteille löydämme lyhyimmät polut.

2. Kohteessa käydään.

3. Siksi löydämme lyhimmän polun määränpäähän.

Eivätkö ne näytä olevan jokseenkin tuttuja? Kuten tämä:

1. Kaikki miehet ovat kuolevaisia.

2. Sokrate on mies.

3. Siksi Sokrate on kuolevainen.

Itse asiassa tämä on sylogismi, klassinen deduktiivisen päättelyn muoto. Tätä logiikat tekevät melkein.

Toinen mielenkiintoinen historiallinen tosiasia: muodollisen laskennallisen käsitteen logiikkarit keksivät ensimmäisen kerran 1930-luvulla. Heidän oli tiedettävä, ovatko tietyt loogiset ongelmat todella ratkaistavissa ollenkaan (jotta he voisivat välttää ajanhukkaa ratkaisemaan jotain ratkaisematonta). Vastauksena siihen he keksivät käsityksen laskettavuudesta.

Myöhemmin vuonna 1936 Alonzo Church ja Alan Turing kehittivät laskettavuuden muodollisen määritelmän samanaikaisesti itsenäisesti. Tämä artikkeli antaa historiallisen katsauksen laskennasta.

Johtopäätöksen oikeellisuus riippuu kahdesta ensimmäisestä lähtökohdasta. Todistuksemme mukaan toinen lähtökohta on triviaali, koska algoritmimme käy kirjaimellisesti kaikissa solmuissa. Ensimmäisen lähtökohdan todistaminen siitä, että löydämme lyhimmän polun siihen mennessä, kun vierailemme solmussa, vaatii kuitenkin jonkin verran työtä.

Matemaattinen induktio voi auttaa. Se on itse asiassa yksi hyödyllisimmistä tekniikoista todistaa monien muiden algoritmien oikeellisuus.

Yleinen virtaus tapahtuu seuraavasti. Ensinnäkin, jos algoritmi toimii syötteellä 0, ja toiseksi, jos se, että se toimii syötteellä, nmerkitsee sitä, että se toimii myös syötteellä n+1 , se toimii kaikille syötteille, jotka ovat suurempia tai yhtä suuria kuin 0. Tässä vaiheessa voit taata algoritmin oikeellisuuden.

Yksinkertaisuuden vuoksi suosittelen sinua tähän luentoselosteeseen saadaksesi täydellisen todistuksen tälle polunhakualgoritmille.

Huomaa, että meidän ei pidä sekoittaa matemaattista induktiota ja filosofista induktiota. Filosofisen määritelmän mukaan matemaattinen induktio on deduktiivinen päättelyprosessi, koska sen oikeellisuus sisältyy sinänsä ilman ulkoisia havaintoja.

Oppitunti on: Kun keksimme algoritmin, sen pitäisi pystyä käsittelemään kaikki mahdolliset suoritustapaukset.

Käytännössä tiukan matemaattisen todistuksen läpikäynti ei välttämättä ole tehokkain strategia. Mutta ainakin haluamme tarkastella mahdollisimman monta teloitustapausta, etenkin kontradiktorisia. Tämä käytäntö parantaisi koodisi luotettavuutta.

Olet ehkä huomannut, että esimerkissä polunhakualgoritmissa se ei toimi, jos reunan paino on negatiivinen. Löydät syyn tästä luentosivulta. Negatiivisen painon käsittelemiseksi voit käyttää Bellman-Ford-algoritmia.

3. Ontologiaongelma: tietorakenne

Toistaiseksi olemme vakuuttaneet itsemme siitä, että meillä on oikea algoritmi. Mutta tämä on vasta puolet taistelusta.

Seuraava kysymys on, miten syötämme tietoja tietokoneisiin? Ihmiset pitävät visualisoidusta tiedosta, kuten kaavioista tai histogrammeista. Mutta nykypäivän tietokoneet käsittelevät vain binaaribittejä.

Meidän on keksittävä tietorakenne, joka sisältää olennaiset tiedot. Ja sen pitäisi olla tehokasta, jotta ohjelma prosessoituu samanaikaisesti.

Jatketaan tietä etsimällä esimerkkiä. Polku on järjestetty luettelo. Mutta on ärsyttävää käsitellä, verrattuna kokonaislukuun. Huomaa, että algoritmistamme meidän on löydettävä lyhin polku löydetyistä poluista. Ja sitten iteroida aina loppuun asti. Näyttää siltä, ​​että meidän on omistettava taulukko tai muisti kunkin polun tallentamiseksi.

Voisimmeko tehdä paremmin? Huomaa, että kelvollisella polulla elementtien peräkkäisten esiintymien on vastattava kaavion reunaa. Mutta meillä on jo reunatiedot ja ne ovat samat kaikille poluille. Miksi emme voi päästä eroon näistä tarpeettomista tiedoista?

No, voimme päästä eroon luettelosta. On käynyt ilmi, että lyhimmän polun keräämiseksi välivaihe on määrittää, mikä on seuraava hypätä, jonka sinun on mentävä. Ainoa mitä meidän on haettava lyhyin polku lähteestä A mihin tahansa kohdesolmuun, on vain kaavio itse ja lyhin etäisyys A: sta jokaiseen solmuun.

Visuaalinen esitys on yllä olevassa kuvassa. Tämä esitys on muistia tehokas. Se on myös tehokkaampi ohjelman prosessoimiseksi.

Näin se rakentaa lyhimmän polun käyttämällä vain etäisyysvektoria. Aloita kohdepisteestä ja tyhjältä polulta. Etsi välipisteet saapuvien reunojen kautta. Valitse se, jonka arvo on pienin distance. Lisää se polun päähän. Toista, kunnes pääsemme lähteeseen. Tällä temppulla on itse asiassa muodollinen merkintätapa, jota kutsutaan takaseurannaksi.

Filosofit etsivät ikuista totuutta. Ja ohjelmoijat haluavat selvittää tarkan tietorakenteen, joka parhaiten kuvaa tiedon dynamiikkaa. Kuten näet polunetsintäesimerkissä, kaikki mitä se tarvitsee lyhimmän polun antamiseen on vain vektori, joka kertoo sinulle lyhyimmät etäisyydet kuhunkin kärkeen. Tämä pätee mihin tahansa kaavioon pisteiden tai reunojen lukumäärästä riippumatta.

4. A posteriori -ehdotus: virheenkorjaus

Useimmat ohjelmoijat ovat käyneet tämän perustelun läpi useita kertoja. Lyön vetoa, että tämä on vaikein ja aikaa vievä osa ohjelmointitehtäviä.

Esimerkiksi segmentointivirheet C-ohjelmissa johtuvat usein nollaosoittimen viitteistä. Olen oppinut tämän käsittelemällä tonnia C / C ++ -segmenttivirheitä. Tietysti on hienovaraisempia tapauksia, jotka liittyvät henkilökohtaisiin ohjelmointitottumuksiin.

Seuraava esimerkki on ohjelmoijan tekemä syntaksivirhe. If-ehdon olisi pitänyt olla is_float==1, mutta ohjelmoija erehtyi loogisen yhtäläisen operaattorin ==arviointiin =. Tämä läpäisee edelleen kääntäjän tarkastuksen, koska jompikumpi on oikea syntaksin.

if (is_float = 1) { // do something}

Tämä on induktiivinen päättelyprosessi. Virheenkorjausdiagnoosisi on järkevää vain, jos olet havainnut tarpeeksi ohjelman suorituksia.

Tässä tulee käytännön arvo. Riippumatta siitä, minkälaisia ​​tekniikoita opit, sinun on kerättävä tarpeeksi käytännön tietoja. Muuten sinulla ei olisi tarpeeksi kokemusta induktion suorittamiseksi.

Sinun tulisi pitää silmällä vikakoodiesi toistuvia malleja. Kun löydät virheen, sen korjaaminen ei riitä. Tarvitset ylimääräisen syy-seurausanalyysin omassa ohjelmointikäytännössäsi. Kysy itseltäsi: onko tämä osa ohjelmointitapojani erityisen haavoittuvainen tällaisille virheille?

Joten miksi sillä on merkitystä?

Ohjelmointi ei ole vain koodin kirjoittamista, se on systemaattinen tapa päättää. Koska koodi tai ohjeet ovat vain keino saavuttaa päämäärä. Kehittämällä ohjelmasynteesitekniikkaa et voi edes vaivautua koodin kirjoittamiseen ja virheenkorjaukseen. Tärkeää on vain, jos voit kertoa tietokoneelle, mitä tehdä.

Ensimmäinen askel kohti ohjelmointitaitojesi parantamista, tämä artikkeli paljastaa taustalla olevan päättelymallin, jota emme ehkä edes tunnista ohjelmoinnin aikana. Suurin osa meistä luottaa alitajuntaan, automaattiseen heijastukseen suurimman osan päivittäisistä tehtävistämme. Mutta mistä parannus tulee? Ensinnäkin se tulee havaitsemaan joitakin virheitä tai virheitä, jotka teimme päättelyprosessissamme.

Käytännön neuvoja varten suosittelen tätä artikkelia ohjelmoijan ajattelusta ja tätä samaa aihetta käsittelevää kirjaa.

Viitteet

  • Laskenta, filosofiset kysymykset. Matthias Scheutz.
  • Kirkon Turingin opinnäytetyö.
  • Ajattele kuin ohjelmoija: Johdatus luovaan ongelmanratkaisuun. V. Anton Spraul.