Ar kada nors bandėte ištraukti poligoninį tinklelį iš 3D diskretiško skalarinio lauko?

Ar ne?

Na, dar 1987 metais du „General Electric“ programuotojai tai padarė – ir jie galiausiai išrado „Marching Cubes“ algoritmą, todėl gydytojai gali paversti medicininius nuskaitymus 3D modeliais, kurie tiesiog išgelbėjo milijonus gyvybių.

Tai yra algoritmo galia.

Whenever you instruct a machine to solve a problem with code, you’re designing a procedure to transform bits into meaningKai kurie algoritmai yra greiti.Kai kurie yra elegantiški.Ir kai kurie yra tokie keistai, jie jaučiasi kaip burtai.

Šioje istorijoje mes nardome į dešimt keisčiausių, ryškiausių kada nors sukurtų algoritmų - tuos, kurie padeda ieškoti milijardų kodų eilučių per milisekundes, kurti begalinius žemėlapius iš nieko ir paversti kvantinį keistumą praktine logika.

1 – bangos funkcijos žlugimas

Vienas iš keisčiausių dalykų moksle yra dvigubo pjūvio eksperimentas: dalelės elgiasi kaip bangos, kai jūs nežiūrite, bet tą akimirką, kai juos stebite, jie įsijungia į vietą kaip dalelės.

Ši „bangų funkcijos žlugimo“ idėja skamba abstrakčiai, tačiau ji buvo paversta stebėtinai praktišku algoritmu. Įsivaizduokite, kad projektuojate vaizdo žaidimo žemėlapį su šoniniu pasukimu. Norite, kad pasaulis jaustųsi rankų darbo, bet taip pat tęstųsi amžinai.

Pradžioje kiekviena žemėlapio plytelė yra tarsi „banga“ – dar nėra nieko konkretaus. Ji yra pilna galimybių. Bet kaip žaidėjas juda į priekį – stebėdamas pasaulį – algoritmas „sugriauna“ tą neapibrėžtumą. Pasaulis sukietėja į konkrečią plytelę, bet tai daro pagal jūsų nustatytas taisykles. Kelias jungia, upės teka ten, kur jos turėtų, ir viskas jaučiasi taip, tarsi ji buvo sąmoningai suprojektuota.

Tai atsitiktinumas su tikslu, visa tai be vieno generuojamo AI gabalo.

#2 Sklaidos modelis

Tai keista, tai tikrai keista.

Paimkite difuzijos modelius – technologijas, kurias naudoja vaizdo generatoriai, tokie kaip DALL·E ir Stable Diffusion.Jie pagrįsti termodinamikos idėja: difuzijos, kur dalelės natūraliai plinta iš aukštesnės koncentracijos vietovių į mažesnės koncentracijos vietoves.

Mašininio mokymosi metu šis procesas yra apverstas.

Užuot pereinant nuo tvarkos prie chaoso, algoritmas pradeda nuo gryno triukšmo – kaip katės paveikslėlio – ir išmoksta palaipsniui tobulinti jį į prasmingą vaizdą.

Bet jums reikia modelio, kad tai padarytumėte gerai. Difuzijos algoritmas veikia dviem etapais.

Pirma, mokymo metu modelis imasi realių vaizdų ir palaipsniui prideda triukšmą į priekį, kol jie tampa neatpažįstami.

Padarykite tai per milijonus pažymėtų vaizdų, ir jūs gaunate modelį, kuris gali svajoti apie naujus vaizdus nuo nulio. Katės erdvėje. Senovės Roma Pixar stiliaus. Hiperrealistinės avokadų kėdės. Jūs jį pavadinote.

Tai sunku apskaičiuoti. bet tai nesibaigia vaizdais. Sklaida jau pertvarko, kaip mes generuojame muziką, garsą ir toliau - vaizdo įrašą.

#3 Simuliuojamas aneurizmas

Viena iš labiausiai varginančių programavimo dalių yra ta, kad retai yra vienas teisingas sprendimas - tik daugybė gerų ir keletas puikių.Kaip "Amazon" sandėlio organizavimas: dešimtys būdų tai padaryti, bet tik keletas, kurie iš tikrųjų yra prasmingi mastu.

Simuliuojamas anėjimas pasiskolino savo pavadinimą iš metalurgijos, kur metalai kartojami ir aušinami pakartotinai, kad pašalintų defektus.Ta pati koncepcija taikoma optimizavimui.Jūs bandote rasti geriausią sprendimą chaotiškame kraštovaizdyje, kuriame yra vietos viršūnės ir slėniai.

