XVII amžius yra laikomas šiuolaikinio mokslo pradžia. Na, buvo ir XVI amžiuje šio to - pavyzdžiui, Koperniko atradimai; ir anksčiau buvo to, ką mes dabar suprantame kaip mokslą, užuomazgų ar pavienių elementų taikymo.
Tačiau mokslas mokslu tapo tik tada, kai tyrimai tapo sistematiški ir nuoseklūs, pradėjo remtis aiškiai nustatytais principais, kaip turi būti atliekami eksperimentai ir analizuojami duomenys, kad gaunami rezultatai būtų kuo objektyvesni. Šitie principai - tai mokslinis metodas, kurio, kaip ir mokslo, užuomazgų randama nuo žilos senovės laikų, bet kuris šiuolaikine forma visuotinai priimtas maždaug XVII amžiuje.
Yra daug filosofinių diskusijų ir bandymų paaiškinti, kur slypi mokslinio metodo esmė ir kodėl jis yra pranašesnis už kitus aplinkos pažinimo būdus. Per daug į jas nesigilinant, metodas susideda iš keturių elementų: stebėjimo, hipotezės, bandymo ir analizės.
Stebėjimas reiškia vykstančių reiškinių… stebėjimą (netikėta, ar ne?), stebėjimo duomenų kaupimą ir sisteminimą, sistemingumų ieškojimą. Hipotezė - paaiškinimo stebimiems reiškiniams sugalvojimas. Bandymas - eksperimentas, skirtas hipotezei ir jos duodamoms prognozėms patikrinti.
Dar mokslinį metodą galima pavaizduoti šitaip.
Galbūt pastebėjote, kad metodo elementų apibūdinimai yra gana netikslūs ir neišsamūs. Tokius juos parašiau būtent todėl, kad egzistuoja įvairios variacijos ir interpretacijos. Kai kurios yra specifinės tam tikroms mokslo šakoms, kitos - tiesiog skirtingų filosofinių krypčių požiūriai, ir taip toliau.
Šiandien trumpai pakalbėsiu apie vieną tokių interpretacijų grupę, susijusią su hipotezėmis ir, sakyčiau, su pačia mokslinio metodo esme. Jei bandytume išsiaiškinti, kur yra mokslinio metodo esmė, svarbiausia dalis, be kurios jis nebebūtų jis daug labiau, nei praradęs kažkurią kitą dalį, tai turbūt daugelis apsistotų kažkur ties hipotezių tikrinimu.
Nes būtent tai - hipotezės ir jai patikrinti skirto eksperimento junginys - skiria mokslinį metodą nuo kitokių pažinimo būdų: grynai empirinio, kur vadovaujamasi vien natūraliais potyriais; arba grynai racionalistinio, kur viską bandoma išmąstyti vien protaujant; ir dar visokių kitokių.
Tam, kad galėtume hipotezę patikrinti, ji turi būti paneigiama. Šioje vietoje pasireiškia lietuvių kalbos trūkumas - mes neturime gramatinės formos, kuria nedviprasmiškai būtų įmanoma išversti terminą „falsifiable“. „Paneigiama“ yra taisyklingas vertimas, bet dviprasmis.
„Falsifiable“ reiškia, kad hipotezė yra tokia, kurią įmanoma paneigti, o ne tai, kad ji jau yra paneigta. Kodėl tai svarbu? Paneigiamumas (falsifiability) reikalingas, kad galėtume įsitikinti, ar hipotezė yra kiek nors naudinga.
Naudinga hipotezė sako, kad kažką matome, nes yra taip, o ne kitaip. Eksperimentas leidžia patikrinti, ar tikrai yra taip; jei paaiškėja, kad yra kitaip, hipotezę galima atmesti. Bet net ir šiame siaurame mokslinio metodo aspekte - hipotezių paneigiamume - slypi įvairios galimos interpretacijos.
Pirmasis iš jų yra dviejų astrofizikų, Džo Silko (Joe Silk) ir Džordžo Eliso (George Ellis) komentaras, prieš savaitę publikuotas žurnale „Nature“. Komentare jie daugiausiai kalba apie stygų teoriją ir porą multivisatos idėjų, bet pagrindiniai teiginiai yra bendresni: hipotezės (ir iš jų susidedančios teorijos) yra mokslinės tik tada, kai jas įmanoma paneigti.
Jeigu teorijos duodamų prognozių niekaip neįmanoma patikrinti - taigi ir paneigti - ji neturi prasmės. Netrukus kitame puikiame mokslinių naujienų puslapyje Science 2.0 fizikas teoretikas Johanesas Kiolmanas (Johannes Koelman) parašė atsakymą į šį komentarą.
Jame jis teigia, kad stygų teorija kaip tik yra labai mokslinė, ne dėl to, kad jos teiginius galima paneigti, bet dėl to, kad jie „visą laiką yra paneiginėjami“. Turima omenyje tai, kad tokios teorijos, kaip stygų, aiškina tokią daugybę reiškinių (stygų teorija turėtų apjungti kvantinę fiziką ir reliatyvumo teoriją), kad vien tai, jog ji gali paaiškinti tai, ką paaiškina ir kitos, dalinės teorijos, jau yra stygų teorijos moksliškumo ir gerumo įrodymas.
Mano supratimu, nors šis komentaras parašytas kaip atsakymas į Silko ir Eliso tekstą, iš tikro jie kalba apie skirtingus dalykus ir abiejuose tekstuose yra nemažai tiesos. Silkas ir Elisas daugiau rašo apie mokslinio metodo esmę, o Kiolmanas - apie mokslinių tyrimų naudą, kuri nebūtinai išmatuojama vien atitikimu moksliniam metodui.
Na, o pabaigai - dar vienas požiūris į tai, kokia hipotezė yra mokslinė, o kokia ne. Fizikas-teoretikas, kvantinės fizikos specialistas ir kvantinės kompiuterijos vienas iš pradininkų, Deividas Doičas (David Deutsch), TED pranešime kalba apie tai, ką reiškia „paaiškinimas“ kaip mokslinis terminas.
Ypač įdomi ta dalis, kurioje jis pateikia pavyzdžių apie mokslinius ir nemokslinius paaiškinimus, pasiremdamas graikų mitais. Mitiniai paaiškinimai nėra moksliniai todėl, kad juos labai lengva pakeisti ir taip pritaikyti prie naujų stebėjimų duomenų.
Mokslinės teorijos lengvai nepakeisi - ji duoda aiškias prognozes, ir jei jos nepasitvirtina, tuo blogiau teorijai.
Gali būti, kad kur nors truputį nusišnekėjau, nes mokslo filosofija nėra mano stiprioji sritis.
Olimpiadose naudojami programavimu pagrįsti algoritmai yra efektyvūs, naudojantys dinaminio programavimo principus. Uždavinio sprendimo schema apima optimalaus sprendinio, turinčio tam tikrą (optimalią) vertę, paiešką.
Svarbu skirti sąvokas sprendinys ir sprendinio vertė. Sprendinys yra pats eksponatų rinkinys (pvz., eksponatų rinkinį, kurį galėtų panešti vagis). Dažniausiai yra efektyvūs algoritmai, duodantys lokalųjį optimumą, nebūtinai gaunamas globalusis optimumas.
Pateiksime kontrpavyzdį eksponatų, kurių bendra vertė yra 160. Tačiau visų trijų paimti negalima, nes visi trys jie netilptų į kuprinę. Taigi, reikia perrinkti visus įmanomus sprendinius ir iš jų išrinkti optimalų.
Šis metodas netaikomas, nes yra labai neefektyvus, t. y. programavimu pagrįsti algoritmai yra efektyvūs. Rekursyvios funkcijos skyrelyje nagrinėjamas ne optimizavimo uždavinys, o lėtas algoritmas. Fig. kas daugiau negu reikia.
Reikšmės perskaičiuojamos daug kartų. Pavyzdžiui, net 5 kartus tenka skaičiuoti . Toliau pateiktas šios funkcijos rekursijos medis. Fig. suskaičiuojamas per laiko intervalą. Algoritmas pradedamas vykdyti iš viršaus į viršų, t. y. gaunant didesnes reikšmes.
Dabar aptarkime dinaminio programavimo algoritmą. Tarkime, turime eksponatų, kurių svoriai ir vertės yra , išreikšti sveikaisiais skaičiais. Užduotis - rasti eksponatų struktūros nustatymo būdą, kad bendras svoris neviršytų , o bendra eksponatų vertė būtų maksimali.
Panagrinėkime konkretų pavyzdį, kai turime tris eksponatus ir maksimalus svoris yra 5 kilogramai. Nagrinėjamo svorio reikšmės lentelėje pažymėtos pilku fonu. Jei svoris[k] <= r, tai D[k, r] = D[k - 1, r], t. y. rinkinį įtraukti negalime.
Kadangi lentelėje daug skaičių, jos teksto nepateikiame. Dinaminio programavimo algoritmas, įsimindamas tarpinius sprendinius, apskaičiuoja šią reikšmę. Pavyzdžio atveju maksimali vertė lygi 33. Tokią vertę galima rasti lentelės pagalba. Sąlyga D[n, S] > D[n - 1, S] rodo, kad įtraukti reikia.
Sudėtingumas atminties atžvilgiu yra nedidelis. Apskaičiuokime ilgiausią didėjantį posekį. Tarkime, turime seką (6, 3), tai ilgiausias didėjantis posekis turi keturis narius. Pradėsime nuo optimalaus sprendinio struktūros nustatymo. Kaip rasti ilgiausią didėjantį posekį?
Tegu tai būtų . Kad posekis būtų didėjantis, turi būti mažesnis už . Tai yra dinaminio programavimo metodo žingsnis. Algoritmas pradedamas vykdyti iš viršaus į viršų, t. y. gaunant didesnes reikšmes langeliuose, galima rasti patį posekį. Pavyzdžiui, pirmas narys lygus , antras - , trečias - .
Dovanų vertes pažymėkime . Tarkime, dovanų vertė lygi . Atkreipkime dėmesį, kad . Jei radome skaičių, galime iš karto apskaičiuoti ir antrą, kurios atiteks Emilijai. Reikia rasti dovanų rinkinį, kad jų suma būtų lygi . Taigi, reikia sudėti dėmenų, norint gauti skaičių A. Jei -asis narys būtinas, tai dėmenų, t. y. -asis narys būtinas.
Dabar galime grįžti prie Teisingų dalybų uždavinio (visų verčių sumos pusei). Reikia nustatyti, kurias dovanas reikia skirti Rusnei, o kurias - Emilijai. Pradėsime analizuoti uždavinį nuo kelių paprastų pavyzdžių. Tarkime, turime devynias knygas. Ar devynias knygas visuomet padalytume optimaliai? Tarkime, darbuotojams darbas paskirstomas lygiomis dalimis, t. y. t. y. kol kas nagrinėtuose pavyzdžiuose galime daryti išvadų.
Tarkime, jas reikia paskirstyti trims darbuotojams. Tarkime, turime keturias knygas. Dabar aptarsime algoritmą šiam uždaviniui spręsti. Taigi, pradėkime nuo optimalios sprendinio struktūros nustatymo, t. y. Taigi, pradėkime nuo optimalios sprendinio struktūros nustatymo. Tarkime, lentynos pabaigos, t. y. -osios, knyga atiteks ne nors kitam, o -osios (t.y. paskutiniam darbuotojui) darbuotojų įvertį . Reikia rasti mažiausias .
Dabar reikia sudaryti ją efektyviai apskaičiuojantį algoritmą, t. y. optimalus lentynos paskirstymas yra sprendinys, t. y. optimalus lentynos paskirstymas. Algoritmo tekstą nepateiksime. Reikia rasti gautojo (optimalaus) paskirstymo įvertį, t. y. lentynoje esančių knygų paskirstymą nuo pradžios iki galo.
Aptarkime procedūros paskirstyk sudėtingumą. Kiek langelių reikia apskaičiuoti? Kiek skaičių iš tam tikro intervalo reikia perrinkti, kad gautume reikšmę? Šio algoritmo sudėtingumas taip pat tiesiškai priklauso nuo , t. y. S reikšmes. Šio algoritmo sudėtingumas būtų . Tačiau tiek prireiktų laiko ir tiek pat atminties.
Reikia rasti sumas visiems , t. y. Algoritmo tekstą nepateiksime. Tarkime, turime medžių. Medžių ašys yra lygiagrečios sodo tvoroms. Užduotis - rasti plotą, kuriame nebūtų medžių.
Įveskime keletą sąvokų. Stačiakampio kraštinės vidiniuose taškuose nėra medžių. Stačiakampio aukštį žymėsime . Fig. ir reikšmes. Reikia rasti didžiausius stačiakampius (t. y. reikšmes.
Pradėsime nuo masyvo D. Naudojama dėklo duomenų struktūra. Koordinatės peržiūrimos iš kairės į dešinę (t. y. 1 iki ) ir paeiliui dedamos į dėklą. koordinatė , nes jau apskaičiuota. Kur - paskutinis dėkle esantis elementas, ir paskutinis dėklo elementas. Jei sąlyga netenkinama, reikia nagrinėti kitą koordinatę.
Šis metodas priskiriamas dinaminį programavimą. Ar tai optimizavimo uždavinys (pvz., trumpiausias ar panašiai)? Ar uždavinyje aprašyto objekto elementai yra surikiuoti? Objektų elementai yra surikiuoti iš kairės į dešinę (t. y. kitokia tvarka. Daugiakampio viršūnės, lapai paieškos medyje ir pan.
Dinaminio programavimo taikymas priklauso nuo uždavinio specifikos. Sakykime, uždavinyje aprašytas objektas turi elementų. Ar galime, turėdami sprendimus tik su mažesniais parametrais, rasti uždavinių sprendimui? Ar galime, turėdami sprendimą objektui su elementų, įtraukę elementą galime gauti sprendinį objektui iš elementų?
Jei ne - dinaminio programavimo taikyti neverta. Tačiau dažnai reikia atsižvelgti į atminties sąnaudas. Ar sprendimui pakaks atminties? Jei sprendimui reikia daug atminties, reikia ieškoti efektyvesnį atminties atžvilgiu algoritmą. Sudėtingumas atminties atžvilgiu yra . Jei tokio algoritmo nepavyktų rasti, dinaminio programavimo taikyti nepavyktų. Analogiškas uždavinys pateiktas S.