Seuraa 
Viestejä936

Tiedän perusjoukko-opin, mutta minua on ihmetyttänyt, miten joukkoja lasketaan yhteen vaikkapa polynomien kanssa, jos halutaan olla täsmällisiä. Miten asymptoottisessa analyysissä käytetty theta-notaation laskusäännöt "toimivat".

Siis Corman & al. määrittelevät notaation Theta(g(n)):={f(n): on olemassa positiiviset vakiot c1, c2 ja n0 siten, että 0<=c1g(n)<=f(n)<=c2g(n) kaikille n>=n_0} kirjassaan "Introduction to Algorithms". Siis Theta on joukko. Mutta samassa kirjassa annetaan, että 2n^2+3n+1=2n^2+Theta(n). Tässä on selitetty, että oikeastaan pitäisi käyttää joukkoon kuulumisen symbolia, mutta käytännössä tehdään yhtäsuuruuden avulla.

Mutta en ole opiskellut joukko-oppia aksiomaattisesti. Onko oikein merkitä 2n^2+3n+1=2n^2+Theta(n) tai vaikka 1=1+{2}? Ainakin kokonaisluvut voidaan määritellä joukko-opin avulla, https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers . Algebran kurssilla oli myös määritelmä, että jos A ja B ovat joukkoja, niin A+B={a+b|a \in A ja b\in B}. Mutta voidaanko polynomit ja reaaliluvut määritellä samaan tapaan joukko-opin avulla?

Haluaisinkin tietää, että jos pitäisi tehdä notaatiollisesti mahdollisimman täsmällisesti algoritmien aikavaativuusanalyysiä, niin miten kertaluokkanotaatiot ja niillä operaatiot tulisi määritellä? Joukko-opilla vai ilman joukko-oppia?

Tiedän myös keskustelun https://math.stackexchange.com/questions/2536528/how-to-define-and-use-r... . Siinä vastattiin, että idea ei ole, että notaatio olisi eksakti vaan että se olisi järkevä. Haasteena onkin kehittää eksakti tapa tehdä algoritmien asymptoottinen analyysi.

Suosituimmat

Uusimmat

Sisältö jatkuu mainoksen alla

Uusimmat

Suosituimmat