Šiame puslapyje pateikiami įvairūs trumpi pranešimai, kurie, galbūt, kada nors bus ir plačiau pateikti.

Greitesnės nei greitos Furjė transformacijos

Furjė transformacijos yra viena svarbiausių koncepcijų informaciniuose moksluose. Tai nereguliarių signalų pateikimo būdas – tokių kaip įtampos svyravimų laide, jungiančiame MP3 grotuvą su garsiakalbiu – kaip grynų dažnių kombinaciją. Jos visuotinai naudojamos apdorojant signalus, tačiau taip pat gali būti panaudotos suspaudžiant vaizdus ir audio duomenis, sprendžiant diferencialines lygtis, tiriant akcijų rinką ir kt.

Dėl to, kad Furjė transformacijos taip paplitusios, kaltas algoritmas, kuris vadinamas greitosiomis Furjė transformacijomis (FFT), sukurtas 20 a. 7-ojo dešimtm., leidęs jas paskaičiuoti akimirksniu. Tačiau buvo žmonių, vis dar bandžiusių surasti dar greitesnius algoritmus.

SODA, grupė MIT tyrinėtojų, pasiūlė naują algoritmą, kuris daugeliu praktiškai svarbių atvejų aplenkia FFT. Kai kuriais atvejais tas pagerėjimas tiesiog dramatiškas – iki dešimties kartų. Jis gali būti ypač naudingas spaudžiant vaizdus.

Kaip ir FFT, naujas algoritmas dirba su skaitmeniniais signalais. Skaitmeninis signalas yra tiesiog skaičių sekos – diskretūs analoginio signalo rinkiniai. FFT ima skaitmeninį signalą ir jį išreiškia kaip svertinę dažnių sumą.

„Svertinė“ reiškia, kad kai kurie dažniai (sumuojant) yra svarbesni nei kiti. Kai kurių jų svoriai tokie mažiai, kad juos galima paprasčiausiai atmesti. Štai kodėl Furjė transformacijos taip tinka duomenų kompresijai. 8x8 taškų bloką galime laikyti kaip 64 skaičių ilgio skaitmeninį signalą, taigi, kaip 64 skirtingų dažnių sumą. Tačiau tyrinėtojai nurodo, kad vidutiniškai 57-is iš šių dažnių galima atmesti tik minimaliai paveikiant vaizdo kokybę. Bee hum signal

Signalai, kuriems Furjė transformacijos įtraukia santykinai mažą didelį svorį turinčių dažnių kiekį, vadinama „išsklaidytais“ (sparse). Naujasis algoritmas paskaičiuoja signalo didžiausių svorių dažnius; kuo labiau išsklaidytas signalas, tuo greičiau veikia algoritmas. Ir jei signalas yra išsklaidytas pakankamai, algoritmas duomenis gali skaidyti atsitiktinėmis porcijomis, o ne visą signalą.

Gamtoje dauguma signalų yra išsklaidyti. Imkim, tarkim, kamerinės muzikos kūrinį. Bendrą signalą sudaro vos keli instrumentai, kurių kiekvienas vienu metu groja tik vieną natą. Iš kitos pusės, visų įmanomų instrumentų, kurių kiekvienas groja visas įmanomas natas vienu metu, įrašas negali būti išsklaidytas – tačiau toks įrašas nieko nedomina.

Naujas algoritmas, kurį sukūrė prof. Adjunktas Dina Katabi ir prof. Piotras Indykas iš MIT CSAIL laboratorijos, kartu su studentais E. Price ir H. Hassanieh, remiasi dviem pagrindinėmis idėjomis. Pirmoji, tai signalo supjaustymas į siaurus „griežinėlius“ taip, kad kiekviename tebūtų tik vienas didelio svorio dažnis. Signalų apdorojime pagrintinė priemonė dažnių atskyrimui yra filtras, atsijojantis vienus dažnius ir praleidžiantis kitus. Jei taip nutinka, kad vienas dažnis su aukštu svoriu atsiduria filtro pakraštyje, tada jsi gali būti nepastebėtas. Tad pirmas uždavinys yra rasti efektyvų būdą taip suderinti filtrus, kad jie galėtų persidengti, ir neliktų praleistų dažnių, tačiau ir griežinėlių traštai būt pakankamai aštrūs.

