Programavimo filosofija

Loginis mąstymas === gera programinė įranga

Programavimas yra naujas raštingumas. Bet kaip rašyti geras programas? Štai pasikartojantys klausimai, kuriuos turime išspręsti:

  • Kaip mes galime pasiūlyti algoritminius problemos sprendimus?
  • Tada, kaip mes žinome, kad sprendimas iš tikrųjų veikia?
  • Net jei esame tikri, kad jis veikia, kaip mes galime nurodyti kompiuteriui jį vykdyti?

Įdomus faktas - jei jums sunku sugriežtinti kurį nors iš šių klausimų, jūs iš tikrųjų užsiimate filosofija.

Norėdami sužinoti, kodėl, panagrinėkime keletą įdomių programavimo ir filosofinių samprotavimų panašumų.

Pirmasis principas: jūs turite labai galvoti.

Kompiuteriai nedaro nieko protingesnio nei mes - skirtumas yra tas, kad jie tai daro didesniu greičiu.

Tačiau jie negali išspręsti tikros problemos, tokios kaip „kaip man patekti į savo biurą iš namų?“

Efektyvų metodą (iš esmės) gali atlikti žmogus be jokių mašinų, išskyrus popierių ir pieštuką. - Bažnyčios-Turingo tezė

Programavimo nuopelnas vis dar slypi argumentavimo dalyje. Tai yra, realaus pasaulio problemos pavertimas paprastomis instrukcijomis, kurias kompiuteris gali vykdyti.

Žinoma, skirtingos programavimo kalbos turi skirtingus semantinių abstrakcijų lygius. „Python“ programa gali būti trumpesnė už C atitikmenį. Bet tai tik keičia vertimų kiekį. Negalime atsikratyti vertimo darbų. Bet šią diskusiją paliksime vėlesniam laikui.

Programuotojo samprotavimai

Dabar mes žiūrime į tam tikrą problemos aprašymą. Pirmiausia galime ieškoti nedidelio masto įvesties-išvesties pavyzdžių, kad suprastume problemą:

Indukcija. Mums reikia algoritmo, kuris galėtų naudoti tokius pavyzdžius. Dabar jūs darote indukciją: apibendrinkite principus iš patirties.

Atskaita. Kaip sužinoti, ar tai tinka kitiems nežinomiems įvestims? Mes darome dedukciją, kad įrodytume savo algoritmo teisingumą.

Ontologija . Turime išlaikyti duomenis kompiuterio atmintyje. Tikslas yra padaryti juos veiksmingus kompiuteriams apdoroti. Žodžių tvarka, kokia duomenų struktūra gali geriausiai užfiksuoti dinaminį mano informacijos srautą?

Vėl indukcija . Tada ateina pats paskutinis etapas: derinimas. Keldami klaidžią programos dalį mes analizuojame netikėtus rezultatus.

Pavyzdys

Dabar panagrinėkime pirmiau minėtą procesą vadovaudamiesi šiuo realiu pavyzdžiu: suraskite trumpiausią kelią nuo A viršūnės iki E viršūnės.

Esant nedidelio masto problemoms, jas galime išspręsti instinktais. Panašu, kad mums labai paprasta atpažinti sprendimą ACE vien žiūrint.

Bet kaip su sudėtingesnėmis topologijomis? O skirtingi kraštų svoriai?

Mums reikia pagalbos iš kompiuterių. Vis dėlto ne tiesiai į priekį pasakyti kompiuteriui, ką daryti. Yra skirtumas tarp žmonių mąstymo ir kompiuterio veikimo.

Procesas

1. Apibendrinkite principus iš patirties: algoritmai

Norėdami pasakyti kompiuteriui, ką daryti, pirmiausia turime sugalvoti algoritminę procedūrą.

Gobšios strategijos yra natūralus būdas tęsti. Tai yra, pradedant nuo šaltinio viršūnės A ir einant iki galo žinomu trumpiausiu keliu. Toliau tyrinėkite naujas viršūnes, kol pasieksime tikslą E. Ir iš tiesų, šis požiūris patenkina mūsų pavyzdį.