Įsivaizduokite, kad ieškote aukščiausio kalnų kalno viršūnės. Pagrindinis kalnų kilimo algoritmas privers jus įstrigti pirmajame smūgyje, kuris atrodo perspektyvus. Tačiau imituojamas prakaitavimas yra protingesnis. Jis prasideda nuo aukštos „temperatūros“, o tai reiškia, kad jis laisvai tyrinėja - kartais netgi priima blogesnius kelius, kad išvengtų vietinių spąstų.

Kompromisas yra žvalgyba prieš išnaudojimą. Ir tai ne tik naudinga kodui – tai gera metafora mokytis koduoti, taip pat. Anksti, jūs atsipalaiduojate tarp kalbų, įrankių ir sistemų.

#4 Miegojimas

Jūs negalite kalbėti apie algoritmus, nepateikdami rūšiavimo - ir galbūt absurdiškiausias (ir visiškai nenaudingas) kada nors sukurtas yraMiegojimas juoda.

Tradiciniai algoritmai, tokie kaipKviksasarbaMaršrutas, naudokite padalinimo ir užkariavimo strategijas, kad pakartotinai suskaidytumėte diapazonus į pogrupius ir efektyviai juos rūšiuotumėte. bet kažkur 4chan, pamišęs genijus pasiūlė visiškai kitokį požiūrį.

Štai kaip tai veikia: kiekvienam skaičiui skaičiuje pradėkite naują siūlą. Kiekvienas siūlas miega keletą milisekundžių, lygių jo vertei, tada atspausdina skaičių, kai jis atsibunda.

Tai praleidžia visą įprastą logiką ir paverčia procesoriaus siūlo tvarkaraštį rūšiavimo varikliu. Jokių palyginimų. Jokių recursijų. Tiesiog miegoti ir spausdinti.

Bet tai yra be galo nepraktiška. Jis sulaužo su neigiamais skaičiais, dublikatais ar didelėmis vertėmis. Jis taip pat yra neveiksmingas, sukuriant vieną siūlą už skaičių. Ir tai priklauso nuo miego laiko, kuris nėra labai tikslus. „Sleep Sort“ yra juokingas ir nenaudingas - puikus pavyzdys, kaip protingas ne visada reiškia naudingas.

# 5 Dievas yra švarus

BogoSort yra juokingas algoritmas: jis atsitiktinai keičia skaičių vėl ir vėl, kol grynai pasisekė, rezultatas yra rūšiuojamas.

Dabar įsivaizduokite, kad tai derinama su kvantinės mechanikos ir multivisato idėja.Teoriškai, jei visi galimi rezultatai egzistuoja begalėse lygiagrečiose visatose, tada yraKai kurieVisata, kurioje jūsų matrica jau rūšiuojama.

Technologijos dar nėra, bet „Quantum BogoSort“ veiktų, sukurdamas visas šias galimybes vienu metu, o tada akimirksniu žlugdamas į visatą, kuriame yra rūšiuojama matrica – iš esmės leisdamas kvantiniam atsitiktinumui atlikti darbą už jus.

Žinoma, tai yra mokslinė fantastika, o ne kompiuterių mokslas.Mes negalime stebėti ar sugriūti multivisato, bet tai yra žaismingas mąstymo eksperimentas apie brute-force atsitiktinumą, paimtas į savo loginį (ir absurdišką) kraštutinumą.

# 6 - Būklė

Ir štai mano mėgstamiausias. tai, ką aš manau, kad algoritmai yra tikrai cool, kaip jie kartais gali atspindėti gamtą. Paimkite Craig Reynolds "Boids" programą iš 1986 m. - tai buvo viena iš pirmųjų dirbtinio gyvenimo modeliavimo ir ji imituoja, kaip paukščiai kaupiasi.JaučiasiTaip gyvas

Kiekvienas paukštis (arba „buonas“) laikosi tik trijų taisyklių: išvengti susidūrimo su kaimynais (Separacija), suderinti su jų kryptimi (Suderinimas) ir judėti link vietinės grupės centro (Suderinimas).

Niekas nėra atsakingas, bet kai imituojate daugybę šių paprastų elgesio būdų, jūs gaunate žavius, organinius modelius, kurie keičiasi ir teka kaip tikra kaimenė.

Grožis čia nėra kodas - tai yra tai, kąIškylaŠios sudėtingos grupės dinamikos nereikia aiškiai programuoti, jos tiesiog atsitinka.

# 7 – SHOR algoritmas

Idėja leisti žmonėms užrakinti savo pašto dėžutes ir pasirašyti savo laiškus unikaliu parašu yra pagrįsta svarbiu kriptografijos konceptu: sunku faktoriuoti didelius skaičius.