Kai tik izoliuojamas spektro „griežinėlis“, vis dar reikia nustatyti didžiausio svorio dažnį jame. SODA straipsnyje tai daroma pakartotinai pjaustant griežinėlį į mažesnes riekeles ir paliekamos tik tos, kuriose sukoncentruota didžioji signalo dalis. Tačiau aprašomas ir efektyvesnis metodas, pasiskolinantis signalų apdorojimo techniką iš 4G ryšio tinklų. Dažniai paprastai pateikiami kaip „aukštyn-žemyn“ vingiai, tačiau juos taip pat galima laikyti ir osciliacijomis – ir nustatyti kur jose yra dominuojantis dažnis.

Du Mičigano tyrinėtojai – matematikos prof. Anna Gilbert ir matematikos prof.adjunktas Martin Strausss – jau buvo patobulinę FFT labai išsklaidytiems signalams – „kai pasiskirstymas k (didelio svorio dažnių) yra žymiai mažesnis bei įėjimo apimtis n“. Tačiau MIT algoritmas gerokai išplečia aplinkybes, prie kurių jis gerokai aplenkia FFT.

Fiksuoto taško pažymėjimas

Jau 50 m. matematikai grumiasi su vadinamąja „fiksuoto taško“ teorema. 2008 m. buvo paskelbtas beveik 30 psl. Apimantis ir labai techninis straipsnis, nepaprastai priartėjęs prie jos įrodymo.

Padėkime akmenuką Katedros aikštėje Vilniuje, savo kieme ar ant palangės – ir visada žemėlapyje galėsite nurodyti tikslią vietą, kuriame jis turėtų būti. Akivaizdu, ar ne? Tačiau ne matematikams. Jie nuo 1963 m. negali susitvarkyti su vadinamąja (nors kiek ir sudėtingesne) „fiksuoto taško teorema“, kurią suformulavo Barry Edward Johnson (beje, ją bandęs įrodyti iki pat savo mirties 2002 m.). Tačiau EPFL (Ecole Polytechnique Federale de Lausanne), Lozanoje (Šveicarija) matematikų grupė rado elegantišką, viename puslapyje išdėstomą, sprendimą, atveriantį naujas perspektyvas fizikoje ir ekonomikoje. Jie tai pasiekė, kitaip ėmėsi spręsti uždavinį.

Įdomu, kad teorema pritaikoma įvairiausiems žemėlapiams, nuo planų iki metro schemų bei erdvių pavaizdavimo kvantinėje mechanikoje. Tačiau jos įrodymui yra būtina rasti fiksuotą tašką kiekvienu konkrečiu atveju. Kadangi galimų žemėlapių aibė yra begalinė, matematikai ieškojo universalaus metodo. Tai buvo panašu į svorio centro bet kokiame kūne paieškas. Ir tas taškas buvo surandamas, tačiau ... kitoje erdvėje, nei pradinė. Ir tai leido įrodyti teoremą
(žr. originalų straipsnį >>>>).

Mirė Herbert Hauptman

2011 m. spalio 23 d., sekmadienį, mirė Nobelio premijos laureatas, 94 m. amžiaus Herbert Hauptman‘as (1917-2011). Amerikos žydiškos kilmės matematikas ir kristalografas, Nobelio premiją gavo 1985 m. chemijos srityje už matematinių metodų sukūrimą cheminių jumginių molekulinės struktūros nustatymui.

Gimė Niujorke, 1937 m. baigė Niujorko Miesto koledžą, o 1939 m. gavo matematikos magistro laipsnį Kolumbijos un-te. 1940 m., po audringo romano, vedė Edith Citrynell. Karo metu buvo pasiųstas tarnauti į Ramiojo vandenyno pietus. Tarnybos įspūdžiai taip paveikė jį, kad visą likusį gyvenimą aktyviai protestavo prieš visus JAV karinius veiksmus.

1970 m. ėmė dirbti Buffalo medicinos fonde ir vėliau tapo jo prezidentu.

Griebtasi didžiųjų neišspręstų uždavinių

Žinoma, kad moksliniai tyrinėjimai vyksta lėtai, tačiau tai niekai, palyginus su metais, sugaištamais sprendžiant didžiąsias neišspręstas matematikos problemas.

Vienos tokios problemos ėmėsi Marsdeno fondo (N. Zelandijos) remiamas projektas, kurio pagrindinis tyrinėtojas Dillon Mayhew su 5 bendradarbių komanda iš Viktorijos jau 12 metų praleido bandydami įrodyti Rota teiginį matroidų geometrijos srities (suformuluotą italų matematiko Gian-Carlo Rota 8-ojo dešimtm. pradžioje). Manoma, kad tai gali nepavykti (jei išvis pavyks) padaryti iki 2020-ųjų. Oriented matroid

