Digresija: i nula je broj

Anegdote su majka mudrosti. Kada sam se davnih dana natjecao na državnom natjecanju iz logike, bio sam okružen gomilom filozofa, jer natjecanja iz logike i filozofije tada (a možda i danas) održavala su se zajedno. Ništa čudno, rekli bi ljudi, srodne discipline. I jedni i drugi razmišljaju, samo što logičari razmišljaju manje i bolje, a filozofi više i gore. (Ovo “gore” može značiti suprotno od dolje, tj. iznad, gore visokoDa ne bi bilo.)

I tako smo mi državni logičari i filozofi išli busom na izlet. Pokraj mene je sjedio neki filozof. Ne znam kako smo došli do toga, ali on je rekao da nula nije broj. Najprije sam mislio da hoće reći da nula nije prirodan broj, na što sam odgovorio da je to stvar definicije, da većina matematičara zaista definira skup prirodnih brojeva bez nule (1, 2, 3, …), ali da se on može definirati i s nulom. Kao što se krug može definirati tako da uključuje ili ne uključuje kružnicu. Stvar dogovora.

Ali ne, nije on mislio na skup prirodnih brojeva, on je tvrdio nešto mnogo jednostavnije i dublje. Nula nije broj, nikakav broj. I džaba sam mu ja objašnjavao da je nula i cijeli broj, i racionalan, i realan broj i svašta još, nije to njega ništa diralo. Njegov argument bio je tipično filozofski, ovako nešto: nula je ništa – doslovno ništa –  a budući da ništa ne može biti nešto, onda ne može biti ni broj. O ničemu je zapravo nemoguće uopće razmišljati. Možemo pojmiti i minus pi kroz tisuću, i imaginarnu jedinicu, sve su to legitimni brojevi, ali ne i nula, on nije pojam, on je ne-pojam. Možemo ga samo ne pojmiti. Tako nešto, jel.

I eto, mogao sam ja koliko hoću objašnjavati čovjeku da je upravo srušio cijelu matematiku, nije se on ništa uzrujavao, imao je taj miran stav blaženog uvjerenja o nečemu što je za njega potpuno očito. Bilo mu je zbilja čudno što se ja toliko nerviram. U povratku sam sjedio u drugom dijelu autobusa.

To me podsjetilo na još neka slična pitanja o nuli. Recimo, kad nam je u V. gimnaziji matematiku predavao legendarni Pjer Mladinić, na početku sata pitao bi: tko je riješio domaću zadaću? I digli bismo ruke. Onda bi pitao: tko nije riješio zadaću? I neki bi digli ruke. E sad, zanimljiva situacija nastala je kad nije bilo domaće zadaće, a on je opet postavio ista pitanja. Tko ima zadaću, tko nema zadaću. I što sad? Biste li digli ruku da imate zadaću? Ili da je nemate? Ili možda oboje?

Prema Pjerovom viđenju, ispravno je dići ruku u oba slučaja. Imate zadaću jer ste riješili svih nula zadataka, ali istodobno je i nemate jer niste riješili nijedan zadatak.

Moderna predikatna logika (logika prvog reda) svakako bi se složila s prvom tvrdnjom: svaki zadatak iz zadaće je riješen (jer nema zadatka koji nije riješen). Kao što je istinita tvrdnja “svi ljudi na Saturnu imaju tri noge” jer na Saturnu nema ljudi pa tvrdnja zaista vrijedi za svih nula ljudi na Saturnu. Negacija bi bila da postoji čovjek na Saturnu koji nema tri noge, a ona je očito lažna, pa je početna tvrdnja istinita.

Ali manje je jasno je li ispravno reći i nemam zadaću. Jer nije posve jasno što uopće znači ta tvrdnja u slučaju kada nije bilo zadaće. Ako ona znači negaciju od imam zadaću, onda je to laž jer smo već utvrdili da je imam zadaću istina. Po Pjerovom shvaćanju, dakle, nemam zadaću znači nešto drugo. Ako to znači “riješio sam nula zadataka”, to bi zaista bila istina, ali onda ne bi “štimao” slučaj kad su riješena npr. dva od deset zadataka, koji također spada u nemam zadaću. Ako pak znači “nisam riješio sve zadatke”, to je isto kao “postoji zadatak koji nisam riješio”, što je laž u slučaju kada nije bilo zadaće pa ipak ne treba dići ruku. Kako god okrenemo, izgleda da je Pjer pogriješio.

No nisam ni spomenuo da je postojalo i treće pitanje: tko ima djelomično zadaću? (Djelomično u značenju barem 70%, ali ne cijelu.) Je li ta tvrdnja istinita kada nije bilo zadaće? Ovo pitanje ostavljamo čitateljima za domaću zadaću. Htio bih se vratiti na prethodni zaključak: ako nešto nemate, možete reći da imate nula. Tako, recimo, ako na natjecanju niste riješili nijedan zadatak, recite da ste riješili nula zadataka. Ako ste zaboravili novčanik, recite da imate nula novaca. Ako nemate automobil, recite da imate nula automobila. Ako želite iznervirati matematičara, uvjeravajte ga da nula nije broj. Onako kako sam ja to proživio u onom busu.