Nuojauta yra ta, kad trumpiausiu keliu į tikslą kiekvienas tarpinis mazgas aplankomas ir trumpiausiu keliu. (Žinoma, ši intuicija daro prielaidą, kad visi kraštai turi teigiamą svorį. Tai gali netikti, priklausomai nuo taikymo. Mes tai išsamiai aptarsime vėliau).

Taigi čia yra algoritminė procedūra:

  1. Kai kurios sąrankos: (1) apskaitytas mūsų aplankytas viršūnes: rinkinys ( visited), (2) prisimena žinomus trumpiausius atstumus iki kiekvienos viršūnės, kurioje naudojamos tik atrastos viršūnės : kitą rinkinį distance(u). Kiekvienos viršūnės atstumas iš pradžių yra begalinis, išskyrus šaltinio viršūnę - 0.
  2. Dabar pradedame tyrinėti: pirmiausia aplankome viršūnę, kurios kelias iki šiol žinomas trumpiausiai, sakykime u. (Iš pradžių tai būtų pirminė viršūnė).
  3. Stovėdami viršūnėje umes apžvelgiame išeinančius kraštus. Kiekvienas kraštas, tarkime (u,v), suteikia mums kelią į viršūnę, vkurioje viršūnė naudojama ukaip paskutinis, bet tik vienas žingsnis. Jei kuris nors iš jų yra trumpesnis kelias varba pirmas kelias, kurį radome v, uragai, mes galime atnaujinti savo trumpiausių kelių rinkinį dabar. Kitu atveju nepaisykite ir tęskite.
  4. Mes atliekame viršūnę u, todėl įtraukiame ją į savo visitedrinkinį.
  5. Grįžkite prie 2 žingsnio ir toliau tyrinėkite, kol aplankysime visas viršūnes.

distancedabar gali mums pasakyti trumpiausius atstumus pasaulyje, nes jis naudojamas norint išlaikyti trumpiausius atstumus naudojant tik aplankytus mazgus. Baigus algoritmą, aplankomos visos viršūnės.

Mes ką tik išradome „Dijkstra“ algoritmą. Žinoma, yra daugybė kitų algoritmų, kaip rasti trumpiausią kelią. Tačiau esmė ta, kad mums reikia algoritminės procedūros, kad išspręstume problemą.

2. Patvirtinkite bendruosius principus dedukcijos būdu

Kaip įsitikinti, kad algoritmo principai yra teisingi? Mes galime arba padidinti savo pasitikėjimą, išbandydami principą pagal daugiau įvesties pavyzdžių, arba, efektyviau, galime rasti griežtą matematinį įrodymą.

Kaip ir a priori filosofijos teiginys, algoritmo teisingumas nepriklauso nuo jo vykdymo. Kitaip tariant, testavimas negali garantuoti algoritmų teisingumo. Turime tai įrodyti.

Štai pagrindinis įrodymų srautas:

1. Visoms aplankytoms viršūnėms randame trumpiausius kelius.

2. Lankomas tikslas.

3. Todėl randame trumpiausią kelią iki tikslo.

Argi jie neatrodo kažkiek pažįstami? Kaip šitas:

1. Visi vyrai yra mirtingi.

2. Sokratas yra vyras.

3. Todėl Sokratas yra mirtingas.

Tiesą sakant, tai silogizmas, klasikinė dedukcinio samprotavimo forma. Tai beveik daro logikai.

Kitas įdomus istorinis faktas: oficialią skaičiavimo sampratą logikai pirmą kartą pateikė 1930-aisiais. Jie turėjo žinoti, ar tam tikros loginės problemos iš tikrųjų yra išsprendžiamos (kad galėtų išvengti laiko švaistymo spręsdamos kažką neišsprendžiamo). Norėdami atsakyti į tai, jie sugalvoja skaičiavimo sąvoką.

Vėliau, 1936 m., Alonzo Churchas ir Alanas Turingas tuo pačiu metu savarankiškai sukūrė oficialų skaičiuojamumo apibrėžimą. Šiame straipsnyje pateikiama istorinė skaičiavimo apžvalga.