D. Mayhew tyrinėja matroidų geometriją, kuri yra labiau šiuolaikinė geometrijos forma nei euklidinė geometrija, kurią moko mokykloje. Ne tiek dėmesį kreipdama kampams ir atstumams, matroidų teorija nagrinėja baigtinį taškų skaičių, kurie nesikeičia atliekant projekciją – pvz., trys taškai visada lieka tiesėje, kad ir kokią tiesės projekciją paimtume. Matroidus dengia „tonos įvairių matematinių objektų“, tačiau jie dažnai susiejami tarpusavyje matrica ar skaičių seka. Tačiau tos matricos yra iš gerokai mažiau žinomų sistemų, tokių, kaip Galua laukai arba baigtiniai laukai, turintys baigtinį elementų skaičių, kartais vos 2. Kiekvienai skaičių sistemai gaunama skirtinga matroidų šeima. Matematikai dešimtmečiais bando suklasifikuoti matroidų šeimas kiekvienai skaičių sistemai.

Uždavinį palengvino tai, kad yra apribojimų, kadangi kai kurie matroidai niekada nesusidaro tam tikrose skaičių sistemose. 1958 m. įrodyta, kad 2-ių skaičių sistema turi vieną draudžiamą matroidą, o po 21-erių metų įrodyta, kad 3-ių skaičių sistema turi 4-is draudžiamus matroidus. Pagaliau, 2000-aisiais įrodyta, kad 4- ių skaičių sistema turi 7 draudžiamus matroidus. Ir iš čia kilo Rota teiginys, teigiantis, kad kiekvienai baigtinio skaičiaus sistemai yra baigtinis draudžiamų matroidų skaičius.

Skaičiuojantys gyvūnai  (2011 03 17)

Galimybė skaičiuoti gali būti įgimta daugeliui rūšių.

Nuo Protingojo Hanso laikų mokslininkai skeptiškai žiūrėjo į gyvūnų mokėjimą skaičiuoti. Arklys, plačiai auditorijai demonstravęs aritmetikos ir kitus sugebėjimus, iš tikro vykdė savo trenerio komandas. Šiuolaikiniai egzemplioriai, tokie kaip Afrikos pilkoji papūga Aleksis, mokanti skaičiuoti iki šešių ir žinanti sudėties bei atimties veiksmus, laikomi išskirtiniais atvejais arba aplinkos sąlygų produktais.

Tačiau neseni tyrinėjimai atskleidė įvairių rūšių skaičiavimo sugebėjimus. Tam tikromis sąlygomis, beždžionės gali aplenkti netgi koledžų mokinius. 2008 m. vasarą K.C. Burns iš N. Zelandijos padarė skyles nukritusiuose medžiuose, į kurias, matant N. Zelandijos liepsnelei, įdėjo po skirtingą kiekį kirminų. Liepsnelė ne tik pirma skrisdavo prie skylės, kurioje daugiau kirminų, bet ir, kai K. Burns ją apgaudavo, pašalindamas keletą kirminų jai nematant, praleisdavo dvigubai daugiau laiko ieškodama dingusių kirminų.

2009 m. balandžio mėn. Rosa Rugani iš Italijos paskelbė apie bandymus su ką tik išsiritusias viščiukais. Jie Mama laikė didesnį objektų skaičių. O Jessica Cantlon kelis metus atlikinėji bandymus su beždžionėmis ir nustatė, kad jos gali rinktis mažesnę objektų aibę nepriklausomai nuo objektų dydžio, formos ar spalvos. E. Brannon bandė išmokyti beždžiones garsų kiekį susieti su figūrų skaičiumi, o taip pat patikrino jų sugebėjimus atimti. Bandymai parodė, kad nors beždžionės ir nepajėgė perprasti nulio koncepcijos, jos suvokė, kad jis yra mažiau nei du ar vienas. Nors E. Brannon jaučia, kad gyvūnai neturi lingvistinio skaičių pojūčio – savo galvose jie neskaičiuoja „viens, du, trys,...“ – jie gali grubiai sumuoti objektų aibes, ir tas sugebėjimas jiems įgimtas. Irene Pepperberg, išgarsėjusi 30-ies metų užsiėmimais su papūga Aleksiu, sako, kad net bitės gali skirti nedidelius kiekius.

Pažanga sprendžiant 40 m. senumo dėlionę