Koja je poanta ovog posta? Nadam se da je jasno. Ovaj post ima određen broj poanti. Broj, naravno da je broj.

Tema dana: glazbeni problemset

Na današnji dan prije točno godinu dana ovdje je objavljen prezabavni mravlji problemset. U skladu sa započetom tradicijom domaćih tematskih problemsetova (objavljen je bio i jedan kraći o nogometu), evo još jedne izložbe iz prebogate riznice dobrih starih hrvatskih zadataka, ovaj put onih čiji se tekstovi bave glazbom.

  1. Zadatak Pjesma (Županijsko 2008.)
  2. Zadatak Melodija (Školsko 2018.)
  3. Zadatak Ljestvica (HONI 2013.)
  4. Zadatak Gitara (HONI 2009.)
  5. Zadatak Ljestve (IBT 2010.)
  6. Zadatak Bard (Županijsko 2007.)
  7. Zadatak Gitara (Županijsko 2017.)
  8. Zadatak Zidarska (DMIH 2004.)
  9. Zadatak Toplista (Županijsko 2006.)
  10. Zadatak Severina (Izborne pripreme 2006.)
  11. Zadatak Zvonimir (Studentsko 2013.)
  12. Zadatak Kolekcija (HIO 2008.)

Nabrijavanje za HONI, drugi dio

Nastavljamo s podsjećanjem na najteža HONI kola svih vremena na svijetu.

Evo jednoga od njih:

http://hsin.hr/honi/arhiva/2012_2013/kolo5_zadaci.pdf