Išvados teisingumas priklauso nuo pirmųjų dviejų prielaidų. Mūsų įrodymu, antroji prielaida yra nereikšminga, nes mūsų algoritmas pažodžiui aplanko visus mazgus. Norint įrodyti pirmąją prielaidą, kad mes pasiekiame trumpiausią kelią, kol aplankysime mazgą, reikia šiek tiek padirbėti.

Matematinė indukcija gali padėti. Tai iš tikrųjų yra viena iš naudingiausių metodų, įrodančių daugelio kitų algoritmų teisingumą.

Bendras srautas vyksta taip. Pirma, jei algoritmas veikia su įvestimi 0, ir, antra, jei tai, kad jis veikia su įvestimi, nreiškia, kad jis veikia ir su įėjimu n+1 , tada jis tinka visoms įvestims, kurios yra didesnės arba lygios 0. Šiuo metu jūs galite garantuoti savo algoritmo teisingumą.

Paprastumo sumetimais persiųsiu jums šią paskaitos pastabą, kurioje rasite pilną šio kelio paieškos algoritmo įrodymą.

Atkreipkite dėmesį, kad neturėtume painioti matematinės ir filosofinės indukcijos. Pagal filosofinį apibrėžimą matematinė indukcija yra dedukcinis samprotavimo procesas, nes jo teisingumas yra savaime, be jokių išorinių stebėjimų.

Pamoka yra tokia: kai mes sugalvojame algoritmą, jis turėtų sugebėti tvarkyti visus įmanomus vykdymo atvejus.

Praktiškai griežtas matematinis įrodymas gali būti ne pati efektyviausia strategija. Bet bent jau mes norime apsvarstyti kuo daugiau egzekucijų atvejų, ypač rungimosi. Ši praktika pagerintų mūsų kodo patikimumą.

Galbūt pastebėjote, kad mūsų kelio paieškos algoritme pavyzdys neveikia, jei krašto svoris yra neigiamas. Priežastį galite rasti šiame paskaitos užraše. Norėdami tvarkyti neigiamo svorio grafiką, galite naudoti „Bellman-Ford“ algoritmą.

3. Ontologijos problema: duomenų struktūra

Iki šiol įsitikinome, kad turime teisingą algoritmą. Bet tai tik pusė mūšio.

Kitas klausimas yra, kaip mes tiekiame informaciją į kompiuterius? Žmonėms patinka vizualizuota informacija, pvz., Grafikai ar histogramos. Tačiau šiandieniniai kompiuteriai sprendžia tik dvejetainius bitus.

Turime sugalvoti duomenų struktūrą, kurioje būtų pagrindinė informacija. Tai turėtų būti efektyvu, kad programa būtų apdorojama tuo pačiu metu.

Tęskime savo kelią ieškodami pavyzdžio. Kelias yra sutvarkytas sąrašas. Tačiau erzina spręsti, palyginti su sveikuoju skaičiumi. Atkreipkite dėmesį, kad savo algoritme turime rasti trumpiausią kelią iš savo atrastų kelių rinkinio. Ir tada kartokite iki galo. Atrodo, kad kiekvienam keliui išsaugoti turime skirti masyvą ar atmintį.

Ar galėtume padaryti geriau? Atminkite, kad tinkamame kelyje eilės elementų pasirodymai turi atitikti grafiko kraštą. Bet mes jau turime informacijos apie kraštus ir jie yra vienodi visuose keliuose. Kodėl negalime atsikratyti šios nereikalingos informacijos?

Na, mes galime atsikratyti sąrašo. Pasirodo, norint surinkti trumpiausią kelią, tarpinis žingsnis yra nustatyti, koks yra kitas apynis, kurį reikia eiti. Viskas, ko mums reikia, norint gauti trumpiausią kelią iš šaltinio A į bet kurį tikslinį mazgą, yra tik pats grafikas ir trumpiausias atstumas nuo A iki kiekvieno mazgo.

Vaizdinis vaizdas pateikiamas aukščiau esančiame paveikslėlyje. Šis atvaizdavimas yra efektyvus atmintyje. Tai taip pat efektyviau apdorojant programą.