Daugumos šifravimo metodų saugumas priklauso nuo šios paprastos matematinės realybės - dauginti didelius skaičius kartu yra lengva, tačiau išsiaiškinti du pirminiai skaičiai už produkto—Problema, žinoma kaipprime factorization —Tai labai sunku ir užima daug laiko.

Tiesą sakant, tai yra taip sunku, kad jūsų nešiojamajam kompiuteriui gali prireikti šimtų trilijonų metų, kad išspręstų šią problemą, nebent, žinoma, mes pradėsime naudoti kvantinius kompiuterius.

Shoro algoritmas gali suskaidyti didelius skaičius į pagrindinius veiksnius daug greičiau nei įprasti metodai.

Šoro algoritmo širdyje yra kvantinės mechanikos sąvokos, tokios kaip qubits, superpozicija ir supainiojimas.Tai leidžia kvantiniams kompiuteriams atlikti didžiulius skaičiavimus lygiagrečiai, ką klasikiniai kompiuteriai net negali priartėti.

Nors pats algoritmas yra teisėtas, jo realaus pasaulio taikymas vis dar yra ankstyvose stadijose. iš tikrųjų didžiausias skaičius, kada nors skaičiuojamas naudojant kvantinius skaičiavimus, yra tik 21.

Pastaruoju metu Kinijos komandai pavyko skaičiuoti didžiulį skaičių naudojant kvantinį kompiuterį, tačiau jie naudojo algoritmą, kuris nėra gerai skalės daug didesniems skaičiams, o tai reiškia, kad jis dar nėra praktiškas bendram naudojimui.

Tačiau, jei kvantiniai kompiuteriai taps pakankamai galingi ir kas nors išsiaiškins, kaip šiuos algoritmus išplėsti iki tikrai didelių skaičių, tikėtis rimtų sutrikimų kibernetinio saugumo pasaulyje.

# 8 - Maršavimo kubai

Šios istorijos pradžioje mes paminėjome Maršavimo kubų algoritmą, tačiau tai verta pasinerti, nes tai buvo pagrindinis 3D duomenų vizualizavimo posūkis, ypač medicinoje.

Įsivaizduokite, kad turite 3D žmogaus kūno nuskaitymą, pavyzdžiui, iš MRT. MRT suteikia jums ne 3D modelį, bet milžinišką skaičių kubą - 3D skalarinį lauką. Kiekvienas taškas toje srityje turi vertę, kuri atstovauja kažką panašaus į audinių tankį ar signalų intensyvumą. Šie duomenys yra nuolatiniai erdvėje, bet mums reikia paversti jį kažkuo vizualiu - paviršiumi, forma, kažkuo, kurį kompiuteris gali piešti.

Algoritmas paima šį 3D lauką ir eina per jį vieną mažą kubą vienu metu.

Dabar čia yra protingas šiek tiek: kiekvienas iš tų aštuonių taškų yra virš arba žemiau slenksčio (tarkim, kur oda virsta kaulu).Taigi kiekvienam kampui priskiriamas 0 arba 1, priklausomai nuo to, ar jis yra paviršiuje, kurį bandote išgauti.

Tai suteikia jums 8 bitų skaičių - 256 galimų kombinacijų kiekvienam mažam kubui. Kiekvienam iš šių kombinacijų konkretus trikampio modelis buvo iš anksto apskaičiuotas ir saugomas paieškos lentelėje. Šie trikampiai naudojami apytiksliai paviršiui, einančiam per tą kubą.

Pakartodamas šį procesą – žygiuojant per kubą po kubo, įjungiant reikšmes, ieškant formų – algoritmas palaipsniui sukuria visą 3D tinklelį.

Tai buvo novatoriškas 1980-aisiais, nes jis pavertė plokščius MRT ar CT skenavimo gabaliukus į realius 3D modelius, kuriuos gydytojai galėjo sukti, priartinti ir analizuoti.

# 9 - Praktinė Bizantijos klaidų tolerancija

Šiuolaikinėje kompiuterijoje mes dažnai dirbame su paskirstytomis sistemomis – kompiuterių tinklais, išplitusiais per debesį.

Įsivaizduokite tai: keli generolai iš Bizantijos armijos supa miestą. Jie turi koordinuoti ir atakuoti tuo pačiu metu, kad laimėtų. Bet jie gali bendrauti tik siunčiant pranešimus, o kai kurie iš tų generolų gali būti išdavikai, bandantys sabotuoti planą. Galbūt vienas nusprendžia miegoti, arba blogiau - meluoja apie tai, kada atakuoti.

Kompiuteriai susiduria su tuo pačiu iššūkiu. paskirstytose sistemose kai kurios mašinos gali žlugti, būti lėtos ar net įsilaužti.