John Conway sukurta „Topswops“ dėlionė yra tokia: imame atsitiktinai nuo 1 iki n sunumeruotą kortų kaladę. Nuimkite juo jos kortų kiekį, kurį nurodo viršutinė korta, ir tas kortas perkelkite į apačią. Tada vėl ir vėl kartokite tą patį – tol, kol viršuje atsiras korta su numeriu 1. Reikia surasti minimalų ir maksimalų žingsnių skaičių priklausomai nuo pasirinkto n.

Kadaise D. Knutas eksponentinę viršutinę ribą ir teigė, kad tai gali būti įrodyta apatinei ribai. Tačiau dabar Dr. Hal Sudborough ir Dr. Linda Morales įrodė, kad apatinė riba yra gerokai geresnė, nei spėjo D. Knutas, kuris jų įrodymą pavadino „elegantišku“ ir „žaviu“.

Halas pacitavo ilgametį „Scientific American“ skyrelio vedėją Martin Gardner‘į: „Nelaikykime Conway kortų žaidimų trivialiais. Jie priklauso perstatų aibių teorijai ir ne tik verčia įrodyti giliaprasmes teoremas, bet atsiliepia ir praktiniams uždaviniams, kylančiais, kaip atrodytų, nesusijusiose srityse“.

Įrodymas pateikiamas ”Theoretical Computer Science“ 2010 m. spalio mėn. numerio straipsnyje “A Quadratic Lower Bound for Topswops”.

Martin Gardner knygoje „Time travel and other mathematical bewikderments“ aprašo eilė kortų dėlionių, priskiriamų J.H. Conway.

Tyrinėtojas aiškina Aukso vidurio paslaptį

Laikoma, kad juo naudojosi senovės egiptiečiai statydami piramides, juo paremta senovės Atėnų architektūra. O „Da Vinčio kode“ išgalvotas simbologistas bando atskleisti jo paslaptis. Kaip jo pavyzdys, neretai pateikiama Monos Lizos paveikslas. Tai Aukso vidurys, geometrinė proporcija, kuri laikoma labiausiai estetiška akiai ir yra daugybės misterijų pagrindas. Dar vadinama dieviškąja proporcija, ji apibūdina stačiakampį, kurio viena kraštinė maždaug 1,5 karto ilgesnė už kitą. O dabar jį paaiškinti ėmėsi Duke universiteto inžinierius Adrianas Bejan‘as – atseit, žmogaus akis vaizdą atpažįsta greičiausiai, kai jis yra tokių proporcijų stačiakampis.

Viziją ir atpažinimą sujungia srautų (oro ar skysčių) dinamikos teorija, pagal kurią srautas teka lengviausiu keliu. Bejan‘as 1996 m. sukūrė konstruktalinio dėsnio terminą, kuris 2009 m. pabaigoje pasirodė ir „Intern. J. of Design & Nature and Ecodynamics”. Bejan’as tvirtina, kad tiek žmogui, žvelgiančiam į paveikslą, tiek stirnai lauke, pasaulis yra orientuotas horizontaliai. Stirnai didžiausias pavojus tyko iš šonų ir užnugario, tad jos rega vystėsi, kad žvalgytųsi į šonus. Anot Bejan‘o, matymas ir atpažinimas vystėsi kartu ir yra vieno proceso dalys.

Daugelyje straipsnių ir knygų, parašytų per paskutinį dešimtmetį, A. Bajan‘as įrodineja, kad konstruktalinis dėsnis leidžia nuspėti daugelio srautų, sutinkamų gamtoje (nuo biologijos ir geofizikos iki socialinės dinamikos bei technologijos vystymosi), elgseną.

Matroidai
Kaip supakuoti standžiau?
Matematika ir biologija
Matematikos filosofinės problemos
Riči srautas ir tenzorius
Tjorstono geometrizacijos teiginys
Apie Tarskio skritulio kvadratinimą
P-NP: Ant sveiko proto svarstyklių
Mokslo ribotumas: Dievas, Giodelis ir gravitacija
Semantinės derybos: Dviprasmybių modeliavimas
Netiesinis mąstymas: išspręsti neišsprendžiamą
Algoritmų pirmeivis gavo Kyoto premiją
Da Vinči matematinė klaidelė
Specialioji reliatyvumo teorija
Peteris Karvašas. Archimedas
Puankarė teiginio įrodymas
Diagramos, pakeitusios pasaulį
Pagrindinės statistinės sąvokos
Paviliota senovinio žaidimo
Matematikai: Žanas Furjė
Scenoje - paprastos grupės
Visata kaip kompiuteris
Matematika ir muzika
Harmoninės eilutės
Ar viskas čia taip?
Landau nuslopimas
Dalyba iš nulio
Fieldso medalis