Taip jis sukonstruoja trumpiausią kelią naudodamas tik atstumo vektorių. Pradėkite nuo paskirties viršūnės ir tuščio kelio. Ieškokite tarpinių viršūnių per gaunamus kraštus. Pasirinkite tą, kurio vertė mažiausia distance. Pridėkite jį prie kelio galvos. Kartokite, kol pasieksime šaltinį. Šis triukas iš tikrųjų turi oficialų žymėjimą, vadinamą atgaliniu stebėjimu.

Filosofai siekia amžinos tiesos. Ir programuotojai nori sužinoti tikslią duomenų struktūrą, kuri geriausiai atspindi informacijos dinamiką. Kaip matote kelio paieškos pavyzdyje, viskas, ko reikia norint pateikti trumpiausią kelią, yra tik vektorius, nurodantis trumpiausius atstumus iki kiekvienos viršūnės. Tai galioja bet kuriam grafikui, neatsižvelgiant į viršūnių ar briaunų skaičių.

4. A posteriori teiginys: derinimas

Daugelis programuotojų šį argumentavimą išgyveno daugybę kartų. Lažinuosi, kad tai yra viena iš sunkiausių ir daug laiko reikalaujančių bet kurios programavimo užduoties dalių.

Pavyzdžiui, segmentavimo gedimus C programose dažnai sukelia nulinės žymeklio nuorodos. Tai sužinojau išsprendęs daugybę C / C ++ segmentavimo gedimų. Žinoma, yra subtilesnių atvejų, susijusių su asmeniniais programavimo įpročiais.

Šis pavyzdys yra sintaksės klaida, kurią padarė programuotojas. Sąlyga „if“ turėjo būti is_float==1, tačiau programuotojas klaidingai ==vertino loginį lygių operatorių kaip vertinimo operatorių =. Tai vis tiek išlaikys kompiliatoriaus patikrą, nes bet kuri iš jų yra teisinga sintaksė.

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

Tai yra indukcinis samprotavimo procesas. Jūsų derinimo diagnozė yra prasminga tik tuo atveju, jei pastebėjote pakankamai programos vykdymų.

Čia atsiranda praktikos vertė. Nesvarbu, kokių metodų mokotės, turite surinkti pakankamai praktinių duomenų. Priešingu atveju neturėtumėte pakankamai patirties indukcijai atlikti.

Turėtumėte stebėti pasikartojančius klaidų kodų modelius. Kai randate klaidą, jos ištaisyti nepakanka. Jums reikia papildomos priežasties-pasekmės analizės pagal jūsų pačių programavimo praktiką. Paklauskite savęs: ar ši mano programavimo įpročių dalis yra ypač pažeidžiama šioms klaidoms?

Tai kodėl tai svarbu?

Programavimas yra ne tik kodo rašymas, bet ir sistemingas samprotavimo būdas. Nes kodas arba instrukcijos yra tik priemonė tikslui pasiekti. Tobulindami programų sintezės techniką, galite net nesivarginti rašydami kodą ir patys derindami. Svarbu tik tai, ar galite pasakyti kompiuteriui, ką daryti.

Kaip pirmas žingsnis tobulinant programavimo įgūdžius, šis straipsnis atskleidžia pagrindinį samprotavimo modelį, kurio galbūt net neatpažįstame, kai programavome. Daugelis iš mūsų pasikliauja nesąmoningais, automatiniais apmąstymais, kad atliktų daugumą savo kasdienių užduočių. Bet iš kur tobulėjimas? Pirmiausia tai pastebima klaidose ar klaidose, kurias padarėme savo samprotavimų procese.

Norėdami gauti praktinių patarimų, aš rekomenduoju šį straipsnį apie tai, kaip mąstyti kaip programuotojas, ir šią knygą ta pačia tema, bet su daugiau informacijos.

Nuorodos

  • Skaičiavimas, filosofiniai klausimai apie. Matthiasas Scheutzas.
  • Bažnyčios-Turingo tezė.
  • Galvok kaip programuotojas: kūrybinių problemų sprendimo įvadas. V. Antonas Spraul.