Būtent čia įeina konsensuso algoritmai, tokie kaip PBFT – praktinė Bizantijos klaidų tolerancija. PBFT yra sukurtas siekiant susidoroti su tokiais gedimais. Jis veikia, kai vienas mazgas siūlo veiksmą, transliuodamas „paruoštą“ pranešimą. Kiti mazgai reaguoja su pripažinimu. Kai tam tikras mazgų skaičius (paprastai du trečdaliai ar daugiau) sutinka, jie pasiekia sutarimą. Galiausiai, originalus mazgas siunčia „įsipareigojimo“ pranešimą, sakydamas visiems atlikti veiksmą. Net jei iki trečdalio mazgų yra klaidingi ar kenksmingi, sistema vis dar gali tinkamai veikti.

Algoritmai, tokie kaip PBFT, yra blokų grandinės sistemų ir paskirstytų debesų duomenų bazių pagrindas, padedantis jiems išlikti nuoseklūs ir patikimi – net ir tada, kai viskas klysta.

Žymė: Boyer Moore

Ir galiausiai, tai atneša mus į senosios mokyklos algoritmą, kuris tyliai įgalina kai kuriuos iš greičiausių įrankių, kuriuos šiandien naudojame, pavyzdžiui, grep. Jis vadinamas Boyer-Moore eilutės paieška, ir neseniai jis sukrėtė mano mintis dėl to, kaip jis yra kontraintuityvus: kuo ilgesnis tekstas, tuo ilgesnis tekstas.GreitesnisJis gauna

Dauguma pagrindinių paieškos algoritmų eina iš kairės į dešinę, tikrindami kiekvieną simbolį po vieną.right to leftpaieškos modelio viduje, ir jis naudoja du protingus triukus, kad praleistų didelius teksto gabaliukus.“needle„Tai didžiulis teksto blokas.

1. Bad character rule:

Jei ieškote "needle" ir dabartinis teksto simbolis yra "z" - tada nėra jokios galimybės, kad rungtynės galėtų prasidėti tuo metu ar anksčiau.

2. Good suffix rule:

Jei ieškote „needle“ ir jūs tik sutapote „dle“ pabaigoje – bet kitas simbolis sulaužo rungtynes – algoritmas nepradeda nuo kito raidės. Vietoj to, jis klausia: ar „dle“ pasirodo anksčiau „needle“? Jei taip, jis pakeičia modelį taip, kad ankstesnės „dle“ linijos. Jei ne, jis visiškai praleidžia visą „dle“ dalį.

Šios heuristinės praleidimo strategijos nėra tobulos, bet jos yraKeliasEfektyvesnis nei brute force metodas.

Kaip tekstas tampa ilgesnis, algoritmas linkęs praleisti vis daugiau ir daugiau simbolių, todėl jis yra greitesnis, palyginti su įvesties dydžiu.Todėl tokie įrankiai kaip grep gali kramtyti gigabaitus žurnalų stebėtinai greitai - ir kodėl šis dešimtmečius senas algoritmas vis dar jaučiasi kaip juodoji magija šiandien.

Kai logika susitinka su vaizduote: tikroji algoritmų galia

Nesvarbu, ar kvantinis neapibrėžtumas paverčiamas praktiniu vaizdo generavimu, imituojant biologinį grupavimo elgesį trimis paprastomis taisyklėmis, ar ieškant teksto atgal, kad būtų galima greičiau rasti modelius, šie metodai rodo, kad netradicinės idėjos dažnai sukuria galingiausius sprendimus.

Tai, kas daro šiuos algoritmus puikiais, yra ne jų efektyvumas ar naujovė – tai jų drąsa. Jie iššūkis prielaidoms. Jie sukasi problemas ant savo galvų. Jie paverčia atsitiktinumą į struktūrą, chaosą į tvarką ir abstrakčią teoriją į realaus pasaulio poveikį.

Daugiau nei elegantiški matematiniai įrankiai – šie 10 keistų algoritmųare a testament to human ingenuity.

Norite dažniau išgirsti iš manęs?

Susisiekite su manimi LinkedIn!

DalinamėsKasdienėveiksmingas įžvalgas, patarimus ir atnaujinimus, kurie padės jums išvengti brangių klaidų ir likti priekyje AI pasaulyje.

Ar esate technologijų specialistas, norintis padidinti savo auditoriją rašydamas?

Don’t miss my newsletter!

ManoTech Audience Acceleratoryra supakuota su veiksmingais copywriting ir auditorijos kūrimo strategijomis, kurios padėjo šimtams specialistų išsiskirti ir pagreitinti jų augimą.