A programozás filozófiája

Logikai gondolkodás === jó szoftver

A programozás az új műveltség. De hogyan írunk jó programokat? Itt vannak a visszatérő kérdések, amelyeket meg kell oldanunk:

  • Hogyan juthatunk el egy probléma algoritmikus megoldásaival?
  • Akkor honnan tudjuk, hogy a megoldás valóban működik?
  • Még ha biztosak is vagyunk benne, hogy működik, hogyan mondhatjuk el a számítógépnek, hogy hajtsa végre?

Szórakoztató tény - ha nehezen tudja megalapozni ezeket a kérdéseket, akkor valójában filozófiát folytat.

Vizsgáljuk meg a programozás és a filozófiai gondolkodás néhány érdekes hasonlóságát.

Az első elv: keményen kell gondolkodni.

A számítógépek semmi okosabbat nem csinálnak, mint mi - a különbség az, hogy gyorsabb sebességgel csinálják.

De nem tudnak megoldani egy olyan tényleges problémát, mint például „hogyan juthatok el otthonról az irodámba?”

Hatékony módszert (elvileg) egy ember is elvégezhet, a papír és a ceruza kivételével bármilyen gépezet nélkül. - Az egyház-türingi tézis

A programozás érdeme továbbra is az érvelés részben rejlik. Vagyis a valós világ problémájának egyszerű utasításokká történő lefordítása, amelyeket a számítógép végrehajthat.

Természetesen a különböző programozási nyelvek különböző szintű szemantikai absztrakciókkal rendelkeznek. Lehet, hogy egy Python program rövidebb, mint C megfelelője. De ez csak megváltoztatja a fordítások mennyiségét. Nem szabadulhatunk meg a fordítási munkától. De ezt a vitát későbbre hagyjuk.

A programozó érvelésének folyamata

Most néhány problémaleírást bámulunk. A probléma megértéséhez először kis léptékű bemeneti-kimeneti példákat kereshetünk

Indukció. Szükségünk van egy algoritmusra, amely képes kezelni az ilyen példákat. Most indukciót folytat: általánosítja az alapelveket a tapasztalatok alapján.

Levonás. Honnan tudjuk, hogy működik-e más ismeretlen bemenetnél? Levonást végzünk algoritmusunk helyességének igazolására.

Ontológia . Az adatokat a számítógép memóriájában kell tartanunk. A cél az, hogy hatékonyak legyenek a számítógépek számára a feldolgozáshoz. Szavak szerint milyen adatstruktúra képes a legjobban megragadni az információim dinamikus áramlását?

Ismét indukció . Ezután jön a legvégső szakasz: hibakeresés. A program hibás részét a váratlan kimenetek elemzésével indukáljuk.

Egy példa

Most vizsgáljuk meg a fenti folyamatot, követve ezt a valós példát: az A csúcs és az E csúcs közötti legrövidebb út megtalálása.

Kis léptékű problémák esetén ösztönökkel oldhatjuk meg őket. Mint például, nagyon egyszerű számunkra a keresés alapján felismerni az ACE megoldást.

De mi van a bonyolultabb topológiákkal? Mi a helyzet a különböző élsúlyokkal?

Segítségre van szükségünk a számítógépekről. Mégsem egyenesen előre megmondani a számítógépnek, mit kell tennie. Rés van az emberek gondolkodása és a számítógép működése között.

A folyamat

1. Általánosítson tapasztalatokból következő elveket: algoritmusok

Ahhoz, hogy a számítógépnek megmondjuk, mit kell tennie, először ki kell dolgoznunk egy algoritmikus eljárást.

A kapzsi stratégiák természetes módon haladhatnak tovább. Vagyis az A forráscsúcsból indulva, és az ismert legrövidebb úton haladunk végig. Folytassa az új csúcsok felfedezését, amíg el nem érjük az E. célt. És valóban, ez a megközelítés kielégíti a példánkat.

Az az intuíció, hogy a cél felé vezető legrövidebb út mentén minden köztes csomópontot a legrövidebb úton is meglátogatnak. (Természetesen ez az intuíció feltételezi, hogy minden él pozitív súlyú. Ez az alkalmazásoktól függően nem biztos, hogy igaz. Ezt később részletesen megvitatjuk).

Tehát itt van az algoritmikus eljárás:

  1. Néhány beállítás: (1) a meglátogatott csúcsok könyvelése: egy halmaz ( visited), (2) emlékezzen az egyes csúcsok ismert legrövidebb távolságaira, amelyek csak felfedezett csúcsokat használnak : egy másik halmazt distance(u). Minden csúcs távolsága kezdetben végtelen, a forráscsúcs kivételével 0.
  2. Most elkezdjük felfedezni: először meglátogatjuk azt a csúcsot, amelynek az eddig ismert legrövidebb útja van, mondjuk az u. (Kezdetben ez lenne a forráscsúcs).
  3. Amikor csúcson uállunk, körülnézünk a kimenő éleken. Minden él, mondjuk (u,v), utat ad a csúcshoz v, amely a csúcsot használja uutolsó, de egyetlen lépésként. Ha bármelyikük valóban rövidebb út v, vagy az első út, amelyre vhurrá, hurrá, akkor a legrövidebb utak halmazát most frissíthetjük. Egyébként hagyja figyelmen kívül és folytassa.
  4. Csúcsokkal végeztünk u, ezért hozzáadjuk a visitedkészletünkhöz.
  5. Térjen vissza a 2. lépésre, folytassa a felfedezést, amíg meg nem látogattuk az összes csúcsot.