(testni primjeri: http://hsin.hr/honi/arhiva/2012_2013/kolo5_testpodaci.zip)

Od zadnja četiri zadatka (5-8), samo dva su bila riješena na natjecanju, svaki od troje ljudi. Ipak, brutforsima su se mogli dobiti djelomični bodovi. I ovo je dobar trenutak da istaknemo…

Pravilo natjecateljskog programiranja #3: Zbrutaj.

Bez obzira radi li se o simulaciji ili pravom natjecanju. Na natjecanju brutfors redovito čini razliku između medalje većeg i manjeg (ili nikakvog) sjaja, a simulaciju čini boljom i ozbiljnijom. I poslije, naravno, ne zaboravimo upsolving.

(Jezikoslovci još nisu složni oko imperativa, a bome ni infinitiva glagola zbrutati. Neki bi rekli izbrutati, slično kao izbaciti ili ispričati. Nema jezičnog opravdanja za ispuštanje slova i, pa se glasovna promjena izbrutati -> zbrutati u pravopisu opravdava činjenicom da je ionako riječ o žargonu, da čak ni osnovni oblik brutati ne koristi nitko normalan i da će se na hrvatskoj televiziji prije izgovoriti Bolzano-Weierstrassov teorem o konvergenciji nego to, pa onda koga briga. Što se tiče imperativa, neki lingvisti protive se obliku zbrutaj i predlažu “simpatičniji” oblik brutni. No taj oblik dolazi od svršenog glagola brutnuti, a ne od nesvršenog brutati. Kao što nije isto skočiti i skakati. Rasprave još traju i nadam se da će novi pravopis biti jasan po tom pitanju.)

Nabrijavanje za HONI, prvi dio

Jučer sam dobio mail koji je započeo na sljedeći način:

Dragi svi,

“it’s the most wonderful time of the year”, odnosno, kreće nova sezona HONI-ja.

U potpisu su Paljak i Kile pod čijim će palicama nastajati ovosezonska kola.

Očekuju se manje promjene u strukturi i bodovanju zadataka na temelju zapažanja i povratnih informacija nekih natjecatelja. Ideja je da zadnja tri zadatka budu poredana po abecedi (a ne po težini) i da nose jednak broj bodova. Testni primjeri na zadnja četiri zadatka trebali bi biti podijeljeni u podzadatke kao na HIO-u. Težine zadataka trebale bi ostati iste kao dosad. Za svaki full score na nekom kolu, Paljak i Kile otplesat će pet minuta stepa na otvaranju državnog.

Ok, ovo zadnje nije iz provjerenih izvora.

A da nam još mjesec dana ne prođe u neistrpljivom iščekivanju prvoga kola, da ne gledate nervozno u datum na mobitelu i da ne lupate ljutito po zidnom kalendaru jer još nije HONI, imam nešto za vas.

Blogaritam ekskluzivno predstavlja Najteža HONI kola svih vremena na svijetu, a kao prvu simulaciju trebamo riješiti sljedeće kolo:

http://hsin.hr/honi/arhiva/2008_2009/kolo1_zadaci.pdf

(testni primjeri: http://hsin.hr/honi/arhiva/2008_2009/kolo1_testpodaci.zip)

To je kolo bilo toliko teško da zadnja tri (od šest) zadataka nisu bila uopće riješena na natjecanju, osim jednog od tih triju zadatka koji je uspio riješiti samo Goran Žužić, tada jedan od najboljih pet srednjoškolaca na svijetu.

Danas su natjecatelji nešto bolji pa će vjerojatno riješiti više. Rješavajte sve zadatke, pravite se kao da ste na natjecanju. (Bez glazbe i mobitela, od simulacije napravite mali ritual. To vrijedi i općenito: svakodnevne stvari, obroke, šetnje, sitne poslove, treba pretvoriti u rituale. Disciplina, urednost i briga o detaljima smanjuju rastresenost i povećavaju usredotočenost, čime bivamo sretniji.)

Kaj su rješavali naši stari

(Naslov je prilagođen iz imena poznate vrbovačke turističke manifestacije “Kaj su jeli naši stari”.)

Stare Lukine materijale već sam dijelio ovdje i ovdje. Podijelit ću sada i preostala dva dokumenta koja imam:

Luka Kalinovčić: Sweep

Luka Kalinovčić: Dinamičko programiranje

Iz potonjih je zadataka Goran Žužić (naš najuspješniji srednjoškolski natjecatelj dosad) nekad davno naučio dinamiku.

A podijelio bih i članak o FUI koji je Frane Kurtović prije deset godina napisao za časopis PlayMath koji smo tada objavljivali mi, učenici V. gimnazije:

Frane Kurtović: Formula uključivanja i isključivanja

Tip of the day: Stjepanovi snippeti

Kad naučite Python i počnete ga koristiti u stručne ili znanstvene svrhe, više nikada nećete napisati nijedan algoritam: jednostavno ćete iskoristiti neki od desetak tisuća dostupnih modula. Sve je već napisano, čemu duplicirati kod? Malo pretjerujem, naravno, ali nije ovo daleko od istine. Proguglajte malo Python libraries. Naravno, na natjecanju je dostupna samo standardna Python biblioteka, ali natjecanja ćete ionako brzo prerasti.

A do tada, ako se za natjecanja pripremate u C++u, bacite oko na “module” Stjepana Glavine:

https://github.com/stjepang/snippets

Dosta korisno za razne online zadatke, čisto i jednostavno za ubaciti u kod (plug & play). Readme na dnu stranice sve objašnjava. Ako niste upoznati s namespaceovima, primjer korištenja možete vidjeti npr. u rješenju skloniste_flow.cxx u folderu suboptimalnih rješenja s Izbornih priprema (http://hsin.hr/pripreme2019/zadaci/rjesenja.zip).

Naravno, budući da ovo nemate na natjecanjima, ideja je i da vam posluži kao referenca da naučite kako što implementirati. Kad smo već kod toga, prilažem i jedan sličan, stariji dokument, tzv. Zagreb reference (implementacije raznih algoritama) autora Lovre Pužara.

Svako stoblo je stablo, ali nije svako stablo stoblo

[Tema dana: prefiksno stablo iliti STOBLO.]

Prije tjedan dana, na 2. izbornom ispitu pojavio se zadatak sa stablom prefiksa, koje služi da bismo efikasno… Ma skužit ćete iz zadataka.

Ponekad se na crtežu ove strukture slova zapisuju u vrhove stabla. To je pogrešno: slova su bridovi, a ne vrhovi stobla. Vrh nije slovo nego prefiks, tj. niz slova kojima smo došli do tog vrha. Što se tiče implementacije, gledajući rješenja s izbornog ispita, vidio sam da neki koriste pointere, a neki ono što i ja koristim: običnu cjelobrojnu tablicu dimenzija N x 26, gdje je N maksimalan broj vrhova stabla, u kojoj sljedbenik[X][slovo] = Y znači da nakon vrha broj X slijedi slovo kojim dolazimo do vrha broj Y. Ako je ta vrijednost 0 (default), znači da nema tog slova nakon prefiksa X. Dodavanje novog vrha svodi se na operaciju sljedbenik[X][slovo] = broj_vrhova++.

Engleski je trie, a etimologija je zanimljiva (s Wikipedije):

Tries were first described by René de la Briandais in 1959. The term trie was coined by Edward Fredkin, who pronounces it /ˈtr/ (as “tree”), after the middle syllable of retrieval. However, other authors pronounce it /ˈtr/ (as “try”), in an attempt to distinguish it verbally from “tree”.

E sad, u Lijepoj Našoj netko (možda Luka Kalinovčić ili netko prije njega) počeo je ovu strukturu zvati stoblom (logika je jasna: tree –> trie, stablo –> stoblo). Taj pojam i dalje koristimo kolokvijalno. Kraće je reći stoblo nego prefiksno stablo ili stablo prefiksa. Ali nemojte ga baš tako zvati u diplomskom radu, čudno će vas gledati.