Kai skaičiai pradėjo galvoti patys
Jei kada nors bandėte suprasti, kaip jūsų telefono skaičiuoklė akimirksniu išsprendžia lygtį, kurią mokykloje sprendėte penkiolika minučių, tikriausiai susimąstėte – kas gi ten viduje vyksta? Atsakymas nėra toks paprastas, kaip atrodo. Už kiekvieno mygtuko paspaudimo slepiasi dešimtmečiais, o kartais ir šimtmečiais, tobulintas matematinis aparatas, kurį mes šiandien vadiname algoritmu.
Matematinių skaičiuoklių raida – tai ne tik technologijų istorija. Tai pasakojimas apie tai, kaip žmonės bandė perduoti savo mąstymo procesus mašinoms. Ir kiekvienas bandymas atskleidė naujų problemų, naujų sprendimų, naujų klausimų. Šiandien panagrinėsime, kaip algoritminis mąstymas keitėsi nuo paprasčiausių aritmetinių operacijų iki šiuolaikinių simbolinės matematikos sistemų.
Nuo abako iki pirmųjų programuojamų mašinų
Istorija prasideda kur kas anksčiau nei pirmasis kompiuteris. Abakas – tai iš esmės pirmoji skaičiuoklė, kuri reikalavo žmogaus, kaip algoritmo vykdytojo. Žmogus žinojo taisykles: kaip perkelti karoliukus, kaip atstovauti skaičius, kaip atlikti operacijas. Algoritmas egzistavo, bet jis buvo žmogaus galvoje, o ne mašinoje.
Tikras lūžis įvyko XVII amžiuje, kai Gottfriedas Leibnizas ir Blaise’as Pascalis sukūrė mechaninius skaičiavimo įrenginius. Pascalina, sukurta 1642 metais, galėjo sudėti ir atimti – ir tai buvo revoliucija. Bet svarbiausia buvo ne pati mašina, o idėja: aritmetines taisykles galima įkūnyti mechanizme. Algoritmas gali būti fizinis.
Leibnizo žingsniuotasis cilindras jau galėjo dauginti ir dalinti – ir čia prasideda įdomiausia dalis. Daugybos algoritmas, kurį mašina „žinojo”, buvo pagrįstas pasikartojančiu sudėjimu. Tai buvo neefektyvu, bet veikė. Ir šis principas – sudėtingą operaciją suskaidyti į paprastesnes, pasikartojančias – išliko kaip pagrindinis algoritminio mąstymo kertinis akmuo iki pat šių dienų.
Charlesas Babbage’as XIX amžiuje nuėjo dar toliau. Jo Analitinis variklis, nors ir nebuvo baigtas, turėjo turėti tai, ko neturėjo joks ankstesnis įrenginys – sąlyginį šakojimąsi. Tai reiškia, kad mašina galėjo „nuspręsti”, ką daryti toliau, priklausomai nuo tarpinio rezultato. Ada Lovelace, rašydama programas šiam neegzistuojančiam kompiuteriui, iš esmės aprašė tai, ką mes šiandien vadiname algoritminiu mąstymu.
Slankiojo kablelio problema ir kaip ji pakeitė viską
Kai atsirado pirmieji elektroniniai kompiuteriai, matematikams iškilo labai konkretus ir labai nemalonus klausimas: kaip tiksliai atvaizduoti realius skaičius? Sveikas skaičius – paprasta. Bet π? Arba √2? Arba 0.000000001?
Slankiojo kablelio aritmetika, kurią mes šiandien laikome savaime suprantama, buvo tikras inžinerinis iššūkis. IEEE 754 standartas, priimtas 1985 metais, iš esmės išsprendė šią problemą – bet ne visiškai. Slankiojo kablelio skaičiai turi ribotą tikslumą, ir tai sukuria tai, ką programuotojai vadina „apvalinimo klaidomis”.
Praktinis patarimas: jei kada nors pastebėjote, kad jūsų skaičiuoklė rodo 0.9999999999 vietoj 1, tai nėra gedimas. Tai yra slankiojo kablelio aritmetikos pasekmė. Skaičius 0.1 dvejetainėje sistemoje negali būti atvaizduotas tiksliai – panašiai kaip 1/3 negali būti tiksliai atvaizduotas dešimtaine trupmena. Todėl 0.1 + 0.2 kompiuteryje gali duoti ne lygiai 0.3, o kažką labai artimą, bet ne identišką.
Šios problemos sprendimui buvo sukurti specialūs algoritmai – „kompensacinė sumavimo” technika, kurią 1965 metais aprašė Williamas Kahanas. Kahano sumavimo algoritmas seka ir „kompensuoja” mažas klaidas, kurios kaupiasi sudedant daug skaičių. Tai gražus pavyzdys, kaip algoritmas gali „žinoti” apie savo paties apribojimus ir juos kompensuoti.
Trigonometrinių funkcijų skaičiavimas: CORDIC ir jo įtaka
Štai čia prasideda tikrai įdomūs dalykai. Kaip skaičiuoklė apskaičiuoja sin(37°)? Jūs paspaudžiate mygtuką ir akimirksniu gausite atsakymą. Bet kas vyksta tuo metu?
Ilgą laiką atsakymas buvo: Teiloro eilutė. Matematiškai, sin(x) galima išreikšti kaip begalinę eilutę: x – x³/3! + x⁵/5! – x⁷/7! + … Imant pakankamai narių, galima gauti bet kokį norimą tikslumą. Ir tai veikė – bet reikalavo daug daugybos operacijų, kurios ankstyvuosiuose kompiuteriuose buvo brangios.
1959 metais Jackas Volderis pristatė CORDIC algoritmą (COordinate Rotation DIgital Computer), kuris pakeitė žaidimo taisykles. CORDIC idėja geniali savo paprastumu: vietoj daugybos naudojami tik postūmiai ir sudėtys. Mašinai daug lengviau pastumti bitus nei dauginti skaičius.
CORDIC veikia taip: įsivaizduokite, kad turite vektorių ir norite jį pasukti iki tam tikro kampo. Vietoj to, kad skaičiuotumėte tikslų posūkį, jūs atliekate seką mažų, iš anksto nustatytų posūkių – kiekvieną kartą artėdami prie tikslo. Kiekvienas posūkis yra 2 laipsnio galia, todėl jį galima atlikti paprastu bitų postūmiu. Rezultatas – trigonometrinės funkcijos be jokios daugybos.
Šis algoritmas buvo naudojamas HP-35 – pirmajame moksliniame kišeniniame skaičiuotuve, išleistame 1972 metais. Ir jis vis dar naudojamas daugelyje mikrovaldiklių bei FPGA sistemų, kur aparatūrinė daugyba yra brangi arba nepasiekiama. Tai puikus pavyzdys, kaip algoritmas gali kompensuoti aparatūros apribojimus.
Simbolinė matematika: kai skaičiuoklė pradėjo suprasti algebrą
Iki tam tikro momento skaičiuoklės dirbo tik su skaičiais. Jūs įvedėte 2+2 ir gavote 4. Bet ką daryti su x² + 2x + 1? Arba su integralu? Arba su diferencialine lygtimi?
Simbolinės matematikos sistemos – tai visiškai kitokia algoritmų klasė. Jos dirba ne su skaičiais, o su matematiniais objektais: kintamaisiais, funkcijomis, operatoriais. Pirmoji tokia sistema, MACSYMA, buvo sukurta MIT 1968 metais, ir tai buvo tikras šuolis.
Simbolinio diferencijavimo algoritmas yra gana elegantiškas. Jis pagrįstas tuo, kad kiekviena matematinė išraiška gali būti atvaizduota kaip medis: lapai yra skaičiai ir kintamieji, o vidiniai mazgai yra operacijos. Diferencijavimo taisyklės (grandinės taisyklė, sandaugos taisyklė ir t.t.) taikomos rekursyviai šiam medžiui. Rezultatas – naujas medis, atvaizduojantis išvestinę.
Bet simbolinis integravimas yra kur kas sudėtingesnis. Diferencijavimas visada veikia – bet integravimas ne. Daugelio funkcijų integralai negali būti išreikšti elementariosiomis funkcijomis. Risch algoritmas, sukurtas 1969 metais, iš esmės išsprendė šią problemą: jis gali nustatyti, ar integralas apskritai egzistuoja elementariosios funkcijos pavidalu, ir jei taip – jį rasti. Tai vienas sudėtingiausių algoritmų, naudojamų šiuolaikinėse matematikos sistemose.
Šiandien tokios sistemos kaip Mathematica, Maple ar nemokama alternatyva SymPy gali spręsti diferencialines lygtis, atlikti simbolinę integraciją, suprastinti algebrines išraiškas ir dar daug daugiau. Praktinis patarimas studentams: SymPy yra nemokama Python biblioteka, kuri gali atlikti daugelį simbolinės matematikos operacijų. Jei mokotės matematikos ar fizikos, verta išmokti ją naudoti – ne tam, kad pakeistų supratimą, bet tam, kad patikrintumėte savo skaičiavimus.
Skaitiniai metodai: kai tikslumas susitinka su realybe
Simbolinė matematika graži, bet ji ne visada praktiška. Daugelio realių problemų – skysčių dinamikos, konstrukcijų mechanikos, finansų modelių – tiesiog neįmanoma išspręsti simboliškai. Čia į žaidimą įeina skaitiniai metodai.
Niutono-Rapsono metodas lygtims spręsti yra vienas elegantiškiausių algoritmų matematikoje. Idėja paprasta: pradedame nuo pradinio spėjimo, tada iteratyviai tiksliname jį, naudodami funkcijos išvestinę kaip „kompasą”. Kiekviena iteracija paprastai padvigubina tikslių skaitmenų skaičių – tai vadinama kvadratiniu konvergavimu.
Bet Niutono metodas turi silpnybių. Jis gali nekonverguoti, jei pradinis spėjimas per toli nuo sprendinio. Jis gali „įstrigti” lokaliame minimumo taške. Ir jis reikalauja išvestinės – o ne visada ją lengva apskaičiuoti. Todėl buvo sukurta daugybė modifikacijų: Broyden metodas, kuris aproksimuoja išvestinę; Brent metodas, kuris kombinuoja kelis skirtingus metodus, automatiškai pasirinkdamas efektyviausią.
Galutinių elementų metodas (FEM) yra kitas puikus pavyzdys. Jis naudojamas inžinerijoje – skaičiuoti, kaip deformuojasi konstrukcijos, kaip sklinda šiluma, kaip teka skysčiai. Idėja: sudėtingą sritį suskaidyti į mažus, paprastus elementus (trikampius, keturkampius), kiekvienam elementui pritaikyti paprastą aproksimaciją, tada sujungti viską į didelę tiesinių lygčių sistemą ir ją išspręsti. Šiuolaikiniai FEM sprendikliai gali dirbti su milijonais elementų – ir tai reikalauja labai efektyvių tiesinės algebros algoritmų.
Greitoji Furjė transformacija: algoritmas, pakeitęs pasaulį
Jei reikėtų išrinkti vieną algoritmą, kuris labiausiai paveikė šiuolaikinį pasaulį, daugelis matematikų ir informatikų pasirinktų Greitąją Furjė transformaciją (FFT). Tai gali skambėti kaip pervertinimas – bet tikriausiai ne.
Furjė transformacija leidžia bet kokį signalą – garso bangą, radijo signalą, vaizdą – išskaidyti į sinusoidžių sumą. Tai nepaprastai naudinga: galima filtruoti triukšmą, suspausti duomenis, analizuoti dažnius. Bet tiesioginė Furjė transformacijos skaičiavimas N taškų signalui reikalauja N² operacijų. Dideliam N tai yra labai daug.
1965 metais Cooley ir Tukey pristatė FFT algoritmą, kuris tą patį skaičiavimą atlieka per N·log(N) operacijų. Atrodo kaip nedidelis patobulinimas? Pabandykite skaičiais: jei N = 1 000 000, tai N² = 10¹², o N·log(N) ≈ 20 000 000. Tai yra 50 000 kartų greičiau. Tai skirtumas tarp skaičiavimo, kuris užtruktų metus, ir skaičiavimo, kuris užtrunka sekundes.
FFT naudojamas beveik visur: MP3 garso suspaudimas, JPEG vaizdų suspaudimas, mobilaus ryšio signalų apdorojimas, medicininiai MRT skenavimo prietaisai, radarų sistemos. Kai klausotės muzikos telefone, FFT veikia fone. Kai darote rentgeno nuotrauką – FFT. Kai kalbate telefonu – FFT. Šis algoritmas yra vienas iš tų, kurių mes tiesiog nepastebime, nes jis tapo toks fundamentalus.
Įdomu tai, kad vėliau istorikai atrado, jog Gaussas iš esmės aprašė tą patį algoritmą dar 1805 metais – bet jo rankraštis liko nepastebėtas beveik 160 metų.
Mašininis mokymasis ir nauja algoritmų era
Pastarąjį dešimtmetį matematinių skaičiuoklių algoritmų raida įgavo visiškai naują dimensiją. Mašininis mokymasis – ypač giliojo mokymosi neuronų tinklai – sukūrė naujus reikalavimus matematiniam aparatui.
Gradientinio nusileidimo algoritmas, naudojamas neuronų tinklų mokymui, iš esmės yra Niutono metodo giminaitis. Bet vietoj vienos lygties sprendžiama optimizavimo problema su milijardais kintamųjų. Stochastinis gradientinis nusileidimas (SGD) ir jo modifikacijos – Adam, RMSprop, Adagrad – yra šiuolaikiniai algoritmų inžinerijos šedevrai, kurie leidžia efektyviai mokytis iš didžiulių duomenų kiekių.
Automatinis diferencijavimas (autodiff) yra dar viena revoliucinė idėja. Tai ne simbolinis diferencijavimas (per lėtas) ir ne skaitinis (per netikslus). Autodiff naudoja grandinės taisyklę sistematiškai, sekdamas kiekvieną kompiuterinę operaciją ir automatiškai apskaičiuodamas gradientus. Tai yra pagrindas, ant kurio stovi PyTorch, TensorFlow ir kitos šiuolaikinės mašininio mokymosi bibliotekos.
Bet čia atsiranda ir naujų iššūkių. Kai neuronų tinklas „sprendžia” matematinę problemą, jis iš esmės aproksimuoja sprendinį, o ne randa tikslų atsakymą. Tai kelia klausimų apie patikimumą, tikslumą, interpretavimą. Šiuolaikiniai tyrimai bando sujungti tradicinių algoritmų tikslumą su neuronų tinklų lankstumu – tai vadinama „fizikos informuotu mašininiu mokymusi” (Physics-Informed Neural Networks).
Kai algoritmai susitinka su kvantiniais kompiuteriais – kas toliau?
Visa ši istorija – nuo Leibnizo cilindro iki GPT – yra pasakojimas apie tai, kaip mes vis geriau mokome mašinas skaičiuoti. Bet kiekvienas žingsnis atneša ne tik sprendimus, bet ir naujus klausimus.
Kvantiniai kompiuteriai žada dar vieną revoliuciją. Shoro algoritmas, sukurtas 1994 metais, teoriškai gali skaičiuoti didelius skaičius į pirminius dauginamuo eksponentiškai greičiau nei bet kuris klasikinis algoritmas. Tai reiškia, kad daugelis šiuolaikinių kriptografijos sistemų taptų pažeidžiamos. Groverio algoritmas gali paieškos problemas spręsti kvadratiškai greičiau. Bet kvantiniai kompiuteriai vis dar turi daugybę praktinių apribojimų – klaidos, dekohesija, temperatūros reikalavimai.
Praktinis patarimas tiems, kurie nori geriau suprasti šią sritį: pradėkite nuo pagrindų. Khan Academy turi puikų kursą apie skaitinę analizę. „Numerical Recipes” knyga (prieinama internete) yra klasikinis šaltinis apie skaitmeninius metodus. Python su NumPy ir SciPy bibliotekomis leidžia eksperimentuoti su dauguma čia aprašytų algoritmų – ir tai yra geriausia mokymosi priemonė.
Svarbiausia suvokti: kiekvienas algoritmas yra kompromisas. Greitis prieš tikslumą. Paprastumas prieš universalumą. Efektyvumas prieš patikimumą. Nėra universalaus geriausio algoritmo – yra tik algoritmai, geriau ar blogiau tinkantys konkrečiai problemai. Ir suprasti šiuos kompromisus – tai ir yra algoritminio mąstymo esmė, kurią matematikai ir informatikai tobulino šimtmečius ir tebetobulina šiandien.
Nuo Pascalinos iki kvantinių kompiuterių – tai ne tik technologijų istorija. Tai istorija apie tai, kaip žmonija bandė suprasti pati save: kaip mes mąstome, kaip mes sprendžiame problemas, kaip mes galime perduoti šį sugebėjimą toliau. Ir kiekvienas naujas algoritmas yra ne tik techninis sprendimas – tai ir filosofinis teiginys apie tai, kas yra skaičiavimas ir kas yra supratimas.