distancemost meg tudja mondani a globális legrövidebb távolságokat, mert csak a meglátogatott csomópontok használatával használják a legrövidebb távolságokat. És az összes csúcsot meglátogatja, amikor az algoritmus befejeződik.

Most találtuk fel újra Dijkstra algoritmusát. Természetesen számos más algoritmus létezik a legrövidebb út megtalálásához. De a lényeg az, hogy algoritmikus eljárásra van szükségünk a probléma megoldásához.

2. Ellenőrizze az általános elveket dedukcióval

Hogyan győződhetünk meg arról, hogy az algoritmus alapelvei helyesek? Vagy növelhetjük magabiztosságunkat az alapelv több beviteli példával történő tesztelésével, vagy hatékonyabban szigorú matematikai bizonyítékot találhatunk.

A filozófiában a priori tételhez hasonlóan az algoritmus helyessége független a végrehajtásától. Más szavakkal, a tesztelés nem garantálja az algoritmusok helyességét. Bizonyítanunk kell.

Itt van a bizonyítás alapvető folyamata:

1. Az összes meglátogatott csúcs esetében megtaláljuk a legrövidebb utakat.

2. Meglátogatja az úti célt.

3. Ezért megtaláljuk a legrövidebb utat a célig.

Nem tűnnek kissé ismerősnek? Mint ez:

1. Minden ember halandó.

2. Szókratész férfi.

3. Ezért Szókratész halandó.

Valójában ez a szillogizmus, a deduktív gondolkodás klasszikus formája. Nagyjából ezt csinálják a logikusok.

Egy másik érdekes történelmi tény: a számítás formális fogalmát a logikusok először az 1930-as években vetették fel. Tudniuk kellett, hogy bizonyos logikai problémák egyáltalán megoldhatók-e (így elkerülhetik az idejük pazarlását valami megoldhatatlan megoldás megoldására). Erre válaszul előállnak a kiszámíthatóság fogalmával.

Később, 1936-ban, Alonzo Church és Alan Turing egyszerre dolgozták ki a számíthatóság formális meghatározását. Ez a cikk a számítás történeti áttekintését adja.

A következtetés helyessége az első két feltételtől függ. Bizonyításunk szerint a második előfeltevés triviális, mivel algoritmusunk szó szerint meglátogatja az összes csomópontot. Az első feltételezés bizonyításához, miszerint megtaláljuk a legrövidebb utat, mire meglátogatunk egy csomópontot, némi munka szükséges.

A matematikai indukció segíthet. Valójában ez az egyik leghasznosabb technika sok más algoritmus helyességének bizonyítására.

Az általános áramlás a következő. Először is, ha egy algoritmus a bemeneten működik 0, másodszor, ha az a tény, hogy az inputon működik, nazt jelenti, hogy a bemeneten n+1 is működik, akkor minden nagyobb vagy azzal egyenlő bemenetnél működik 0. Ezen a ponton garantálni tudja az algoritmus helyességét.

Az egyszerűség kedvéért erre az előadási jegyzetre utalok, hogy teljes bizonyítékot nyújtson ennek az útkereső algoritmusnak.

Ne feledje, hogy nem szabad összekeverni a matematikai indukciót és a filozófiai indukciót. Filozófiai meghatározás szerint a matematikai indukció deduktív érvelési folyamat, mivel helyessége magában rejlik, külső megfigyelések nélkül.

A tanulság: amikor kitalálunk egy algoritmust, képesnek kell lennie az összes lehetséges végrehajtási eset kezelésére.

A gyakorlatban a szigorú matematikai bizonyítás átélése nem biztos, hogy a leghatékonyabb stratégia. De legalább a lehető legtöbb kivégzési esetet meg akarjuk vizsgálni, főleg az ellentéteseket. Ez a gyakorlat javítaná kódunk robusztusságát.

Lehet, hogy észrevette, hogy példánkban az útkereső algoritmusban ez nem működik, ha az él súlya negatív. Az okot ebben az előadásban találja meg. Negatív súlyú gráf kezeléséhez használhatja a Bellman-Ford algoritmust.

3. Az ontológiai probléma: adatszerkezet

Eddig meggyőztük magunkat arról, hogy van egy helyes algoritmusunk. De ez csak a csata fele.

A következő kérdés az, hogyan tápláljuk be az információkat a számítógépekbe? Az emberek szeretik a megjelenített információkat, például a grafikonokat vagy a hisztogramokat. De a mai számítógépek csak bináris bitekkel foglalkoznak.

Ki kell dolgoznunk egy olyan adatstruktúrát, amely tartalmazza az alapvető információkat. És hatékonynak kell lennie ahhoz, hogy a program egyszerre dolgozzon fel.

Folytassuk az utat a példakereséssel. Az elérési út rendezett lista. De bosszantó kezelni, egész számhoz képest. Ne feledje, hogy algoritmusunkban meg kell találnunk a legrövidebb utat a felfedezett utak halmazából. És akkor iteráljon egészen a végéig. Úgy tűnik, hogy minden útvonal tárolásához el kell különítenünk egy tömböt vagy memóriát.

Tehetnénk jobban? Ne feledje, hogy egy érvényes útvonalon az elemek egymás utáni megjelenésének meg kell felelnie a grafikon élének. De már megvan az élinformáció, és ezek minden útvonalnál megegyeznek. Miért nem szabadulhatunk meg ettől a felesleges információtól?

Nos, megszabadulhatunk a listától. Kiderült, hogy a legrövidebb út összegyűjtése érdekében a közbenső lépés annak meghatározása, hogy mi a következő ugrás. Az A forrásból bármelyik célcsomópontig a legrövidebb utat csak magának a grafikonnak és az A-tól minden csomóponthoz vezető legrövidebb távolságnak kell megkeresnünk.

A fenti képen vizuális ábrázolás látható. Ez az ábrázolás memória-hatékony. A program feldolgozása is hatékonyabb.

Így konstruálja a legrövidebb utat, csak a távolságvektor felhasználásával. Kezdje a cél csúcsától és egy üres útvonaltól. Keresse meg a köztes csúcsokat a bejövő éleken keresztül. Válassza ki a legalacsonyabb értéket distance. Adja hozzá az útvonal fejéhez. Addig ismételje, amíg el nem érjük a forrást. Ez a trükk tulajdonképpen rendelkezik egy hivatalos jelöléssel, amelyet visszakövetésnek hívnak.

A filozófusok az örök igazságot keresik. A programozók pedig meg akarják találni azt a pontos adatszerkezetet, amely a legjobban rögzíti az információk dinamikáját. Amint az útkereső példában látható, a legrövidebb út megadásához csak egy vektor kell, amely megadja az egyes csúcsoktól a legrövidebb távolságokat. Ez minden grafikonra érvényes, függetlenül a csúcsok vagy élek számától.

4. A posteriori tétel: hibakeresés

A legtöbb programozó rengetegszer átesett ezen az érvelésen. Fogadok, hogy ez a programozási feladatok egyik legnehezebb és időigényesebb része.

Például a C programok szegmentálási hibáit gyakran null mutató hivatkozások okozzák. Ezt megtanultam, miután rengeteg C / C ++ szegmentációs hibát kezeltem. Természetesen vannak finomabb esetek, amelyek a személyes programozási szokásokhoz kapcsolódnak.

Az alábbi példa egy programozó által elkövetett szintaxis hiba. Az if feltételnek kellett volna lennie is_float==1, de a programozó a logikai egyenlő operátort tévesen ==értékelési operátornak tévesztette =. Ez akkor is átengedi a fordító ellenőrzését, mert bármelyik helyes szintaxis.

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

Ez induktív érvelési folyamat. A hibakeresési diagnózisnak csak akkor van értelme, ha elegendő programvégrehajtást figyelt meg.

Itt jön be a gyakorlat értéke. Nem számít, milyen technikákat tanul, elegendő gyakorlati adatot kell gyűjtenie. Ellenkező esetben nem lenne elég tapasztalata az indukció lebonyolításához.

Figyelnie kell a hibakódok ismétlődő mintáit. Ha hibát talál, annak kijavítása nem elég. Szüksége van néhány ok-okozati elemzésre a saját programozási gyakorlatában. Kérdezd meg magadtól: a programozási szokásaimnak ez a része különösen kiszolgáltatott az ilyen típusú hibáknak?

Akkor miért számít?

A programozás nem csupán a kódírásról szól, hanem az érvelés szisztematikus módjáról is. Mert a kód vagy az utasítások csak a cél elérésének eszközei. A programszintézis technika fejlesztésével még a kódírást és a hibakeresést sem zavarhatja. Csak az számít, hogy meg tudja-e mondani a számítógépnek, mit kell tennie.

A programozási képességek fejlesztése felé tett első lépésként ez a cikk feltárja az alapul szolgáló gondolkodási mintát, amelyet programozáskor még fel sem ismerhetünk. Legtöbbünk a tudatalatti, automatikus reflexióra támaszkodik a mindennapi feladataink nagy részének elvégzéséhez. De honnan származik a fejlődés? Először abból származik, hogy észrevettünk néhány tévedést vagy hibát, amelyet az érvelési folyamat során követtünk el.

Gyakorlati tanácsokért ajánlom ezt a cikket arról, hogyan gondolkodhatunk programozóként, és ezt a könyvet ugyanarról a témáról, de további részletekkel.

Hivatkozások

  • Számítás, filozófiai kérdések kb. Matthias Scheutz.
  • Az egyház-türingi tézis.
  • Gondolj úgy, mint egy programozó: Bevezetés a kreatív problémamegoldásba. V. Anton Spraul.