[ MajorFatal @ 25.12.2005. 10:33 ] @
Kompresija random-like podataka bi se vrsila na sledeci nacin: ako imamo fajl (koji hocemo da kompresujemo) duzine n bita I ako napravimo brojac takodje duzine n, koji broji od 0 do 2^n -1 nas fajl bi se nasao na tom brojacu na poziciji m (obzirom da su iste duzine fajl I brojac). Zapis (n,m) bi bio nas kompresovani fajl.
Dekompresija bi se vrsila na sledeci nacin: iz kompresovanog fajla bi procitali n I napravili brojac duzine n. Zatim bi procitali m, pustili brojac u rad I zaustavili kod m-tog fajla po redu. Stanje na brojacu u tom trenutku bi bio nas originalni fajl.
Da bi postojala kompresija m bi moralo biti izrazeno (I zapisano) kao a^b +x tj. a^b + c^d – e^f + .. +x^y + z tj. zbirom koeficijenata I drugih brojeva osim 2, na najoptimalniji (najkraci) nacin. Tacna vrednost tog izraza bi se izracunavala tek prilikom dekompresije.
Prilikom kompresije ne bi bilo neophodno (a ni pozeljno) pravljenje brojaca. M se da izracunati na osnovu “tezinskih” koeficijenata direktno iz originalnog fajla. Na primer za fajl 0101 m je : 0*2^3 + 1*2^2 + 0*2^1 + 1*2^0 = 5.
[ Ivan Dimkovic @ 25.12.2005. 10:37 ] @
To nece ici, ako je signal slucajne prirode, zbir koeficijenata kojim hoces da ga opises ce zauzimati mnogo vise mesta od samog signala ;)

Probaj sa iole kompleksnijim signalom na papiru - pa ces videti da ne ide.


[Ovu poruku je menjao Ivan Dimkovic dana 25.12.2005. u 11:39 GMT+1]
[ MajorFatal @ 25.12.2005. 10:42 ] @
Ja sam kontao da bilo koji moze da se predstavi sa desetak - petnaest sabiraka.
[ Ivan Dimkovic @ 25.12.2005. 10:51 ] @
Citat:

Kompresija random-like podataka bi se vrsila na sledeci nacin: ako imamo fajl (koji hocemo da kompresujemo) duzine n bita I ako napravimo brojac takodje duzine n, koji broji od 0 do 2^n -1 nas fajl bi se nasao na tom brojacu na poziciji m (obzirom da su iste duzine fajl I brojac). Zapis (n,m) bi bio nas kompresovani fajl.


Pa zapis (n, m) je svakako vise podataka od predstavljanja samog broja? Tvoja "pozicija u brojacu" je zapravo sam broj.

Broj: 154, bin: 10011010
n = 8
m = 154 - tacno 154 puta moras da "brojis" do tog broja ;)

Objasni mi, sta si ti tu skratio?
[ MajorFatal @ 25.12.2005. 13:05 ] @
Na zalost za ovako malo n=8 ne moze da se "vidi" da kompresija moze da postoji za vece vrednosti n. Na primer zapis (m =) 2^6 zauzima 24 bita u memoriji tj. vise od 6 bita, ali zato zapis 2^32 zauzima ISTO prostora tj. 32 bita ( po 8 bita svaki znak i broj), dok vec zapis 2^64 zauzima manje prostora (opet 32 bita) u odnosu na 64.
Konkretno ono sto hocu da kazem je da bi m u ovom slucaju 154 trebalo zapisati kao npr: 2^7 + 5^2 + 1 s tim sto u ovom slucaju ne bi bilo kompresije jer bi ovaj zapis zauzimao 72 bita sto je vise od 8 bita ali za vece fajlove ovakav nacin zapisivanja bi dosao do izrazaja kao veoma racionalan tj. doneo bi nam kompresiju.
[ Ivan Dimkovic @ 25.12.2005. 13:09 ] @
Taj zapis ti ne bi doneo kompresiju u generalnom slucaju (gde tvoj model ne zna koja ce informacija biti sledeca) jer za slucajnu sekvencu brojeva P tvoji koeficijenti bi zauzimali vise mesta nego sama sekvenca P.

Za individualne male slucajeve gde si pronasao mogucnost kompresije si sam zapravo napravio model licnim pogadjanjem koeficijenata - te koeficijente moras negde da uskladistis, sto zauzima prostor. Za generalni slucaj to ne moze da funkcionise sa dobitkom u prostoru, jer tvoj dekoder nema model koji bi dedukovao te koeficijente, vec oni moraju biti preneti, tj. pohranjeni u kompresovani signal.

Ako malo bolje razmislis, tvoja "kompresija slucajnih brojeva" je isto sto i "beskonacna kompresija" za koju si sam uvideo da je nemoguca - jer je sekvenca kompresovana nekim od poznatih algoritama za kompresiju zapravo vrlo bliska slucajnom nizu brojeva.

Dakle, ti bi svojom "kompresijom slucajnih brojeva" zapravo kompresovao nesto sto je vec svedeno na stanje blisko entropiji. Sto je protivno matematickoj teoriji informacija Kloda Sanona.


[Ovu poruku je menjao Ivan Dimkovic dana 25.12.2005. u 14:14 GMT+1]
[ MajorFatal @ 25.12.2005. 21:59 ] @
Citat:
Ivan Dimkovic: Taj zapis ti ne bi doneo kompresiju u generalnom slucaju (gde tvoj model ne zna koja ce informacija biti sledeca) jer za slucajnu sekvencu brojeva P tvoji koeficijenti bi zauzimali vise mesta nego sama sekvenca P.

Ne razumem ono da moj model ne zna koja ce informacija biti sledeca. Da li si napravio lapsus kada si napisao za slucajnu sekvencu brojeva P hoteci da kazes za slucajnu sekvencu bita P koeficijenti bi zauzimali vise mesta nego sama sekvenca? Mislim da sam u prethodnom postu pokazao kako je onaj nacin zapisivanja koeficijenata sve racionalniji za sve vece brojeve. Ako ipak tu treba da stoji “za slucajnu sekvencu brojeva P” onda ne znam na koju sekvencu brojeva mislis. Kod mene se originalni fajl ceo posmatra kao neka vrsta broja (malo veceg doduse) I jedan je, nema sekvence takvih brojeva.

Citat:
Ivan Dimkovic

Za individualne male slucajeve gde si pronasao mogucnost kompresije si sam zapravo napravio model licnim pogadjanjem koeficijenata - te koeficijente moras negde da uskladistis, sto zauzima prostor.

Naravno ali ovo vazi za svaku vrstu kompresije ako se ne varam neki prostor mora biti iskoriscen.
Citat:
Ivan Dimkovic

Za generalni slucaj to ne moze da funkcionise sa dobitkom u prostoru, jer tvoj dekoder nema model koji bi dedukovao te koeficijente, vec oni moraju biti preneti, tj. pohranjeni u kompresovani signal.

Prilikom dekompresije iz koeficijenata bi se racunala “puna vrednost” datog broja tj. redosled pojavljivanja originalnog fajla na brojacu.
Citat:
Ivan Dimkovic

Ako malo bolje razmislis, tvoja "kompresija slucajnih brojeva" je isto sto i "beskonacna kompresija" za koju si sam uvideo da je nemoguca - jer je sekvenca kompresovana nekim od poznatih algoritama za kompresiju zapravo vrlo bliska slucajnom nizu brojeva.
Naravno da je isto, sto sam I naglasio u “beskonacnoj kompresiji” I pozvao ljude da ucestvuju u okviru ove teme jer sam tamo napravio isuvise gresaka ali nisam uvideo da je nemoguca sto dokazuju I ovi napori
[ formeye @ 26.12.2005. 08:57 ] @
Bilo kakva kompresija podataka je moguca ako i samo ako postoji visak informacija.
Ako su podaci slucajni (po definiciji slucajnosti), tada ne postoji visak podataka i, samim tim, kompresija je nemoguca.
[ Ivan Dimkovic @ 26.12.2005. 11:23 ] @
Citat:

Ne razumem ono da moj model ne zna koja ce informacija biti sledeca. Da li si napravio lapsus kada si napisao za slucajnu sekvencu brojeva P hoteci da kazes za slucajnu sekvencu bita P koeficijenti bi zauzimali vise mesta nego sama sekvenca? Mislim da sam u prethodnom postu pokazao kako je onaj nacin zapisivanja koeficijenata sve racionalniji za sve vece brojeve. Ako ipak tu treba da stoji “za slucajnu sekvencu brojeva P” onda ne znam na koju sekvencu brojeva mislis. Kod mene se originalni fajl ceo posmatra kao neka vrsta broja (malo veceg doduse) I jedan je, nema sekvence takvih brojeva.


Nisi pokazao, pokazao si samo jedan podesen primer.

Probaj sa nekoliko slucajnih nizova - i probaj na papiru da uskladistis, i videces da ne ide, da je informacija koja je potrebna da se "opise" pseudo-slucajni niz uvek veca od samog niza.
[ MajorFatal @ 26.12.2005. 20:44 ] @
Citat:
formeye: Bilo kakva kompresija podataka je moguca ako i samo ako postoji visak informacija.
Ako su podaci slucajni (po definiciji slucajnosti), tada ne postoji visak podataka i, samim tim, kompresija je nemoguca.

Ako slucalne podatke lociram na brojacu tada mi ceo fajl postaje visak informacija I odlucujem se da pamtim samo njegov redosled pojavljivanja na brojacu sto je mnogo krace. Ovo mi je pak dovoljno da kasnije regenerisem tj. dekompresujem fajl.
Citat:
Ivan Dimkovic: Nisi pokazao, pokazao si samo jedan podesen primer.

Probaj sa nekoliko slucajnih nizova - i probaj na papiru da uskladistis, i videces da ne ide, da je informacija koja je potrebna da se "opise" pseudo-slucajni niz uvek veca od samog niza.

Probao bih ja ali kako da probam sa primerima gde je niz bita (fajl) duzi od 32 bita sto mi je neophodno da bi kompresija radila to na papiru vec ide malo teze pa sam ja mislio da nadjem nekog crnca na elitesecurity-u da uradi programcic za mene uz pomoc koga bi se veoma lako i brzo utvrdilo da li kompresija postoji ili ne.
[ netoff @ 27.12.2005. 14:36 ] @
Ja ne znam da li MajorFatal zajebava sve ovde na forumu:))
[ MajorFatal @ 29.12.2005. 20:11 ] @
Pa izgleda da najvise zajebavam sam sebe sto ocekujem da bilo sta bude od ovoga. U svakom slucaju hvala svima na aktivnom ucescu u raspravi. Ja odustajem.
[ netoff @ 29.12.2005. 23:28 ] @
Iako ti sada to možda ne izgleda tako, najbolje bi ipak bilo da odustaneš.
[ MajorFatal @ 30.12.2005. 13:04 ] @
Srecna svima nova 2006-ta godina i bozicni praznici uz najlepsi pozdrav HRISTOS SE RODI!
[ jablan @ 30.12.2005. 13:18 ] @
Citat:
MajorFatal: Srecna svima nova 2006-ta godina i bozicni praznici uz najlepsi pozdrav HRISTOS SE RODI!

...što se lako može kompresovati u:
Code:

AGwAeQAgAFIAZQBwAG8AcgB0ACAAUABlAHIAcwBvAG4AYQBsACAAQwBhAHIAZAAHAAcATgBhAG0A
ZQA6ACAATQBsAGEAZABlAG4AIABKAGEAYgBsAGEAbgBvAHYAaQAHAQcARABhAHQAZQA6ACAAVAB1
AGUAcwBkAGEAeQAsACAATgBvAHYAZQBtAGIAZQByACAAMQAxACwAIAAyADAAMAAzAAcAVwBlAGUA
awA6ACAABwAHAAcABwAgACAABwBEAGUAcwBjAHIAaQBwAHQAaQBvAG4ABwBTAHQAYQB0AHUAcwAH
AEMAbwBtAG0AZQBuAHQAcwAHAEEAdAB0AGEAYwBoAC4AIABOAGEAbQBlAAcABwBFAG4AZAAgAG8A
ZgAgAEQAYQB5ACAAcwB0AGEAdAB1AHMAIAByAGUAcABvAHIAdAAgACAAKABwAHIAZQB2AGkAbwB1
AHMAIABkAGEAeQApAAcABwAxAC4ABwBjAGwAZQBhAG4AaQBuAGcAIABjAG8AZABlAAcAQwBvAG0A
cABsAGUAdABlAGQABwAHAAcABwAyAC4ABwBmAGkAeABpAG4AZwAgAGIAdQBnAHMAIAAmACAAdABl
AHMAdABpAG4AZwAHAEMAbwBtAHAAbABlAHQAZQBkAAcABwAHAAcAMwAuAAcAYwBvAHAAAAYAADYI
AAA4CAAAQggAAEQIAABkCAAAZggAAGgIAAB0CAAAqAgAAKoIAAC0CAAAtggAALgIAAC6CAAAvAgA
AL4IAADp2MSwn4p0xGVTxLBT2EEwAAAAAAAAAAAAAAAAIBVouD0rABZoPAboAENKEgBPSgMAUUoD
AF5KAwBhShIAACMVaFYzNQAWaDwG6AA1CIFDShIAT0oDAFFKAwBeSgMAYUoSACMVaFYzNQAWaLEn
gQA1CIFDShIAT0oDAFFKAwBeSgMAYUoSAB0WaDZTmgA1CIFDShIAT0oDAFFKAwBeSgMAYUoSACsV
aDZTmgAWaLEngQA1CIFDShIAT0oDAFFKAwBeSgMAYUoSAG1IGghzSBoIKBZoNlOaADUIgTYIgUNK
EgBPSgMAUUoDAF5KAwBhShIAbUgaCHNIGggAIBZoNlOaADUIgTYIgUNKEgBPSgMAUUoDAF5KAwBh
ShIAACYVaFYzNQAWaDUhMAA1CIE2CIFDShIAT0oDAFFKAwBeSgMAYUoSAAAmFWhWMzUAFmixJ4EA
NQiBNgiBQ0oSAE9KAwBRSgMAXkoDAGFKEgAAIBVouD0rABZosSeBAENKEgBPSgMAUUoDAF5KAwBh
ShIAACwVaIBUkAAWaLEngQA1CIFCKghDShQAT0oDAFFKAwBeSgMAYUoUAHBo////ABAABgAANggA

[ BraMom @ 30.12.2005. 18:42 ] @
Srećni praznici svima i posebno Jablanu.

Svake godine se pojavi bar jedan post o nekoj "super" kompresiji. Više ne znam da li to negativno ili mozda pozitivno, to mu dođe kao početak interesovanja za teoriju informacija...
[ formeye @ 31.12.2005. 09:21 ] @
Srećno sve svima vama.

Citat:
BraMom: Svake godine se pojavi bar jedan post o nekoj "super" kompresiji. Više ne znam da li to negativno ili mozda pozitivno, to mu dođe kao početak interesovanja za teoriju informacija...

Nadaj se, nadaj... :)))
[ MajorFatal @ 31.12.2005. 09:38 ] @
Cisto da imate sta da citate 31-vog u noc posto vecina vas onanista nece ici nigde za novu godinu ;)
Da si Jablane isprogramirao program i utvrdio da dolazi do ekspanzije a ne do kompresije ja bih ti se zahvalio do neba, priznao da sam majmun i odustao od daljeg insistiranja na kompresiji. Ovako ostaje mi samo da se kiselo nasmejem na salu koja je smesna koliko i ova moja o onanistima (znaci nimalo).
Citat:
BraMom

Svake godine se pojavi bar jedan post o nekoj "super" kompresiji.

Sto samo svedoci da jedna takva nova kompresija mora da postoji i samo ceka da bude otkrivena.
U novoj godini sam odlucio da primenim radikalno drugaciji nacin pristupa problemu. Dakle 31-vog tacno u ponoc otvara se KONKURS! Prvi ko isporuci bilo kakav program uradjen po uputstvima iz prvog posta u okviru ove teme ima od mene MALO PIVO ispred prodavnice ili dragstora PO SOPSTVENOM IZBORU! Sta sad kazete momci? Malo pivo mozda ceka samo Vas.
Jos jednom srecna nova godina svima.
[ Ivan Dimkovic @ 31.12.2005. 10:08 ] @
E a ako nekom uspe da kompresuje proizvoljnu random sekvencu - od mene dobija 10 gajbi piva kojeg zeli ;-)))))
[ blaza @ 31.12.2005. 12:27 ] @
Loseless kompresija proizvoljne random sekvence ne predstavlja narocit problem.
Vise na: http://www.geocities.com/patchnpuki/other/compression.htm


[Ovu poruku je menjao blaza dana 31.12.2005. u 20:14 GMT+1]
[ MajorFatal @ 02.01.2006. 11:00 ] @
Svaka cast Patricku ali ja bih i dalje voleo da vidim svoj algoritam na delu. Valjda ce se neko smilovati.
[ MajorFatal @ 02.01.2006. 11:01 ] @
.

[Ovu poruku je menjao MajorFatal dana 02.01.2006. u 12:06 GMT+1]
[ jablan @ 02.01.2006. 18:58 ] @
Srećnu novu svima želim... Malo kasnim sa čestitkom, onanisao sam za doček...
Citat:
BraMom: Više ne znam da li to negativno ili mozda pozitivno, to mu dođe kao početak interesovanja za teoriju informacija...

Naravno da je pozitivno, entuzijazam je najbolji stimulans za napredak, setimo se sopstvenih početaka, doduše mi smo lestvicu postavljali nešto niže od "kompresije slučajnih podataka". Iz neke dalje perspektive, i pobede i porazi su podjednako vredni za razvitak mladog uma - porazi, ruku na srce, nešto teže padaju, ali je, barem u početku, izvučena korist ekvivalentna.
Citat:
Ivan Dimkovic: E a ako nekom uspe da kompresuje proizvoljnu random sekvencu - od mene dobija 10 gajbi piva kojeg zeli

MajorFatal, za mene bi ovo bio dovoljan podstrek da naučim to malo programiranja neophodnog da implementiram tvoj algoritam. S obzirom da ovde u Srbiji ne raspolažem Dimkovićevim finansijskim resursima, bio bih spreman da dam svoj skroman doprinos u vidu 2 gajbe gorenavedenog piva.
Edit - sintaksa

[Ovu poruku je menjao jablan dana 02.01.2006. u 20:04 GMT+1]
[ MajorFatal @ 02.01.2006. 21:32 ] @
Ama kad nesto ne ide onda ne ide. A ja sam pokusavao I to iz vise navrata da naucim da programiram I jednostavno nema sansi. Kontam po nesto ali kockice mi se jednostavno ne slazu u celinu. Konkretno prvo sam dosao u dodir sa Delphyjem u firmi Microcom u Bg. Tu sam naucio neke da kazem osnove. Onda sam bas u nameri da ne odustanem tako lako uzeo za diplomski da uradim neki program u Delphy-u. Toliko sam bio uspesan da je na kraju moj profesor kod koga sam uzeo diplomski morao da isprogramira 99% programa. Posle sam sam kod kuce provezbao onu knjigu od Laslo Krausa, neki primeri su mi radili a neki ne tek vec kod knjige od Paul Kimmela “Vodic za programere” vise nemam pojma sta se desava I veci deo jednostavno ne razumem. Imao sam najbolju volju ali...od C++ sam odustao kad mi nije poslo za rukom ni da iskompajliram program “Hallo world”, znaci da se ne upinjem vise. Ali da se ovo ne pretvori u moju tuznu ispovest.

Ono sto mene nervira jeste da iako na osnovu svojih skromnih iskustava sa programiranjem isto zamisljam kao sto ga zamislja mali Perica ipak mi se cini da bi za implementaciju ovog programa malo iskusnijem programeru trebalo jedno popodne. Sa druge strane za one manje iskusne ovo bi bila odlicna stilska vezba bilo bi tu itekako zanimljivog posla najvise oko odredjivanja koeficijenata upisivanja I tumacenja istih. Najgore od svega je da ste svojevremeno u okviru ovog istog podforuma kukali kako nemate sta da programirate, kao dajte da se nesto zanimljivo programira inace umresmo od dosade. Pa sta je sad?
U svakom slucaju ja cekam jos neko vreme da se neka dobra dusa smiluje na moje vapaje a onda se selim na Delphy, Kylix forum gde cu pokusati da uz vasu pomoc uradim program, s tim sto ce to tek biti plac majke bozije. Verujte mi da vam je lakse da to isprogramirate nego da se posle preganjate sa mnom i ucite me stvari koje meni jednostavno ne idu u glavu.

Dizem ulog na konkursu sada je nagrada 1 malo pivo I kesica “Prima” stapica.


[Ovu poruku je menjao Mihajlo Cvetanović dana 07.09.2011. u 15:56 GMT+1]
[ MajorFatal @ 06.01.2006. 09:09 ] @
Ala ste se uspavali. Vec tri dana se niko ne javlja. Nadam se da to znaci da programirate.

Srecan bozic svima zelim uz najlepsi pozdrav HRISTOS SE RODI!
[ srki @ 06.01.2006. 14:19 ] @
Vaistinu.

Sto se tice kompresije, pa niko nece da programira nesto za sta unapred zna da nece raditi. Ti hoces da kazes da ce tvoj algoritam da kompresuje bilo sta sto ima vise od 32 (ili koliko god) bitova? Zasto onda ne bi uzeo fajl od gigabajta pa ga kompresovao prvo na megabajte pa onda taj na kilobajte pa tako dalje sve dok ne dodjes do minimalnog fajla :-))) Drugim recima, ne razumem kako ne vidis zasto to ne bi radilo...

Evo malo na drugi nacin.
Zamisli da ti sa 32 bita mozes da kompresujes sekvencu od 64 bita. Broj mogucih zapisa od 64 bita je 2^64. Broj mogucih zapisa od 32 bita je 2^32. To znaci da dekompresijom mozes da dobijes samo 2^32 slucajeva a tih slucajeva bi trebalo da bude 2^64.
[ MajorFatal @ 07.01.2006. 21:39 ] @
Hristos se rodi. Evo I na bozic se bavim kompresijom sto znaci da cu se istom baviti cele godine ako je verovati narodnom predanju.

Citat:
srki

Sto se tice kompresije, pa niko nece da programira nesto za sta unapred zna da nece raditi.


Ama kako znas da nece raditi? Zadnje do cega smo dosli je da Dimkovic tvrdi da ce koeficijenti zauzimati vise mesta nego sam fajl a ja tvrdim suprotno s tim da nijedan nije dokazao svoje stavove. S jedne strane on je belosvetski strucnjak s druge strane ja sam pokazao I dokazao da onakav nacin zapisivanja koeficijenata biva sve racionalniji za sve vece brojeve (zato sam svojevremeno I nazvao ovu kompresiju “beskonacna” a ne zato sto verujem da se moze kompresovati do beskonacno malih vrednosti, “konacno resenje” je otuda sto sam posle duze razmisljanja konacno dosao do resenja). Evo jos jedan primer just for the record: Gorepomenuti izraz 2^64 koji zauzima 32 bita tj. manje od 64 bita ipak zauzima celih 50% od fajla, dok na primer izraz 2^8000 koji zauzima 48 bita u odnosu na 8000 bita zauzima oko 0,5% od fajla. Itd za jos vece vrednosti jos vece iskoriscenje.

Citat:
srki:  Ti hoces da kazes da ce tvoj algoritam da kompresuje bilo sta sto ima vise od 32 (ili koliko god) bitova? Zasto onda ne bi uzeo fajl od gigabajta pa ga kompresovao prvo na megabajte pa onda taj na kilobajte pa tako dalje sve dok ne dodjes do minimalnog fajla :-))) Drugim recima, ne razumem kako ne vidis zasto to ne bi radilo...


Upravo ta granica od 32 ili kolko vec bita ispod koje dolazi do ekspanzije umesto do kompresije I sprecava da se ovom modelu prisije to da bi visestrukom primenom algoritma rezultujuci fajl tezio nuli sto bi ovaj model cinilo nemogucim. U stvari ti si se dobro izrazio: dolazilo bi se do minimalnih fajlova s tim sto ja ne verujem da bi kod ovog modela bilo mesta za visestruku kompresiju tj. kompresiju u vise nivoa, mislim da bi se vec u prvom koraku dobijali izuzetno mali tj. kompresovani fajlovi. Doduse to sto ja verujem I mislim nista ne znaci dok ne dokazem a da dokazem ne mogu jer ne znam da programiram a vi necete da mi pomognete tako da mi ostaje samo da kukam.

Citat:
srki

Evo malo na drugi nacin.
Zamisli da ti sa 32 bita mozes da kompresujes sekvencu od 64 bita. Broj mogucih zapisa od 64 bita je 2^64. Broj mogucih zapisa od 32 bita je 2^32. To znaci da dekompresijom mozes da dobijes samo 2^32 slucajeva a tih slucajeva bi trebalo da bude 2^64.


A sad ti zamisli da ja bilo koji niz od 32 bita mogu da procitam kako hocu. Na primer mogu da ga procitam s leva na desno pa s desna na levo I da ta dva niza spojim u tom slucaju dobio sam novi niz od 64 bita. Ili da citam svaki drugi bit pa ceo niz po redu pa svaki drugi unazad itd. Kao sto vidis u 32 bita moze da se krije I vise od 2^64 kombinacija samo naravno treba znati izvuci ih odatle. Upravo to bi trebalo da se postize onakvim eksponencijalnim nacinom zapisivanja koeficijenata. Bili bi kraci kad se zapisu a “duzi” kad se protumace. Evo malo I na drugi nacin sto bi ti reko: Evo ga jedan brojac:
1: 000
2: 001
3: 010
4: 011
5: 100
6: 101
7: 110
8: 111
A evo ga I drugi brojac:
1: 0
2: 1
3: 00
4: 01
5: 10
6: 11
7: 000
8: 001
Kao sto vidis I sa manjim brojem bita se moze izbrojati isti broj kombinacija tako sto se duzina niza uvede kao dodatna informacija.

Al ajde da se ne lazemo I meni je ovo najsumljiviji deo cele ove price. S jedne strane logika, zdrav razum I teorija informacija mi govore da je ovo nemoguce izvesti. S druge strane ja jednostavno ne mogu da skontam kako to da do bilo kog broja ne moze da se dodje uz pomoc nekoliko pravilno odabranih koeficijenata. Takodje mi nije jasno ako ceo fajl nosi sa sobom gomilu informacija npr. Informacije koje je odgovarajuci engine u stanju da protumaci, preciznu poziciju na brojacu, redosled pojavljivanja na brojacu I verovatno jos neke informacije kojih ja sad ne mogu da se setim pa ako ja od svih tih informacija odaberem samo jednu za pamcenje tj. redosled pojavljivanja na brojacu to je onda manje informacija za pamcenje od one ukupne mase prema tome trebalo bi da je potrebno I manje bita za njihovo predstavljanje.
Bah nije ni bitno. Odavno sam se pomirio sa sudbinom da od ovoga najverovatnije nece biti nista, mogu samo jos da se nadam. Opet dizem ulog na konkursu: nagrada je: 1 malo pivo I kesica “Prima” stapica, smoki ili cips “Pik Cacak” PO SOPSTVENOM IZBORU! I polovina novca od prodatih kompresora. U pitanju su naravno milionski iznosi ;)
[ kurt.hectic @ 08.01.2006. 01:26 ] @
Citat:
Ama kako znas da nece raditi? ... ja sam pokazao I dokazao da onakav nacin zapisivanja koeficijenata biva sve racionalniji za sve vece brojeve
Nisi pokazao, nego si samo rekao. Ali kada si rekao nehotice si bio u pravu. Kod postaje efikasniji sa povećanjem kardinalnosti alfabeta koji se koristi za kodiranje.

To je prosta posledica slabog zakona o velikim brojevima ali ne dokazuje da tvoj način kodiranja išta kompresuje.
Citat:
primer just for the record: Gorepomenuti izraz 2ˆ64 koji zauzima 32 bita tj. manje od 64 bita ipak zauzima celih 50% od fajla, dok na primer izraz 2ˆ8000
Nije ti dobar primer. Kompresor treba da sabija podatke u srednjem, a ne da sabija podatke za nekoliko datih primera. Znači, za sve moguće ulazne nizove podataka, sa velikom verovatnoćom izlazni niz podataka mora da bude kraći. Da bi to pokazao nije ti potrebno da znaš programiranje. Programiranje dolazi tek na kraju kada je sve objašnjeno.
Citat:
A sad ti zamisli da ja bilo koji niz od 32 bita mogu da procitam kako hocu.
Tvoj rezultat je i dalje slabiji od rezultata teorije informacija. Tu se kaže da za bilo koju strategiju kodiranja nije moguće opisati izvor podataka bez gubitaka pomoću izvora manje entropije.

Pošto rezultat važi za bilo koju strategiju, važi i za čitanje unapred, unazad, svakog drugog, svakog trećeg itd. Sorry.

Ti se nadaš da ćeš ako opišeš kodiranje koje deluje fensi da nekako magično preskočiš fundamentalna ograničenja. To ne ide tako.
Citat:
Takodje mi nije jasno ako ceo fajl nosi sa sobom gomilu informacija npr. Informacije koje je odgovarajuci engine u stanju da protumaci, preciznu poziciju na brojacu, redosled pojavljivanja na brojacu I verovatno jos neke informacije kojih ja sad ne mogu da se setim pa ako ja od svih tih informacija odaberem samo jednu za pamcenje tj. redosled pojavljivanja na brojacu to je onda manje informacija za pamcenje od one ukupne mase
Ovo ti je ključna primedba. Tačno je da ako znaš dosta o izvoru da ćeš bolje da ga kompresuješ. Ako znaš nešto o izvoru, tj. ako imaš engine koji razume šta to izvor šalje, onda izvor sigurno nije "random-like", već ima neku skrivenu strukturu. "Random" podaci su po definiciji random baš zato što ne možeš da u njima pronađeš strukturu.

Računanjem entropije možeš da proveriš da li postoji struktura ili ne.

Ako struktura postoji, onda možeš da pređeš na smišljanje načina kako da je iskoristiš da bi kompresovao podatke. Zavisno od strukture podataka i zavisno od kvaliteta rekonstrukcije koju želimo postoje različite strategije.

Ako nikakva struktura ne postoji i podaci su stvarno "random", onda nema pomoći, to ti je kao da hoćeš da staviš kilo u pola kile: nemoguće. Ukratko, ne dobijaš pomoć jer tvoj napad na problem ne obećava.
[ srki @ 08.01.2006. 07:22 ] @
Citat:
MajorFatal
Ama kako znas da nece raditi? Zadnje do cega smo dosli je da Dimkovic tvrdi da ce koeficijenti zauzimati vise mesta nego sam fajl a ja tvrdim suprotno s tim da nijedan nije dokazao svoje stavove.

Pa Senon je to dokazao jos 1948. Tako mi znamo da to nece raditi:
http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf

Ja stvarno ne razumem kako me nisi shvatio. Ako imas fajl od 32 bita i pokusavas da ga otpakujes koliko razlicitih fajlova mozes da dobijes? Mozes da dobijes maksimalno 2^32 razlicita fajla. A koliko ima razlicitih fajlova od 64 bita? Ima ih 2^64. To znaci da otpakivanjem fajla od 32 bita ne mozes da dobijes bilo koji fajl.

[Ovu poruku je menjao srki dana 08.01.2006. u 08:27 GMT+1]
[ ivan.mile @ 08.01.2006. 10:45 ] @
Citat:

Evo malo I na drugi nacin sto bi ti reko: Evo ga jedan brojac:
1: 000
2: 001
3: 010
4: 011
5: 100
6: 101
7: 110
8: 111
A evo ga I drugi brojac:
1: 0
2: 1
3: 00
4: 01
5: 10
6: 11
7: 000
8: 001
Kao sto vidis I sa manjim brojem bita se moze izbrojati isti broj
kombinacija tako sto se duzina niza uvede kao dodatna informacija.


Ovaj drugi brojač neće raditi kako treba. Zašto? Zato što si napravio
prefiksne kodne reči. Npr. ako očitaš 0000001 šta si ti ustvari očitao?
Da li 000 001 ili 00 0 001 ili 0 0 0 0 0 1 ili 0 0 0 001... ? Drugim
rečima, otkud znaš gde ti je granica između dve kodne reči, kako
razlikuješ da li ti je stigla 3 (00) ili dve 1 (0 0)?
[ formeye @ 08.01.2006. 13:39 ] @
Citat:
Evo malo I na drugi nacin sto bi ti reko: Evo ga jedan brojac:
1: 000
2: 001
3: 010
4: 011
5: 100
6: 101
7: 110
8: 111
A evo ga I drugi brojac:
1: 0
2: 1
3: 00
4: 01
5: 10
6: 11
7: 000
8: 001
Kao sto vidis I sa manjim brojem bita se moze izbrojati isti broj
kombinacija tako sto se duzina niza uvede kao dodatna informacija.

Moras da pamtis i duzinu, a u ovom slucaju duzina ide od 1-3 bita. Za zapis duzine ti je, dakle, potrebno 2 bita. Sto znaci da bi ti drugi brojac izgledao ovako:
[duzina] [vrednost]
1: 01 0
2. 01 1
3. 10 00
4. 10 01
...
Tako da ovo ispadne ekspanzija...

[Ovu poruku je menjao formeye dana 08.01.2006. u 14:39 GMT+1]
[ MajorFatal @ 09.01.2006. 22:33 ] @
Citat: Nisi pokazao, nego si samo rekao. Ali kada si rekao nehotice si bio u pravu.

Ili sam pokazao, ili rekao ili nehotice bio u pravu. Dogovori se pa kazi.

Citat: Kompresor treba da sabija podatke u srednjem, a ne da sabija podatke za nekoliko datih primera. Znači, za sve moguće ulazne nizove podataka, sa velikom verovatnoćom izlazni niz podataka mora da bude kraći.

U srednjem sta? Ovde ne razumem sta si napisao.
Posto sam po tvom priznanju I nehotice bio u pravu smatram da je stvar dokazana I da ce zaz sve primere izlazni niz podataka biti kraci. Primere svako moze odabrati po sopstvenom nahodjenju. Inace kako znas da je nehotice, ja sam bre razmisljo o tome.

Citat: Pošto rezultat važi za bilo koju strategiju, važi i za čitanje unapred, unazad, svakog drugog, svakog trećeg itd. Sorry.

Otkud znam. Ja sam se nado da ce cudnih nacina citanja da me spase operator ^ (na) on obezbedjuje da se vise puta citaju nizovi bita ispred I iza njega I time bi se dobijala prividna ekspanzija inace kraceg niza bita dok bi se o pravilima citanja brinuo odgovarajuci engine. Nisam znao da nije moguce opisati izvor podataka bez gubitka pomocu izvora manje entropije.



Citat:
kurt.hectic:  Ako znaš nešto o izvoru, tj. ako imaš engine koji razume šta to izvor šalje, onda izvor sigurno nije "random-like", već ima neku skrivenu strukturu.


Ja kolko znam EXE fajlovi sa jedne strane su smisleni tj. postoji engine koji razume sta to oni salju, a sa druge strane toliko su rastrkane structure da mogu da se posmatraju kao random-like o cemu svedoci I slab uspeh uobicajenih nacina kompresije nad njima.

Citat:
srki

Ja stvarno ne razumem kako me nisi shvatio. Ako imas fajl od 32 bita i pokusavas da ga otpakujes koliko razlicitih fajlova mozes da dobijes? Mozes da dobijes maksimalno 2^32 razlicita fajla. A koliko ima razlicitih fajlova od 64 bita? Ima ih 2^64. To znaci da otpakivanjem fajla od 32 bita ne mozes da dobijes bilo koji fajl.


Nema potrebe da se ponavljas, za ovako postavljeno pitanje vec sam ponizno priznao da nemam pravi odgovor. Mada tako kako ti postavljas stvari gledajuci nijedna vrsta kompresije ne bi bila moguca jer nijedan kraci fajl ne bi mogao da se raspakuje u nijedan duzi zbog broja kombinacija koje su u stanju da tvore kraci I duzi fajl.

Ovde cu ja ponoviti ono sto meni I dalje nije jasno. Kako to da redni broj pojavljivanja fajla na brojacu ne moze da se dobije sa nekih desetak petnaest sabiraka – koeficijenata? U primeru sa 2^8000 gde isti zapis zauzima oko 0,5% od duzine fajla svi sabirci zajedno bi zauzimali 5-10%od velicine fajla. A ti I Dimkovic pak hocete da me ubedite da bi mi trebalo 200 I vise sabiraka. Pa to onda ne bi bio broj nego neosvojiva tvrdjava. Svako ko je gledao kviz “Brojke I slova” ili Muzicku/TV slagalicu tj. igru “Moj broj” svedok je koliki je procenat takmicara dolazio u veoma kratkom vremenu do tacnog broja I to sa unapred zadatim koeficijentima. A ovde bi se koeficijenti birali po sopstvenom nahodjenju oni koji najvise odgovaraju za postavljeni cilj (broj) I to bez vremenskog ogranicenja.


Citat:
ivan.mile: Ovaj drugi brojač neće raditi kako treba. Zašto? Zato što si napravio
prefiksne kodne reči. Npr. ako očitaš 0000001 šta si ti ustvari očitao?
Da li 000 001 ili 00 0 001 ili 0 0 0 0 0 1 ili 0 0 0 001... ? Drugim
rečima, otkud znaš gde ti je granica između dve kodne reči, kako
razlikuješ da li ti je stigla 3 (00) ili dve 1 (0 0)?


Znam gde mi je granica izmedju dve kodne reci tako sto mi sa brojaca u odredjenom trenutku stize tacno jedna kodna rec koju onda tumacim ili koristim vec na bilo koji smislen nacin, I ne pada mi napamet da ih pisem zajedno jednu do druge u tom obliku pa da onda ne znam gde mi je granica izmedju dve kodne reci. Konkretno ako je stanje na zaustavljenom brojacu 00 to je 3 a ne dve jedinice. A 0000001 je 128 (ako se nisam zabrojo) mozes proveriti ako nastavis drugi brojac.

Citat:
formeye: Moras da pamtis i duzinu, a u ovom slucaju duzina ide od 1-3 bita. Za zapis duzine ti je, dakle, potrebno 2 bita. Sto znaci da bi ti drugi brojac izgledao ovako:
[duzina] [vrednost]
1: 01 0
2. 01 1
3. 10 00
4. 10 01
...
Tako da ovo ispadne ekspanzija...


Informacija o duzini je sadrzana u samom nizu a vec sam napomenuo da stanja sa brojaca u ovom obliku ne bih pisao jedna do drugih tj. nije mi potrebna posebna informacija o duzini da bih razdvajao kodne reci.

Citat:
kurt.hectic

Ako nikakva struktura ne postoji i podaci su stvarno "random", onda nema pomoći, to ti je kao da hoćeš da staviš kilo u pola kile: nemoguće. Ukratko, ne dobijaš pomoć jer tvoj napad na problem ne obećava.


Pa I nikakva struktura je nekakva struktura, takozvana “nikakva” bice da I za nju ima leka. Neki pametan cova rece da su za citav razvoj civilizacije zasluzni ljudi koji su pokusavali I uspevali da urade nemoguce. A da necu dobiti pomoc na sajtu specijalizovanom za pomoc sam skapirao davnih dana. Da ne zivim tu gde zivim cudio bih se, ovako nista.

Vec ste se navikli da sa svakim novim javljanjem dizem ulog na konkursu pa tako I ovog puta: 1 malo pivo, stapici “Prima”, smoki ili cips “Pik Cacak” po sopstvenom izboru I 49% akcija od preduzeca koje ce prodavati kompresore. Jeste da deluje da je manja ponuda nego prosli put kad sam nudio polovinu zarade tj. 50% ali podela fifti-fifti implicira ortacko ili drustvo sa ogranicenom odgovornoscu sto su ekonomski dokazano propali I neefikasni modeli tako da je 49% u solidnom I ekonomski uspesnom modelu akcionarskog drustva mnogo bolja ponuda. Eto ga jos jedan primer kako je manje u stvari vece I kako stvari nisu uvek onakve kakvim se cine na prvi pogled.
[ srki @ 09.01.2006. 23:56 ] @
Citat:
A da necu dobiti pomoc na sajtu specijalizovanom za pomoc sam skapirao davnih dana. Da ne zivim tu gde zivim cudio bih se, ovako nista.

A nego sta radimo nego ti pomazemo? Pomazemo ti da shvatis da je ovo uzaludno i da ne gubis vreme. Ja ne razumem kakvu vrstu pomoci bi hteo. Sta bi ti rekao kada bi te neko pitao da mu pomognes da stavi dva litra vode u flasu koja prima litar? Verovatno bi mu objasnio da ne moze (bez obzira na to kako sipa) pa bi se on kao ti ljutio sto neces da mu pomognes. Ja stvarno ne razumem ovakav tvoj stav pa koliko nas se javilo i ostavilo komentar u cilju da ti pomognemo a ti kazes da niko nece da ti pomogne. mi hocemo da ti pomognemo ali to sto se tebi ne svidja nacin na koji ti pomazemo je samo tvoj problem. Cak smo ti i ostavili link sa dokazima da tvoja kompresija nece raditi.

Citat:
Mada tako kako ti postavljas stvari gledajuci nijedna vrsta kompresije ne bi bila moguca jer nijedan kraci fajl ne bi mogao da se raspakuje u nijedan duzi zbog broja kombinacija koje su u stanju da tvore kraci I duzi fajl.


Ne nego to samo znaci da bilo koja kompresija ne moze da spakuje sve fajlove. Ako pokusas da spakujes random fajl sa RAR-om ili ZIP-om dobices veci fajl od originala.

Citat:
Kako to da redni broj pojavljivanja fajla na brojacu ne moze da se dobije sa nekih desetak petnaest sabiraka – koeficijenata? U primeru sa 2^8000 gde isti zapis zauzima oko 0,5% od duzine fajla svi sabirci zajedno bi zauzimali 5-10%od velicine fajla.

A sta ti predstavlja redni broj fajla? Zar nije to sam taj fajl?
Recimo ako poredjas (u binarnom zapisu brojeve po redu:
000 ( a to je 0 dekadno)
001 ( to je 1 dekadno)
010 (2 dekadno)
011 (3 dekadno)
100 (4 dekadno)
101 (5 dekadno)
...
Ako ti hoces da zapises fajl pod rednim brojem 5 to znaci da moras da upises 101 tj. nista nisi skratio. Ne razumem zasto kazes da bi kompresija radila za 32 bita a ne bi radila za npr. 8 bitova? Koji je minimalni broj bitova da bi tvoj kompresija kao radila?

Ajde ovako, posto zelis da ti pomognemo posaljes mi 500 evra i ja ti uradim program. Ako kompresija radi za bilo koji fajl ja ti vratim tih 500 evra i odreknem se svih autorskih prava i prava na bilo kakvu buducu zaradu?
[ Yu Raider @ 11.01.2006. 17:29 ] @
Citat:
srki:
Ajde ovako, posto zelis da ti pomognemo posaljes mi 500 evra i ja ti uradim program. Ako kompresija radi za bilo koji fajl ja ti vratim tih 500 evra i odreknem se svih autorskih prava i prava na bilo kakvu buducu zaradu?


Eeeee Srbijo, Srbijo...

@MajorFatal
Iz iskustva znam da ti verovatno niko nece napisati program, moj savet je da se ipak zavatis malo programiranja. Pa nije bwe tolko tesko, ja, koji sam star 13 godina sam (skoro) napravio program za pravljenje autorunova... Doduse ne znam bas mnogo o otvaranju i pisanju binarnih fajlova (zapravo, nista ne znam o tome)... Ali da bi ti dogurao dotle nemoj da ocekujes da ce to biti prvi program koji si napravio, to jednostavno ne ide tako, moras da pocnes od Hello World stvarcica...

Sto se tice kompajlera, preporucujem Bloodshed Dev-C++ (www.bloodshed.net).
Takodje, uopste i ne moras da koristis C++, mozes da to isto uradis i iz Visual BASIC-a na primer, u sv. slucaju izbor je na tebi...

Srecno!

[Ovu poruku je menjao Yu Raider dana 11.01.2006. u 18:35 GMT+1]
[ formeye @ 11.01.2006. 19:01 ] @
Citat:
@MajorFatal
Iz iskustva znam da ti verovatno niko nece napisati program, moj savet je da se ipak zavatis malo programiranja. Pa nije bwe tolko tesko, ja, koji sam star 13 godina sam (skoro) napravio program za pravljenje autorunova... Doduse ne znam bas mnogo o


Da postoji iole bilo kakva sansa da ovo proradi, nasao bi se neko da napise program - kolega i ja smo radili kompresiju za slike iako je, generalno, uzaludno jer i ovako ima dosta formata...

@MajorFatal
Da li tvrdis da ovom tvojom kompresijom je moguce svaki fajl kompresovati na fajl manji od njega samog?
[ Ivan Dimkovic @ 11.01.2006. 19:38 ] @
Citat:

Eeeee Srbijo, Srbijo...


Bas tako, eto par nas pokusava da objasni coveku da to ne ide, iz valjda nekog iskustva - pa mora i na plasticni nacin sa "500 eura" ;-)
[ srki @ 11.01.2006. 21:47 ] @
Ma moze i za 100€ :-)
[ MajorFatal @ 11.01.2006. 23:14 ] @
Citat: Ja ne razumem kakvu vrstu pomoci bi hteo.

Hteo bih da mi neko uradi program koji ja sam ne mogu da uradim.

Citat: Sta bi ti rekao kada bi te neko pitao da mu pomognes da stavi dva litra vode u flasu koja prima litar? Verovatno bi mu objasnio da ne moze (bez obzira na to kako sipa) pa bi se on kao ti ljutio sto neces da mu pomognes.

Ne bih nista objasnjavo nego bih sipo dok se sve ne prelije, isto tako ocekujem od vas da uradite program pa ako isti ne bude kompresovao podatke tek tad cu da poverujem da ova moja ideja nije dobra.

Citat: mi hocemo da ti pomognemo ali to sto se tebi ne svidja nacin na koji ti pomazemo je samo tvoj problem.

Pa normalno da mi se ne svidjaju jalove rasprave, teoretisanje, zajebavanje I provokacije. Inace ofiro vas je Jablan kada je rekao da je za implementaciju ovog programa potrebno “nesto malo programiranja” pa kad je tako sta cekate? Nemojte se vise brukati nego uradite program.

Citat: Cak smo ti i ostavili link sa dokazima da tvoja kompresija nece raditi.

Link je da izvines samo sa dokazima da niko pre mene nije razmisljao na ovaj nacin.
Citat:
srki: A sta ti predstavlja redni broj fajla? Zar nije to sam taj fajl?


Pa sad I jeste I nije. Jeste jer je svaki fajl “brojac samog sebe” a nije jer postoji I drugi redni broj fajla tj. dekadni zapis pozicije fajla a na njega sam ja konkretno mislio kada sam pominjao redni br. fajla koji se da krace zapisati uz pomoc gorepominjanih koeficijenata.

Citat:
srki
Recimo ako poredjas (u binarnom zapisu brojeve po redu:
000 ( a to je 0 dekadno)
001 ( to je 1 dekadno)
010 (2 dekadno)
011 (3 dekadno)
100 (4 dekadno)
101 (5 dekadno)
...
Ako ti hoces da zapises fajl pod rednim brojem 5 to znaci da moras da upises 101 tj. nista nisi skratio. Ne razumem zasto kazes da bi kompresija radila za 32 bita a ne bi radila za npr. 8 bitova?


Uvek nadjete najgore primere, al ajde:

Odaberemo fajl 101 (5 dekadno). Binarni I dekadni zapis su nam isti jer je broj 5 kodovan sa 3 bita tj. 101. Postoji I treci zapis uz pomoc koeficijenata I izgledao bi ovako: 2^2 +1. On bi zauzimao vise prostora u memoriji I od binarnog I od dekadnog tj. zauzimao bi 15 bita (po 3 bita za svaki znak I broj-I to pod uslovom da smo preostale kombinacije iza 101 iskoristili da kodujemo operatore ^ I +)

Pogledajmo jos jedan mali ali za nijansu normalniji primer gde smo se odlucili da sve brojeve dekadnog sistema kodujemo sa po 4 bita:
Odaberemo fajl 1110. Fajl je 14-ti po redu kad bi ga gledali kao deo izlaznih vrednosti brojaca sa 4 bitna mesta. Redni broj fajla 14 bi nam ovaj put zauzimao vise mesta u memoriji nego u prethodnom primeru tj 8 bita (po 4 bita za jedinicu I cetvorku) tj. vise od binarnog zapisa samog fajla (4 bita). I da ne zaboravimo zapis uz pomoc koeficijenata za br. 14 bi mogao da izgleda ovako: 3^2 +5 sto zauzima 20 bita (po 4 bita za svaki broj I znak) ponovo vise I od binarnog I od dekadnog.

E sad bih iskoristio priliku da ponovim cinjenicu vezanu za zapisivanje brojeva koeficijentima. Dakle na 32 bita se nalazi granica od koje iduci ka visim vrednostima zapisivanje uz pomoc koeficijenata postaje sve racionalnije. Zapis 2^31 (zauzima 32 bita) zauzima vise mesta od niza koji pokusava da opise a zapis 2^33 (takodje zauzima 32 bita) zauzima manje mesta. Sto idemo ka vecim vrednostima zapis je sve racionalniji: 2^64 zauzima 32 bita u odnosu na 64 to je 50%, 2^8000 zauzima 48 bita u odnosu na 8000 to je manje od 0,5% itd.

E sad da predjemo na primer koji bi odgovarao ovoj vrsti kompresije:
Odabracemo fajl sa 8000 jedinica jedna do druge. To je 8000 bita u memoriji. Dekadni zapis je broj sa oko 2500 cifara tj. 20000 bita. Dok je zapis koeficijentima 2^8000 tj. 48 bita. E sad ovaj primer na zalost ne moze da posluzi kao dokaz da zapisivanjem koeficijentima dolazi do kompresije jer je “namesten” tj. bio je dovoljan samo 1 koeficijen za opis rednog broja fajla. Meni je potreban dokaz da bi ovakav nacin zapisivanja bio racionalan za svaki broj iz opsega 0 do 2^8000 -1 a to se moze postici samo odgovarajucim programom. Opet na osnovu toga sto samo 1 koeficijent koji zauzima 48 bita tj. 0,5% duzine niza obuhvata ceo opseg vrednosti koje treba da se opisu sklon sam da verujem da bi I one vrednosti izmedju mogle da se opisu sa relativno malim brojem koeficijenata tj. da mi za bilo koji fajl duzine 8000 bita tj. njegov redni broj nije potrebno vise od 200 sabiraka da bih ga dobio.
Mislim da je stvar jos ociglednija za jos vece fajlove. Ne mogu da zamislim da bi za fajl duzine megabajta bilo potrebno 2000 ili koliko vec sabiraka. Jeste da bi redni brojevi takvih fajlova bili veci ali nisu nip o cemu slozeniji a I vrednosti koeficijenata bi bile vece a citav opseg vrednosti bi se dao opisati sa jednim koeficijentom npr 2^8388608 sto je 72 bita.

Citat:
srki:  Koji je minimalni broj bitova da bi tvoj kompresija kao radila?


To cemo utvrditi eksperimentalnim putem kad budemo imali program. Za sada mogu samo da lupim da je to negde izmedju 32 I 320 bita.

Citat:
srki

Ajde ovako, posto zelis da ti pomognemo posaljes mi 500 evra i ja ti uradim program. Ako kompresija radi za bilo koji fajl ja ti vratim tih 500 evra i odreknem se svih autorskih prava i prava na bilo kakvu buducu zaradu?


Jeste da ovo ne zavredjuje nikakav komentar al cisto da se ne bi ponovilo. Mnogo je kume. Da imam 500 evra odma bi se zenio. Vidim da nisi odavde pa cisto da te upoznam sa prilikama. U mom malom gradicu za 500 evra bi moro da rintam najmanje pola godine I to bez da jedem I pijem. Znaci nista od dogovora. Za sada samo pored uobicajenih malo pivo itd. Nudim 51% akcija od firme koja ce prodavati kompresore. Znaci kontrolni paket akcija na izvolte.

Citat:
Yu Raider

@MajorFatal
Iz iskustva znam da ti verovatno niko nece napisati program, moj savet je da se ipak zavatis malo programiranja.


Poznajuci sopstvene programerske mogucnosti to mi je stvarno zadnja solucija. Ono sto sam pretio da cu da se selim na Delphi, Kylix forum to ja samo zavaravam samog sebe. Jedino se tesim ako ipak dodje do toga da cu mozda nauciti nesto novo a mozda I prokinem pa pocnem da programiram. Vec sam pisao sta me sve nervira u ovoj situaciji ali da dodam jos I ovo: neke kolege ovde pisu programe bukvalno u hodu bez imalo razmisljanja I zapinjanja za njih bi bio cipkin dim da isprogramiraju ovo ali nece. Inace hvala na podrsci.

Citat:
formeye
@MajorFatal
Da li tvrdis da ovom tvojom kompresijom je moguce svaki fajl kompresovati na fajl manji od njega samog?


Ne. Samo fajlove koji su veci od odredjene granicne vrednosti za koju jos ne znam tacno gde je. Dakle kompresija ne bi radila za izuzetno male fajlove.

Citat:
Ivan Dimkovic: Bas tako, eto par nas pokusava da objasni coveku da to ne ide, iz valjda nekog iskustva - pa mora i na plasticni nacin sa "500 eura" ;-)


Od tebe se I ocekivalo da podrzavas ucene. Umesto da si ukorio bezobraznika…

Citat:
srki: Ma moze i za 100€ :-)


da se nadjemo na 20 evra, litar rakije iz Valjevskog kraja i kilo duvan cvaraka?
[ Ivan Dimkovic @ 11.01.2006. 23:44 ] @
Nisi ti citao comp.compression izgleda - tvoja teorija je odavno obradjena ;)

http://www.faqs.org/faqs/compression-faq/part1/

Citat:

Yet another popular idea is to split the input bit stream into a sequence of
large numbers, and factorize those numbers. Unfortunately, the number of bits
required to encode the factors and their exponents is on average not smaller
than the number of bits of the original bit stream, so this scheme too cannot
compress all data.
Another idea also related to primes is to encode each
number as an index into a table of primes and an offset relative to the indexed
prime; this idea doesn't work either because the number of bits required to
encode the index, the offset and the separation between index and offset
is on average not smaller than the number of bits of the original bit stream.


Dakle, po 100-ti put - tvoj metod generalno ne radi, moze da upali za par namestenih slucajeva, ali u proseku ce informacija za skladistenje koeficijenata (faktora) biti veca od samog originalnog broja, pod uslovom da skladistis originalni broj na optimalan nacin. Nema potrebe da pravis program za to, postoji matematicki dokaz da je to sto hoces nemoguce.

Cak najobicnija RLE metoda radi bolje za tvoju namestenu sekvencu od 8000 jedinica - RLE metoda daje 16 bita, tvoja metoda daje 48 bita.

Postoje daleko optimalniji nacini reprezentacije originalnog signala, recimo aritmeticko kodiranje - i ako uporedis aritmeticki kodiran signal, sa serijom tvojih "koeficijenata" - doci ces do zakljucka da je aritmeticki kodiran signal uvek kraci i blizi entropiji.

U suprotnom, ti si opet izmislio kompresiju slucajnih podataka - a to smo valjda vec pokrili.

Hajde ovako,

- Pretpostavimo da tvoj metod radi za svaki fajl, tj. dovoljno dugu sekvencu M pseudo-slucajnog sadrzaja - sto je ono sto ti tvrdis.

- Zatim, pretpostavimo da si ti sekvencu M kompresovao vec jednom tvojim metodom i dobio sekvencu N, koja je i dalje duza od tvoje minimalne duzine, i zadovoljava tvoj uslov za kompresiju da je "dovoljno dugacka"

- Sada ces sekvencu N opet pohraniti u tvoj metod, i, po tebi - dobiti sekvencu X, koja je kraca od sekvence N

- Ponavljamo ovo dovoljno veliki broj puta...

Sta dobijamo na kraju? Beskonacnu kompresiju?

Back to the drawing board.

[Ovu poruku je menjao Ivan Dimkovic dana 12.01.2006. u 00:45 GMT+1]
[ srki @ 12.01.2006. 00:27 ] @
Citat:
MajorFatal: da se nadjemo na 20 evra, litar rakije iz Valjevskog kraja i kilo duvan cvaraka?


Jao brate, ma mogu i samo cvarci, za njih bi sada dao sta god da mi trazis!!! Ajde ti mi to nekako posaljes a ja uradim program i ako radi ja se odricem zarade i posaljem ti 10000€. Moze?

Inace nisi lepo razumeo moj primer sa sipanjem vode. To je isto kao da ti neko kaze da ako na neki poseban nacin sipas mozes da uguras 2 litra a ne objasni ti tacno koji je to poseban nacin. Drugim recima ti treba da nam das tacan format kompresovanog fajla. Gde zapisujes broj koeficijenata, koliko bitova to zauzima, koliko bitova ti zauzimaju koeficijenti i kako se to odredjuje itd...Kako da ti pomognemo ako ni ti nisi tacno objasnio kako izgleda taj fajl. Objasni nam cemu ti sluzi svaki bit u tom fajlu.

[Ovu poruku je menjao srki dana 12.01.2006. u 01:28 GMT+1]
[ masetrt @ 12.01.2006. 10:59 ] @
Citat:
Meni je potreban dokaz da bi ovakav nacin zapisivanja bio racionalan za svaki broj iz opsega 0 do 2^8000 -1 a to se moze postici samo odgovarajucim programom

Program koji ti trazis ne bi nista dokazao. Mozda bi pokazao da si u nekim slucajevima u pravu a u nekim ne, ali dokazao ne bi nista jer ko ce da proba sve moguce kombinacije? (odgovor niko)

Code:
To cemo utvrditi eksperimentalnim putem kad budemo imali program. Za sada mogu samo da lupim da je to negde izmedju 32 I 320 bita.

Opet pogresan pristup. Ne moze se nesto sto treba da bude egzaktno utvrdjivati eksperimentalnim putem, vec se mora matematicki dokazati.

Code:
Samo fajlove koji su veci od odredjene granicne vrednosti za koju jos ne znam tacno gde je. Dakle kompresija ne bi radila za izuzetno male fajlove.

WTF

Uopste ne zelim da ulazim u pricu o tvom algoritmu za kompresiju (jer postoje ljudi koji su na slican nacin razmisljali mnogo pre tebe) nego o pristupu problemu. Sta bi bilo da projektujes kuce i da za nesto samo osecas da si u pravu a kad se kuca sagradi ispostavi se da nije bas tako? Kao sto ti je Ivan rekao prvo sve isplaniraj, dokazi(matematicki), pa kad ljudima ovde predocis dokaz tuci ce se ko ce da ti implemenntira algoritam. U svakom slucaju samo napred.
[ MajorFatal @ 13.01.2006. 09:17 ] @
Srecna svima srpska nova godina, petak 13-ti i treci dan kurban bajrama. Na novopristigla pitanja cu odgovoriti odmah posle nove godine.
[ MajorFatal @ 13.01.2006. 14:48 ] @
Evo naso sam malo vremena pa cu odgovoriti pre nove godine. Cisto da Jablan ima sta da cita za docek ;)

Citat:
Ivan Dimkovic: Nisi ti citao comp.compression izgleda - tvoja teorija je odavno obradjena ;)


Citao sam comp.compression I zaista nasao sam neke SLICNE primere ali ne i ISTI.

Citat: Yet another popular idea is to split the input bit stream into a sequence of large numbers, and factorize those numbers. Unfortunately, the number of bits required to encode the factors and their exponents is on average not smaller then the number of bits of the original bit stream, so this scheme too cannot compress all data.

Za jedno oko konj corav. Eto kako ponekad finese odlucuju pobednika. I da ih sad covek lepo pita zasto ste za ime boga delili ulazni niz bita na sekvencu velikih brojeva verovatno ne bi imali sta da kazu. A da su samo malo apstrahovali ideju kao sto sam ja to ucinio dobili bi pravi rezultat. Posledica njihove deobe je sledeca: kako ni do jednog broja nije lakse ili teze doci uz pomoc koeficijenata (faktora) za vecu kolicinu brojeva bili su im potrebni visestruki setovi koeficijenata plus informacije o deobi tj ponovnom sastavljanju sekvence brojeva u pocetni niz - I kvota je premasena. Tolika kolicina informacija zauzima vise mesta nego pocetni niz. A sta se desava u mom modelu: Ceo fajl se tretira kao samo jedan broj. Za samo jedan broj potreban je samo jedan set koeficijenata da ga opise I nema pamcenja dodatnih informacija o deobi tj. sastavljanju sekvence brojeva. Za razliku od njihovog primera koji je kompresovao samo neke podatke program uradjen po mom modelu bi za dovoljno velike fajlove kompresovao sve podatke.

Citat:
Ivan Dimkovic
Dakle, po 100-ti put - tvoj metod generalno ne radi, moze da upali za par namestenih slucajeva, ali u proseku ce informacija za skladistenje koeficijenata (faktora) biti veca od samog originalnog broja, pod uslovom da skladistis originalni broj na optimalan nacin. Nema potrebe da pravis program za to, postoji matematicki dokaz da je to sto hoces nemoguce.


Po 1000-ti put to sto SLICAN primer dokazano ne radi nije dokaz da moj primer ne radi. Inace svaka cast na moci opazanja primeri su zaista slicni ali slicni su I zaprezna kola I porse u oba slucaja u pitanju je prevozno sredstvo ali tu svaka slicnost prestaje.

Citat:
Ivan Dimkovic
Hajde ovako,

- Pretpostavimo da tvoj metod radi za svaki fajl, tj. dovoljno dugu sekvencu M pseudo-slucajnog sadrzaja - sto je ono sto ti tvrdis.

- Zatim, pretpostavimo da si ti sekvencu M kompresovao vec jednom tvojim metodom i dobio sekvencu N, koja je i dalje duza od tvoje minimalne duzine, i zadovoljava tvoj uslov za kompresiju da je "dovoljno dugacka"

- Sada ces sekvencu N opet pohraniti u tvoj metod, i, po tebi - dobiti sekvencu X, koja je kraca od sekvence N

- Ponavljamo ovo dovoljno veliki broj puta...

Sta dobijamo na kraju? Beskonacnu kompresiju?

Back to the drawing board.


E pa sad ovo vec nije fer sta mi radis. Na ovo pitanje sam vec odgovarao Srkiju 07.01.2006. Pitanje je bilo sto ne bih kompresovao gigabajte u megabajte, megabajte u kilobajte itd. Odgovor cu naravno ponoviti I malo prosiriti.

Upravo ona granica velicine fajla ispod koje zapisivanje koeficijentima jos nije doslo do izrazaja kao racionalan nacin I ispod koje dolazi do ekspanzije umesto do kompresije sprecava da se ovom modelu prisije etiketa da bi visestrukom primenom algoritma rezultujuci fajl tezio nuli sto bi ovaj model cinilo nemogucim. U odgovoru Srkiju sam izrazio sumnju da bi uopste bilo mesta za visestruku kompresiju tj. kompresiju u vise nivoa ali sada bih jos da potsetim na cinjenicu da bi ovakva vrsta kompresije davala sve bolje rezultate sa sve vecim fajlovima tj. iduci “unazad” tj. kompresujuci sve manje fajlove dobijali bi se sve slabiji rezultati tj. sve manji stepen kompresije sto bi zajedno sa pamcenjem podataka o nivoima kompresije u jednom trenutku dovelo do pitanja racionalnosti daljeg kompresovanja. Uopste uzev iako ste u par navrata pokusali da mi prikacite nekakvu magicnost I volsebnost ovakve ideje kompresije u pitanju je ipak jedan prilicno realan model sa mnogobrojnim manama I vrlinama kao sto je I red.

I ono beskonacna kompresija sam vec objasnio: odnosilo se na sve veci stepen iskoriscenja sa sve vecim fajlovima a ne na teznju ka beskonacno maloj vrednosti za sve manje fajlove. Back to the drawing board.

Citat:
srki: Jao brate, ma mogu i samo cvarci, za njih bi sada dao sta god da mi trazis!!!


Posalji adresu I dobijes cvarke prvom prilikom. Kako je sezona svinjokolja prosla drzi palceve da ih jos ima u lokalnim mesarama inace ces morati da cekas do sledece jeseni.

Citat:
srki:  Drugim recima ti treba da nam das tacan format kompresovanog fajla.


Tacan format kompresovanog fajla bi bio (n,m) gde je n duzina fajla u bitima a m redni broj pojavljivanja fajla na brojacu iste duzine izrazeno putem koefiucijenata (faktora)

Citat:
srki:  Gde zapisujes broj koeficijenata, koliko bitova to zauzima,


Nigde, to bi bila suvisna informacija. Znaci nimalo.


Citat:
srki:  koliko bitova ti zauzimaju koeficijenti


Kolko god a ja opravdano smatram da ce to biti manje od ulaznog niza.

Citat:
srki: kako se to odredjuje


Kako se sta odredjuje? Daj boze da me pitas kako se odredjuju koeficijenti za odredjeni broj jer bi u tom slucaju ova rasprava krenula ka nekim tehnickim detaljima vezanim za samu implementaciju za sta je I bilo krajnje vreme.

Citat:
srki: Kako da ti pomognemo ako ni ti nisi tacno objasnio kako izgleda taj fajl. Objasni nam cemu ti sluzi svaki bit u tom fajlu.


E ako dosad nisam objasnio…

Citat:
masetrt: Program koji ti trazis ne bi nista dokazao. Mozda bi pokazao da si u nekim slucajevima u pravu a u nekim ne, ali dokazao ne bi nista jer ko ce da proba sve moguce kombinacije? (odgovor niko)

Citat:
To cemo utvrditi eksperimentalnim putem kad budemo imali program. Za sada mogu samo da lupim da je to negde izmedju 32 I 320 bita.

Opet pogresan pristup. Ne moze se nesto sto treba da bude egzaktno utvrdjivati eksperimentalnim putem, vec se mora matematicki dokazati.


Kad je neko u pravu ja to odmah priznajem. Obe primedbe su na mestu. Kako lose stojim sa matematikom meni bi jedan od mogucih dokaza bio da se program uradi pa ako kompresuje podatke I ideja je bila ispravna a ako ne kompresuje onda nije.

Citat:
masetrt:  Kao sto ti je Ivan rekao prvo sve isplaniraj, dokazi(matematicki), pa kad ljudima ovde predocis dokaz tuci ce se ko ce da ti implemenntira algoritam.


Ma tucicete se vi ko ce da implementira algoritam I kad vam kazem da imam cetri sestre za udaju. Srkiju sam vec nasao tanku zicu “zal za rodnom grudom” naci cu I vama. Ipak kako jos nisam stigao do te dekadentne faze da nudim sestre na konkursu u zamenu za program ponuda je sledeca: 90% akcija firme koja ce se baviti prodajom komresora. Malo li je? Srecna srpska nova godina.

[Ovu poruku je menjao Gojko Vujovic dana 22.01.2006. u 13:08 GMT+1]
[ formeye @ 14.01.2006. 10:40 ] @
Moras da shvatis jednu stvar - kompresije bez gubitka mogu da rade samo na jedan nacin - da neke stvari smanjuju (kompresuju) a neke sire.

Dokaz:
To jest, ako posmatras nizove bitova duzine n, njih ima tacno 2^n (oznacimo skup tih nizova sa A). Tvrdis da svaki od tih nizova mozes da sabijes na manju duzinu od n, dakle da niz a_i mozes da sabijes na n - k(a_i), gde je k(a_i) > 0 za bilo koje i. Odatle sledi da k(a_i) >= 1 za svako i, to jest n - k(a_i) <= n - 1 za svako i.

Nizova duzine n-1 ili manje, ima tacno 2^(n-1) + 2^(n-2) + ... + 2 + 1 = 2^n - 1 (oznacimo skup tih nizova sa B).

Funkcija koja slika A na B ne moze biti "1-1" (kardinalni broj skupa B je manji od kardinalnog broja skupa A), to jest postojace bar dva niza a_1 i a_2 iz A koji se slikaju u isti niz b_1 iz B. Samim tim ce biti nemoguce na osnovu niza b_1 odrediti koji je bio pocetni niz koji smo kompresovali. []


Ovo je bio matematicki dokaz (ispisan koliko sam mogao laickijim jezikom) da je ono sto zelis nemoguce uraditi.

Da bih predupredio pitanje tipa "dokazi da moj postupak ne valja" dovoljno je da kazem da je ovim gore dokazano da ne postoji postupak koji valja.

Analogno bi bilo traziti nacin da se izvrsi trisekcija ugla lenjirom i sestarom i da me pitas zasto tvoj nacin nije dobar. Nije dobar, jer je matematicki dokazano da je nemoguce.

Ne moram da podsecam da racunari rade na osnovu matematickog modela i da, samim tim, taj model savrseno odgovara realnosti, za razliku od stvari koje srecemo u fizici koja je samo priblizni matematicki model realnosti.
[ srki @ 14.01.2006. 11:10 ] @
Citat:
MajorFatal
Tacan format kompresovanog fajla bi bio (n,m) gde je n duzina fajla u bitima a m redni broj pojavljivanja fajla na brojacu iste duzine izrazeno putem koefiucijenata (faktora)

Koliko bitova bi trebalo da zauzima n? To je jako bitno jer inace ne mozemo da znamo sta je u fajlu broj n.
[ peka @ 18.01.2006. 02:33 ] @
Ali, svaka cast covjeku na upornosti. Toliko ljudi mu objasnjava da je nesto jednostavno nemoguce, postoje i matematicke teorije, ali covjek jednostavno ne odustaje.
[ MajorFatal @ 18.01.2006. 21:42 ] @
Citat:
formeye: Moras da shvatis jednu stvar - kompresije bez gubitka mogu da rade samo na jedan nacin - da neke stvari smanjuju (kompresuju) a neke sire.


Ova kompresija bi smanjivala vece fajlove a sirila izuzetno male tako da je ovaj uslov zadovolljen.

Citat:
formeye
Dokaz:
To jest, ako posmatras nizove bitova duzine n, itd.


Cim sam priznao da malo losije stojim sa matematikom odmah mi nudis matematicki dokaz. Trebalo mi je tri dana da svarim sta si onde napisao I jos tri da smislim odgovor. Pa evo sto se mene tice nisi morao matematicki da dokazujes nesto za sta sam Srkiju vec dva puta priznao da nemam odgovor. Ali dobro mozda volis da dokazujes tako da evo I treci jubilarni put tvoj dokaz stoji cvrsto kao kamen temeljac I dokazuje da je ono sto pokusavam nemoguce u bilo kojoj varijanti.

Ali kako sam ja jedan opasan nenavid iskoristicu priliku da ovde napisem bar dva momenta koja me bune kako kod ovog I ovakvog dokaza tako I kod svih ostalih.

Koliko razlicitih kombinacija ti nude 32 bitna mesta? Tacno 2^32. A ako 32 bitna mesta iskoristim da zapisem npr. Koeficijent 9^99 I onda pustim da ga engine procita tj. protumaci. tj. izracuna dobija se daleko veci broj nivoa razlikovanja rednog broja pojavljivanja fajla na brojacu. Zajedno sa ostalim koeficijentima koji sluze za finu nivelaciju pozicije fajla na brojacu trebalo bi da je moguce dobiti svaki broj pojavljivanja fajla uz minimalan br. bita. Karakteristicnije je za vece fajlove 56 bitnih mesta nudi 2^56 kombinacija 56 bita se moze iskoristiti za zapisivanje npr. 666^999 sto je zlo na naopako veci broj nivoa razlikovanja.

Drugi moment koji me buni je sledeci: 2^n – 1 = 2^(n-1) + 2^(n-2) + …+ 2 + 1
Sto je savrseno tacno. Ipak posto je n = (n-1) + 1 tj. nizovi 2^n se mogu dobiti tako sto se nizovima 2^(n-1) doda samo jedan bit ispred ja kontam da se samo malo drugacijim nacinom dodavanja tog jednog bita moze dobiti I veci broj kombinacija a evo I kako:
Ako taj jedan bit zapisemo kao samostalnu kombinaciju I tumacimo je u zavisnosti od toga koja je bila prethodna kombinacija bita dobija se 4*2^n bita tj. potencijalni brojac bi izgledao ovako:

b_1
0
b_2
0
b_3
0
.
.
.
b_n
0
b_1
1
b_2
1
.
.
b_n
1

sto znaci da bi samo uz pomoc nizova 2^(n-1) I jednog bita mogli da obelezimo svih 2^n kombinacija te bi nam preostalih 2^(n-2) + 2^(n-3) + itd postali cist visak a gde ima viska informacija ima I kompresije to sam od vas naucio. Dakle iako se neki nizovi ponavljaju razlicito se tumace u zavisnosti od prethodnog stanja na brojacu koje je uvek razlicito ili da pokusam da budem jos jasniji pocetak potencijalnog brojaca koji bi radio na tom principu bio bi:

0 .. 0
1 .. 1
2 .. 0
3 .. 00
4 .. 0
5 .. 01
6 .. 0
7 .. 10
8 .. 0
9 .. 11
10.. 0
11.. 01
12..1
13..10
14..1
15..11
16..1
17..00
18..1
19..01
20..10
21..11
22..00
23..01
24..11
25..10
26..00
27..11

sto ce reci da iako u ovim zadnjim kombinacijama mora da se pamti 4 bita 2 aktuelna I dva prethodna ipak smo iskodovali vise od 16 kombinacija koje bi nam dala 4 bitna mesta. Ovo bi trebao biti dokaz da je I sa manje od 2^(n-1) + 2^(n-2) + itd. Moguce obeleziti 2^n -1 kombinacija.

E moj Srki necemo mi daleko dogurati ako ti meni postavljas ovakva pitanja.

Citat:
srki: Koliko bitova bi trebalo da zauzima n?


Za razlicite ulazne fajlove I zapis n o duzini fajla bi zauzimao razlicit proctor u memoriji.

Citat:
srki:  To je jako bitno jer inace ne mozemo da znamo sta je u fajlu broj n.


Gde si u celom ovom izlaganju nasao da se pominje fajl broj n? Mogao si samo naci fajl broj m.

Citat:
peka: Ali, svaka cast covjeku na upornosti. Toliko ljudi mu objasnjava da je nesto jednostavno nemoguce, postoje i matematicke teorije, ali covjek jednostavno ne odustaje.


Sta znam ja cu ovo shvatiti kao kompliment.

Na vec cuvenom konkursu nudim 99% akcija firme koja ce prodavati kompresore. Sebi sam ostavio tek 1% cisto da mogu da zivotarim.
[ srki @ 18.01.2006. 22:23 ] @
Citat:
Gde si u celom ovom izlaganju nasao da se pominje fajl broj n? Mogao si samo naci fajl broj m.

Gde si ti video da sam ja rekao "fajl broj n"?
Ja te samo pitam kako da znamo koji bitovi u tom kompresovanom fajlu predstavljaju broj n.

Citat:
Za razlicite ulazne fajlove i zapis n o duzini fajla bi zauzimao razlicit proctor u memoriji.

Ali kako da znamo kako da znamo koji prostor zauzima n? To moramo da znamo da bismo znali koji bitovi u fajlu predstavljaju broj n. Jos uvek nismo dobili tacan format fajla i normalno da niko ne moze da ti pomogne (a ne da nece kako ti kazes).

[Ovu poruku je menjao srki dana 19.01.2006. u 00:40 GMT+1]
[ formeye @ 18.01.2006. 22:59 ] @
A.S. Matematicki dokaz ne sluzi da bi tebe zbunio. Veruj mi, vise bi mi prijalo da ti matematika "ide" jer bi onda odustao od odgovaranja na ovu temu.

Prvo da ti odgovorim na "drugi moment":
Ako nizu od n - 1 elemenata dodas jedan bit, dobijas niz od n elemenata - sta si onda kompresovao? (pocetna poruka je bila n bitova).

A sada prvi moment.
Na 32bita mozes da zapises 2^32 razlicite vrednosti. E sad, da li ces ih tretirati kao 1, 2, 3, ... ili 100, 200, 300, ... ili kako god, uvak ces moci da zapises najvise 2^32 razlicite vrednosti. Samim tim, ne postizes nikakvu "finu nivelaciju".

Citat:
Ova kompresija bi smanjivala vece fajlove a sirila izuzetno male tako da je ovaj uslov zadovolljen.

Nije. Kao sto si mogao da procitas u dokazu, odnos smanjivanje / povecavanje mora da postoji za svaku duzinu fajla. Dakle, ako kompresija smanji neki fajl od 100MB, postojace fajl od 100MB koji ce se povecati zahvaljujuci kompresiji.

Jedna mala napomena:
U dokazu si mogao da vidis da nema dovoljno nizova duzine n - 1 ili manje za "registrovanje" nizova duzine n. Obrati paznju na to sta se onda desava sa nizovima duzine n + 1 i da ne postoji nacin da se svi oni registruju nizovima duzine n ili manje, a kamoli ako uzmemo u obzir da smo nizove krace od n bita vec iskoristili za "registrovanje" (i to ne svih) nizova duzine n. Sada obrati paznju na nizove duzine n + 2, n + 3...


[Ovu poruku je menjao formeye dana 19.01.2006. u 00:03 GMT+1]
[ formeye @ 18.01.2006. 23:03 ] @
Jedan mali savet. Umesto da branis svoju kompresiju, pokusaj da razmislis na koji nacin mozes da pokazes da ne valja. Tek kad si siguran da ti nisi u stanju da oboris svoju teoriju, tak je tada baci lavovima. :)

Malo čan budističkog pristupa nije na odmet.

[Ovu poruku je menjao formeye dana 19.01.2006. u 00:06 GMT+1]

[Ovu poruku je menjao Gojko Vujovic dana 22.01.2006. u 13:10 GMT+1]
[ bojan_bozovic @ 19.01.2006. 00:46 ] @
Citat:
Kompresija random-like podataka bi se vrsila na sledeci nacin: ako imamo fajl (koji hocemo da kompresujemo) duzine n bita I ako napravimo brojac takodje duzine n, koji broji od 0 do 2^n -1 nas fajl bi se nasao na tom brojacu na poziciji m (obzirom da su iste duzine fajl I brojac). Zapis (n,m) bi bio nas kompresovani fajl.
Dekompresija bi se vrsila na sledeci nacin: iz kompresovanog fajla bi procitali n I napravili brojac duzine n. Zatim bi procitali m, pustili brojac u rad I zaustavili kod m-tog fajla po redu. Stanje na brojacu u tom trenutku bi bio nas originalni fajl.
Da bi postojala kompresija m bi moralo biti izrazeno (I zapisano) kao a^b +x tj. a^b + c^d – e^f + .. +x^y + z tj. zbirom koeficijenata I drugih brojeva osim 2, na najoptimalniji (najkraci) nacin. Tacna vrednost tog izraza bi se izracunavala tek prilikom dekompresije.
Prilikom kompresije ne bi bilo neophodno (a ni pozeljno) pravljenje brojaca. M se da izracunati na osnovu “tezinskih” koeficijenata direktno iz originalnog fajla. Na primer za fajl 0101 m je : 0*2^3 + 1*2^2 + 0*2^1 + 1*2^0 = 5.


recimo 2^32 bita i brojac 2^31 bit treba ti dakle po tvome 2^31 za brojac i 2^31 za poziciju. ;-) Sta je 2^31+2^31? ;-)
[ Srđan Krstić @ 19.01.2006. 16:30 ] @
Citat:
A ako 32 bitna mesta iskoristim da zapisem npr. Koeficijent 9^99 I onda pustim da ga engine procita tj. protumaci. tj. izracuna dobija se daleko veci broj nivoa razlikovanja rednog broja pojavljivanja fajla na brojacu.

NE!
Po 0xFFFFFF-ti put: sa 32 bitna mesta mozes da predstavis SAMO 2^32 razlicita broja... Nema tu nikakvih nivelacija niti koeficijenata niti bilo cega. Postoje 2^32 razlicite kombinacije sa 32 bita i to je ultimate truth, a ako bi na BILO KOJI NACIN (koeficijenti ili stogod) uspeo da predstavis vise od toga to bi znacilo, po Dirichlet-ovom principu (ili pigeon-hole, ako ti volja), da bar dva broja predstavljas istom sekvencom bitova, i samim tim, tvoj fajl postaje nemoguc za desifrovanje. A to sto ti mozes sa dva bita da predstavis ne 9^99, nego 65535^65535, to ne znaci NISTA, jer to sto mozes da predstavis neki tamo mnogo veliki broj APSOLUTNO nikako ne ukazuje da mozes da predstavis sve brojeve manje od njega. Kardinalnost skupa brojeva koje ti mozes da predstavis sa 32 bita je 2^32, voleo ti to ili ne, bili oni uzastopni ili ne.

I opet, po 0xFFFFFF-ti put, MOLIM TE pokusaj da iskodiras to sto pricas.... Ukoliko stvarno imas toliko interesovanja za cs, a ocigledno da imas kad posle OVOLIKO vremena i ne pomisljas da odustajes, ako nesto vredi nauciti to je da programiras. Posto od tvoje kompresije, brat bratu, nema nista, zasto da bar nesto dobro ne izadje iz svega ovoga?! A niko, ali NIKO nece da isprogramira ovo za tebe, jer:

1. glupo je programirati nesto TOTALNO uzalud
2. ruku na srce, malo je nervirajuce sto toliko kukas svakodnevno, uz to ignorises to sto ti je slovima SVAKO dokazao na najraznoraznije nacine da je tvoja komresija daleko nemoguca, a za ovo vreme si mogao da to isprogramiras zilion puta, pa taman da nisi seo za tastaturu nikad u zivotu!

Zato eto najsrdacnijeg saveta: sedi da to isprogramiras, gde god da zapnes pomocice ti ljudi sa foruma, pa kolko god vremena i zivaca izgubio naucices mnogo toga SIGURNO. A posto volis da motivises ljude, evo, ako ti sednes i sam to isprogramiras, dobijes od mene i gajbu piva, i cvarke, i sve moguce sestre, necake, tetke, babe, ma sta god pozelis ;-)

Pozdrav i puno srece u ucenju programiranja!
[ bojan_bozovic @ 20.01.2006. 12:54 ] @
@MajorFatal

Da 1000puta bi implementirao ovo u bilo kom programskom jeziku do sada. Malo da ti pojasnim Formeye-ov dokaz:

Neka imas 2 skupa podataka A i B - gde ti je A ulaz za kompresiju a B izlaz, kompresiju imas samo ako je funkcija f:A->B (f koja slika A u B) bijekcija tj. postoji fukcija g:B->A tako da vredi g(f(a))=a za svako a iz A (inverzna funkcija) inace nemas dekompresiju.

Da vidimo tvoj slucaj (kardinalni broj skupa A je broj elemenata skupa za konacan skup, za beskonacan skup nije, ali nam ovde to ne treba) - imas 2 skupa koja nemaju isti broj elemenata tj. card(A)/=card(B) (u pitanju su konacni skupovi A,B)
Ajde da dokazemo da ne postoji funkcija f u tom slucaju da je bijekcija? Tj. da ili skup A ili skup B ne moze da se preslikava u drugi uz inverznu funkciju (onu koja ti dekompresuje?)

Neka je card(A)/=card(B) i A,B su konacni skupovi i f funkcija f:A->B (slika A u B) ako je card(A)>card(B) postoji makar jedno a iz A koje se ne slika u b iz B tako da je a1=a2 -> f(a1)=f(a2) a ako je card(A)<card(B) postoji makar jedno b iz B koje se ne slika u a iz A i b1=b2 -> g(b1)=g(b2), inace bi imali isti broj elemenata (za konacne skupove). Zasto je ovaj drugi uslov nuzan? 1-1 ili injektivna funkcija? Neka je a1/=a2 i f(a1)=f(a2) tj imamo a1,a2 iz A koji se slikaju u isto b iz B i ne mozemo imati inverznu f-ju g:B->A. Za beskonacni skup je card(A)=card(B) ako i samo ako postoji bijekcija f:A->B ili sto je isto bijekcihja g:B->A jer onda je f(g(b))=b za svako b iz B i f:A->B ;-)




[Ovu poruku je menjao bojan_bozovic dana 20.01.2006. u 14:13 GMT+1]

[Ovu poruku je menjao bojan_bozovic dana 20.01.2006. u 14:14 GMT+1]
[ MilosSavic @ 21.01.2006. 12:50 ] @

Racunarstvo je jedna divna nauka, tako lepa u svojim metodama koje cine da nus produkti nasih istrazivackih pokusaja budu vise od pukih statistika a manje od mnogostrukih interpretacija koje nastaju uploadovanjem licnog, logalnog ili globalnog iskustva/konsenzusa u te nus produkte na nizem nivou (primetiti da je pogled na nivoe rekurzivan, najnizi nivo, tj. onaj na kome rekurzija pocinje da se zamotava jeste statistika). Nus produkti racunarskog naucnoga rada su algoritmi ili njihove konkretne realizacije programi ali na nivou dinamike tj. izvrsavanja istih.. Nus produkti cine da racunarstvo bude malkice vise od nauke, da bude umetnost u rangu muzike ili slikarstva posmatrajuci razgradnju i prosirivanje intuicije stvaraoca (mada neki programi pisani u malko avangardnijim jezicima koji prate malkice neintuitivne paradigme mogu imati i estetske lepote, posebno kada program dozivljavate u fuziji statike zapisa i dinamike izvrsavanja, ali kada dinamika daje dubinu, lepotu i drugaciji dozivljaj statike... obicno inverzna postava jeste nase intuitivno poimanje racunarskog programa, jedan materijalisticki pogled gde se zarad dinamike steti na statici programa koji joj daje estetske vrednosti), ali i da dalje ostane totalitarno DETERMINISTICKA... Tu smo, kljucna rec za sada DETERMINISTICKA, sto za one koji nisu u savremenim tokovima racunarstva znaci: ako imas algoritam A i u njega ubacis konkretan input i, uvek dobijes konkretan i isti output o, ali uvek, bez izuzetaka, u najsirem smislu te reci... I nijedna druga nauka sem racunarstva nije tako dobro i u tom pogledu totalno deterministicka, sto je ujedno i njena najveca prednost u odnosu na druge nauke, posebno fiziku i "kvazi-nauku" matematiku... Ok, zastanimo za trenutak...
Zivimo u svetu koji nam posredstvom sebe predoci razne probleme. Opet u zavisnosti od konkretnog istorijskog konteksta socijalni konsenzus nekada kaze da je svrha naseg postojanja upravo u resavanju problema. Buduci da trenutno zivimo u drustvu koje se po sociolozima zove informaticko drustvo, a trenutno vreme informaticka era, mozemo reci da je socijalni konsenzus postignut, i to na zalost nas samih racunardzija (jer pocinjemo vise da se bavimo onim pomenutim materijalnim programiranjem na ustrb onog pravog umetnickog, sto bi Puza rekao onog pre Hrista) i ponekih ostataka romanticarskih dusa. Super na relaciji problem-resenje prvi korak jeste ideja. Koliko i problema, toliko i ideja po problemu, a resenja i modela obrnuto proporcionalno *sto bi trebalo da znaci da sve u svemu to tezi nuli*. E tu je problem, ideja koliko god hoces a nauka deterministicka, a mi u zabludi i mislimo da imamo savrsenu detereministicku intuiciju, te da nam ideje manje vise pa uvek rade. Nekima se to desi na prvoj ideji, nekima na svakoj. Mislimo da nam je racunarska intuicija dovoljno izgradjena da mozemo predvideti rezulat algoritma na input na osnovu samog statickog pogleda na njega u malo losijem slucaju, a u najgorem da je logicka struktura naseg algoritma takva da odgovara resenju naseg problema prateci odgovarajucu filozofiju algoritma kao pojave. Treci i poseban problem jeste to sto mozemo da biramo izmedju losijeg i najgoreg slucaja, mada to ne bi smeli/trebali ciniti (mada po kongitivnim sposobnostima i energetskim kapacitetima, tesko da mozemo isterati oba puta kao valja bez potpunog socijalnog odricanja). Prednost je opet sto je nauka u domenu interpretacije totalno DETERMINISTICKA, te onda bez problema SAMI mozemo graditi i doizgradjiati nasu racunarsko umetnicku intuiciju, bilo kroz formalno matematicko dokazivanje korektnosti algoritma, bilo kroz njegovu samu implementaciju kao dokaz konceptu, i to mnogo brze, bolje i bezbolnije nego kod drugih prirodno-pozitivistickih nauka. Zato, apel, prestanite vise da se*ete i umesto toga razvijajte vasu racunarsku intuiciju, bilo formalno, bilo implementaciono, bilo oboje, ali nikako socijalno na ovom nivou, da bi ste kada je izgradite do potrebnog nivoa mogli je doizgradjivati i socijalno-hegelovski... Tek onda se pojavite na nekom forumu i ke*ate kao toboze neko pametan koji sve svoje komplekse leci kroz odrzavanje kompleksa vise vrednosti, te stoga bar dva pojedinca na ovom forumu su u ovom trenutku doziveli svojih vorholovskih pet minuta slave na ovom massmedia prostoru i tih pet minuta je proslo i ne ponovilo se... Sve ostalo jednostavno nije vredno truda ni jednog bajta
[ MilosSavic @ 21.01.2006. 13:20 ] @

A sada sam uspeo i da procitam najvece rangiranu glupost u ovom topicu:

"Ne moram da podsecam da racunari rade na osnovu matematickog modela i da, samim tim, taj model savrseno odgovara realnosti, za razliku od stvari koje srecemo u fizici koja je samo priblizni matematicki model realnosti."

Racunari ne rade na osnovu matematickog modela, racunar jeste konkretna realizacija jednog matematickog modela. Taj matematicki model daleko da odgovara bilo kakvoj realnosti (mada mislim da se u ovom slucaju pod pojmom realnosti mislilo na nesto sto svakako nije semanticko znacenje ove reci). Stvari koje srecemo u fizici nisu priblizni matematicki modeli realnosti, nego je realnost realnost, a modeli u fizici su posledica matematickog modeliranja te realnosti, znaci potpuno obrnut pristup problematici. Ako si instrumentalista realnost te ne interesuje i u neku ruku je negiras, interesuje te samo da li tvoj model predvidja ishod eksperimenta sto kasnije egzaktno proveravas i onda kazes ok model radi ili ok model ne radi. Ako radi onda se igras sa njim menjajuci neki od parametara modela da vidis kako bi se realnost ponasala u tim slucajevima... Ukoliko si realista i imas model koji radi posao onda si dosao do apsolutne istine, ukoliko je model matematicko-deterministicki mozes se igrati i boga tako sto ces ga racunarski simulirati. Medjutim daleko smo mi od apsolutnih istina i toga da matematicki model racunara savrseno odgovara realnosti (a to je upravo tvoja tvrdnja), jer da je tako ziveti danas ne bi bilo nikako zanimljivo...
[ formeye @ 21.01.2006. 13:35 ] @
Citat:
... Racunari ne rade na osnovu matematickog modela, racunar jeste konkretna realizacija jednog matematickog modela. ...

Nije šija, nego ... šija?

Obožavam filozofe. Raspiseš se toliko, a ne kažeš apsolutno ništa. Svaka čast!

Računar *radi* po matematičkom modelu. Ako dokažeš (ne)ispravnost algoritma u matematičkoj teoriji, algoritam (ne)će raditi u realnosti. Ako dokažeš nemogućnost postojanja određenog algoritma u matematičkom modelu, algoritam neće biti moguće konstruisati ni u realnosti.

Za razliku od života, za koji možimo diskutovati da li je deterministički ili ne (a što nikad nećemo moći da dokažemo), u računarstvu su stvari malo drugačije.

P. S. Malo si off-topic...

[Ovu poruku je menjao formeye dana 21.01.2006. u 15:27 GMT+1]
[ RooTeR @ 21.01.2006. 15:37 ] @
Citat:
formeye:
Obožavam filozofe. Raspiseš se toliko, a ne kažeš apsolutno ništa. Svaka čast!


Jedan je Milos Savic (ovo treba da zvuchi, onako, navijachki:)
[ bojan_bozovic @ 21.01.2006. 17:54 ] @
Citat:
Racunarstvo je jedna divna nauka, tako lepa u svojim metodama koje cine da nus produkti nasih istrazivackih pokusaja budu vise od pukih statistika a manje od mnogostrukih interpretacija koje nastaju uploadovanjem licnog, logalnog ili globalnog iskustva/konsenzusa u te nus produkte na nizem nivou (primetiti da je pogled na nivoe rekurzivan, najnizi nivo, tj. onaj na kome rekurzija pocinje da se zamotava jeste statistika). Nus produkti racunarskog naucnoga rada su algoritmi ili njihove konkretne realizacije programi ali na nivou dinamike tj. izvrsavanja istih.. Nus produkti cine da racunarstvo bude malkice vise od nauke, da bude umetnost u rangu muzike ili slikarstva posmatrajuci razgradnju i prosirivanje intuicije stvaraoca (mada neki programi pisani u malko avangardnijim jezicima koji prate malkice neintuitivne paradigme mogu imati i estetske lepote, posebno kada program dozivljavate u fuziji statike zapisa i dinamike izvrsavanja, ali kada dinamika daje dubinu, lepotu i drugaciji dozivljaj statike... obicno inverzna postava jeste nase intuitivno poimanje racunarskog programa, jedan materijalisticki pogled gde se zarad dinamike steti na statici programa koji joj daje estetske vrednosti), ali i da dalje ostane totalitarno DETERMINISTICKA...


U bre, deterministicka je zato sto je logika u kompjuteru Hilbertova logika, a brojevi u kompjuteru matematicki brojevi (prirodni su dosta) i iz toga izgradjujes celo programiranje i celu matematiku, odnosno, moze se uvek logicki dokazati da su algoritmi u matematici i programi u kompjuteru, ako ne isti ono izomorfni tj da pojasnim laicki, samo drugaciji zapis iste stvari. Ako je neki problem matematicki resiv uvek mozes konstruisati program na osnovu algoritma koji ce ga resavati, i ako je matematicki neresiv ne mozes konstruisati program koji bi ga resio. Evo dokaza: Neka je matematicki problem M neresiv, a mozes napisati program koji ga resava imas kontradikciju, jere na osnovu programa P imas algoritam (matematicki) za resavanje problema M. To drugacije zapisivanje iste stvari tj izomorfizam, posledica je identicnog aksiomatskog skupa u programiranju i matematici. Racionalni brojevi u matematici i u programiranju su isti zapis jedne stvari (koju ako zelis mozes da zapisujes kako hoces, ukljucujuci i razlomke sa rimskim brojevima, i heksadekadnim razlomcima). Logika u matematici je ista i u kompjuteru, samo je zapis drugaciji, i to vazi za sve sto se moze implementirati i u matematici i u programiranju i logicki dokazati.
[ MilosSavic @ 22.01.2006. 10:31 ] @

Nije sija nego nije sija...
Pazi ovako: imas racunar, ne znas kako radi, proucavas ga bilo kako ali da je bilo kako nesto sto je po socijalnom konsenzusu opet nesto sto se zove naucni metod i zakljucis da racunar radi po matematickom modelu koji je posledica tvog istrazivanja.. E onda mozes da kazes racunar radi po matematickom modelu.. Ali situacija je malko drugacija imas matematicki model koji se zove Tjuringova masina (a ne nesto iz Hilbertove logike, mada za istu nikada nisam cuo, iako dobro znam i sta je to logika i ko je to Hilbert, no dobro) i onda na osnovu toga nastane njegova materijalno prostorno vremenska realizacija koja se zove racunar i ona ne radi po matematickom modelu, nego je konkretna realizacija matematickog modela sto je veoma bitna razlika... I ne zaboravi kojim sledom umnih padavina ide tvoje izlaganje: prvo kazes racunar radi po matematickom modelu, a onda kazes da taj model savrseno odgovara realnosti, sto je besmislica a sto sam pokusao da kazem, ali si ti u svom odgovoru izbegao ovu drugu stvar (kao i celu stvar oko fizike za koju imas potpuno pogresnu predstavu). Poenta je bila na relaciji realnost-model, gde ti kazes ili imas takvu predstavu da se ide od modela ka realnosti umesto obrnuto, a na sta sam ja pokusao i da ukazem...
Filozof?!?!?!
DA jesam off topic, i u tom kontekstu je pisan i ceo tekst, uostalom nista vise off topic nego vecina odgovora ovde...
Daj molim te pojasni mi sta je to algoritam u realnosti, a sta je to algoritam u matematickoj teoriji... Algoritam ne egzistira u realnosti, algoritam jeste matematicki model i samo matematicki model i nista drugo i nista vise. Da li je algoritam nesto vise od matematickog modela ne znamo iliti socijalni konsenzus po tom pitanju jos nije dostignut, jer nista konkretno ne postoji sto bi se moglo nazvati algoritam a da nije matematicki model, kada se to nesto pojavi i kada budu postojale arhitekture na cemu ce se to moci izvrsavati onda mozemo reci da je algoritam nesto vise...
Poslednji tvoj pasus je off topic na ovu temu, ali se sa njim slazem dokle god je racunarstvo ovakvo kakvo je. Uostalom taj pasus direktno obara sve ono sto si ti u prethodnim postovima i rekao, a na sto sam ja ukazao.

E sada za drugog pacijenta:
Govorio sam o razvoju intuicije stvaraoca umetnika i hteo sam da kazem zasto je racunarstvo tako dobro sa te strane i u tom kontekstu je upotrebljeno to DETERMINISTICKO, ja uopste nisam ulazio u to zasto je ona deterministicka, samo sam objasnio sta je to i zasto je dobro kada je tako.... A ono sto si ti pisao nema veze sa vezom o onome sto sam ja hteo da kazem i tvoj tekst uglavnom predstavlja sintaksno spojenu gramaticko tacnu kombinaciju strucnih izraza u iskaz koji nema nikakvo ali ama bas nikakvo semanticko znacenje, jer ti i ne znas o cemu pises. Prvo, u tvom transferu iz naucnog u laicki govor (ali u onom naucnom) upotrebljavas fraze kao sto su: "logika u kompjuteru", "brojevi u kompjuteru", "implementirati u matematici" strasno :)... Posto sam jelte off topic strasno bih voleo da znam sta je to: Hilbertova logika, potom sta je to logika u kompjuteru, potom da li postoje brojevi koji nisu matematicki, zatim da li se moze dokazati da je algoritam izomorfan sa programom ili se to moze uvek dokazati (kao da postoji vise vrsta pojma algoritam i vise vrsta pojma program). Druga stvar, mislim i da postoje problemi koji su resivi i za koje se mogu pokazati da su resivi, a da ne postoji algoritam za njihovo resavanje jer do sada nije pronadjen. Zatim bih voleo da mi se pojasni sta je to aksiomatski skup u u programiranju i ako je moguce da mi se navedu aksiome iz tog skupa. Zatim tvoj dokaz uopste nije dokaz i uopste i nije tacan... I ne postoji dokaz za izomorfizam pojma algoritam iz matematicke teorije i pojma program u racunarstvu, zasto, zato sto nije ni potreban jer ono drugo nastaje iz onog prvog, zatim su to stvari koje se manje vise intuitivno usvajaju jer matematicari ne mogu da postignu konsenzus oko toga sta je to algoritam i sta je to efektivan postupak. Druga stvar ne mozes tek tako skakati sa nivoa na nivo i govoriti o necemu sto je zapis broja i necemu sto je zapis algoritma jer svakako ta dva pojma nisu u istom domenu, mada je ovaj drugi moguce svesti na ovaj prvi. Uostalom zapis tu i ne igra nekavu veliku ulogu. I na kraju sto je najgore, ja se u potpunosti slazem sa tobom, jer znam sta si hteo da kazes (ali opet ponavljam da to sto si rekao nema nikakvo znacenje), ali to nema ama bas nikakve veze sa onim sto sam ja hteo da kazem.
E sada za onoga prvog pacijenta: ako si mislio da sam ja filozof i demagog obrati paznju na ovog drugog pacijenta... I sta se bre primate toliko :)

[ formeye @ 22.01.2006. 20:13 ] @
Citat:
MilosSavic: E sada za drugog pacijenta:

Pre svega, ovo dovoljno govori o tvojim intelektualnim (ne)sposobnostima i (ne)kulturi, tako da cu se potruditi da ovo sto zelim da kazem, srocim sto je moguce jednostavnije.

Citat:
MilosSavic:
da racunar radi po matematickom modelu koji je posledica tvog istrazivanja.. E onda mozes da kazes racunar radi po matematickom modelu.. Ali situacija je malko drugacija imas matematicki model koji se zove Tjuringova masina (a ne nesto iz Hilbertove

Racunar je pravljen po matematickom modelu, i samim tim radi po matematickom modelu.
Racunar radi po matematickom modelu, i samim tim model odgovara realnosti.

P.S. O "primanju": Uporedi duzinu svojih tekstova sa zajednickom duzinom mene i 2. kolege, pa primeti ko se prima, a ko ne, ja samo uzivam da se raspravljam... Pozdrav.
P.P.S. Ako imas zelje da nastavis raspravu, molim te pokreni drugu temu i ostavi nam link, a ovde da se vratimo "Kompresiji random-like podataka"
[ MilosSavic @ 22.01.2006. 21:16 ] @


Ha, super :)

Ako je racunar pravljen po matematickom modelu i ako samim tim racunar radi po matematickom modelu i pri tome znacenje glagola raditi poistovecujes sa znacenjem glagola biti konkretna materijalna prostorno vremenska realizacija, onda je recenica koja kaze da taj model odgovara realnosti, ako pod realnoscu kao imenicom podrazumevas samo racunar i nista vise, VISAK i uopste je nije potrebno naglasavati jer tako dobijas nesto sto se zove petlja iliti od "nije sija..." napravis "nije sija nego vrat" program koji stampa sam sebe a sto je sa stanovista teorije informacija nesto sto je mnogo prostorno slozenije i vremenski zahtevnije od "nije sija nego vrat", a cela stvar je u stvari samo "nije sija..."
Druga stvar jeste da stvari opet pokusavas da izvuces iz konteksta. Tvoj sled umnih padavina je sada u potpuno drugom kontekstu nego u onom iz onoga posta...
Trece implikacije su stvarno lepe stvari ali kada ih izvuces iz vremenskog konteksta, a ovde ga svakako ima: prvo model pa onda racunar....
I cetvrto realnost nisu racunari, nego je opet ponavljam realnost realnost a to se ne moze modelirati TJURINGOVOM masinom iliti onome sto po tebi radi po Tjuringovoj masini, ali evo vidis to "ne radi po Tjuringovoj masini" nego je to konkretna prostorno vremenska materijalna realizacija Tjuringove masine, stoga treba biti malkice precizniji kada se upotrebljava taj pojam realnosti.
Peta stvar: i ta dve implikacije iz p sledi q i iz q sledi p nisu tacne, zasto, zato sto Tjuringova masina ima nesto sto se zove beskonacna traka, a svi dobro znamo da je memorija racunara konacno limitirana. Sto znaci da iz p sledi q ali da iz q ne sledi p, toliko o relacijama od realnosti do matematickog modela za koji uopste nemas izgradjen bilo kakav senzibilitet. Znaci i pored svih jezickih zavrzlama opet nisi u pravu.
Sesta stvar: a to je ona najbolja, jeste da ako iz p sledi q, ne mora da znaci, a najcesce i nije tako da iz q sledi p. Problem je u tome sto je p = q i to je ONO STO JA PRICAM, a onda je tacno i ONO STO TI PRICAS. Znaci da li ti je lepse ako ja kazem da je "p = q" ili da je "iz p sledi q onda iz q sledi p". "iz p sledi q onda iz q sledi p" je tacno ako je "p = q"... Ja sve vreme pricam o "p = q" a ti sve vreme o "iz p sledi q onda iz q sledi p" (ali pazi, ti ne pricas ovako: "iz p sledi q I (i kao operator) iz q sledi p", sto je p = q, upravo zbog onog vremenskog konteksta koji sam pominjao, prvo model, pa onda racunar) sto je tacno samo ukoliko je ono sto ja kazem tacno. Ali je onda sto ti kazes potpuno nebitno, jer pod a) nije opstije pod b) nije krace od onoga sto ja kazem i pod c) nije tacno ukoliko ja ne kazem svoju recenicu... Eto vidis koliko meni treba bajtova da tebi jednom intelektualno sposobnom objasnim jednu veoma prostu stvar... Algoritamska teorija informacija kaze da ne moze krace imajuci u vidu paramtere ovog algoritma objasnjavanja koji ima bar dva :)

Pazi posto sam filozof i racunarima sa bavim samo teorijski i filozofski i nemam nikakvih prakticnih racunarskih sposobnosti, imam tu carobnu sposobnost da velikom brzinom kucam koristeci se tastaturom, tako da moje ruke mogu da isprate tok mojih misli. Toliko o duzini tekstova. Duzina tekstova nema nikakve veze sa kolicinom primanja. Posto neki ljudi imaju nesto da kazu, a neki koji nemaju nista, misle da oni koji imaju nesto da kazu, pa cak bilo to i filozofski, mlate praznu slamu i da se primaju. E sada sta ovi koji imaju nesto da kazu misle o onima koji nemaju sta da kazu, oni misle da samim tim sto je neko rekao da su srali nesto sto je reda velicine kilobajta i da neko drugi kaze da on time nije rekao nista, moze da znaci samo dve stvari: taj ili nije shvatio ili je to pogresno. Buduci da jos nisam dobio nikakvu argumentaciju o pogresnoj filozofiji koja nikako ne pretenduje da bude apsolut mogu da zakljucim samo ono prvo.

Priznajem da imam ogranicene intelektualne sposobnosti kao i taj koji je izneo tvrdnju o mojim intelektualnim nesposobnostima. I gde bas od ovolikog silnog raspisivanja tebi samo to bode oci. I gde samo na osnovu toga mozes zakljuciti o mojim kongitivnim sposobnostima. Mozda je to bila samo mala sitna provokacija da se vidi kao ce taj kome je upucena da reaguje ili uopste ne reaguje. Buduci da smo na forumima i da se ne poznajemo, a da ja sve svoje drugare za koje ne znam ni ko su ni sta su, zovem pacijenti, to ne bi trebala biti uvreda, ukoliko ti to tako dozivljavas IZVINI. Problem je u tome sto je pod tim pojmom postignut socijalni konsenzus koji kaze da je reci nekome pacijent nesto pogrdno. E pa u mom univerzumu to nije tako. Da li su mi sada intelektualne (ne)sposobnosti manje ili vece? Kulturan svakako nisam u najsirem znacenju te reci, pobogu tek sam na samom pocetku trece decenije zivota gde se ono biti kulturan socijalno i ne kotira bas najbolje. Zatim moje intelektualne sposobnosti i kultura uopste ne uticu na to da li ti meni zelis da kazes nesto u manje bajtova. Onda si ti nekulturan jer na jedan kulturno zavijen nekulturan nacin opstis sa nekulturnim i na jedan nacin gledas me sa visine, jer pobogu ti si kulturan a ja nisam. Uostalom, istorija nas uci da i ponizavati nekoga mozda znaci i vise ga voleti od nekog treceg ko ga ne ponizava. Manje boli reci nekome skini se i idi citaj knjigu a onda dodji da socijalno razvijas svoju intuiciju nego mu praznim pricama u MB otvarati oci (mada ja to uporno radim, jel se ili izgleda primam ili ne volim ljude koji misle da time sto im kazem da su pacijenti misle da je to nesto pogrdno).

Da se vratite CEMU? Iliti jos bolje pitanje KOME? (e sada ce neko da kaze da nisam intelektualno sposoban i nekulturan)

P.S A da tek znas kako ja uzivam da se raspravljam, cudo jedno...
P.S.2 A ako ti se ne svidja a ti obrisi, ali prvo pusti da svi procitaju, da ne bude da ona druga strana nije imala sta da kaze. Mada ako to obrises to ce biti najkrace kazivan odgovor ikada, cemu verovatno svi ovde i na ovom forumu treba da tezimo, ne bi li negativno narusili energetsko-umne potencijale ove planete

[ bojan_bozovic @ 22.01.2006. 21:30 ] @
@milos savic

Hilbertova je tradicionalna logika, jer kao jedna algebra, mozes da je definises kako hoces.

Imas odredjeni aksiomatski skup u matematici koji sluzi za definisanje bas svega - koriscenjem formalne logike i samo tih aksioma - kako su te aksiome iste i u programiranju a ista je i logika dolazis uvek do istih zakljucaka. BTW kakve veze ima Turingova masina sa ovim ;-)

Evo ti dokaza:

neka imamo algebarsku strukturu A operacije na njoj (o...on) i relacije na njoj ([=...[=n) i algebarsku strukturu B sa operacijama O1...On i {=..{=n.

A je izomorfno B ako i samo ako postoji bijektivna f-ja F:A->B da vredi

a1[=a2 onda i samo onda ako je F(a1){=F(a2)
a1oa2 <=> F(a1)OF(a2)

gde je [= relacija na skupu A a {= relacija na skupu B
a o operacija na skupu A i O operacija na skupu B

za svaku operaciju o...on i relaciju [=...[=n

;-)

Dakle da vidimo, pretpostavimo da je problem P neresiv tj preslikavanje P:A->A1<=A (A1 podskup A) ne postoji, da je A izomorfno B i da operacije o...on ukljucuju i algebru logike na A, tj O...On algebru logike na B, tj uz koriscenje operacija i relacija na algebri A ne moze da se dodje do resenja u obliku kompozicije ;-) (npr. racunanje pi sa konacno mnogo decimala ;-)) a pretpostavimo da je resiv u algebri B ;-) operacijama O..On i relacijama {=..{=n i A je izomorfno B onda bijekcija F-1:B->A u svakom koraku dovodi do resenja u A jer su operacije i relacije sacuvane, tj. u svakom koraku je F-1(b1)OF-1(b2)=a1oa2 i F-1(b1){=F-1(b2)=a1[=a2, s tim sto, kako ispada, koraka moze da bude najvise prebrojivo mnogo ;-) Da ti uzmes jedan udzbenike iz analize i algebre ;-) E da, ovo jeste dobar dokaz (trivijalan je!) mozda bih mogao da reaktiviram svoj indeks matematickog fakulteta koji mi skuplja prasinu godinama ;-)

S tim sto je i P operacija na A pa mora da vredi F(a1Pa2)=b1Rb2 za svako a iz a a R je upravo kompozicija O..On, {=...{n iz B jer inace imamo kontradikciju, pa ne moze da slika B u B1<=B ;-). Nego, ti da mi odgovoris, kada operacija o...on moze da bude prebrojivo mnogo ;-)

[Ovu poruku je menjao bojan_bozovic dana 22.01.2006. u 22:55 GMT+1]
[ formeye @ 22.01.2006. 23:11 ] @
1. Implikacije nemaju veze sa vremenskim kontekstom. U recenici "racunar radi po matematickom modelu" nigde nije spomenuto sta je doslo pre. Slazem se da je u tom postu bilo viska informacija, to jest naglasavanja - istu stvar sam rekao na bar 2 razlicita nacina (ne shvatam kako je to tebi zasmetalo), ali ni u jednom trenutku nisam rekao neistinu.
2. i 3. Problem sa kontekstom je da postoji "tvoj kontekst" i "moj kontekst". Mozda sam izvukao svoje recenice iz tvog, ali iz mog nisam. Ako "citas izmedju redova" u mom tekstu, ne pozivaj se na to sto si ti shvatio da pise.
4. Realnost je realnost - Zemlja je geoidnog oblika?
Ako tvrdis da se realnost ne moze opisati Tjuringovom masinom, dokazi. (da ne budem pogresno shvacen, NE tvrdim da se moze opisati nego, jednostavno, znam da je i jedno i drugo tvrdjenje nemoguce dokazati)
5. Gde sam ja spomenuo Tjuringa (osim kad sam tebe citirao)? U ovu raspravu je Tjuring dosao u tvom postu tvrdnjama da su racunari "konkretna materijalna prostorno vremenska realizacija" Tjuringove masine. Ja spominjem iskljucivo "matematicki model". ("tvoj kontekst" i "moj kontekst")

Mislim da si ovde iskljucio numeraciju :)

Kao can budista, smatram da je umetnost reci sve u sto manje reci, jer bespotrebno trosenje reci samo razvodnjava ideju i poentu teksta.

Primam izvinjenje, a ja se izvinjavam zbog provokacije.

Sto se tice "tvog univerzuma" i toga da ti ne smatras da je nesto uvreda, postoji jedan mali problem - ovde nisi u tvom univerzumu, kao sto ja nisam u svom, nego smo u ES univerzumu. "Kad si u Rimu, ponašaj se kao Rimljanin"

Citat:
Onda si ti nekulturan jer na jedan kulturno zavijen nekulturan nacin opstis sa nekulturnim i na jedan nacin gledas me sa visine, jer pobogu ti si kulturan a ja nisam.

Ovo nije nekultura sa moje strane, nego samoljublje, arogancija, egoizam, egot(e)izam... :)

P.S. Sto jes, jes, sad je i kasno vracati se na temu. (Izvini MajorFatal)
P.P.S. Nikad nisam bio za brisanje postova.
P.P.P.S. A i nisam moderator
P.P.P.P.S. Godine nisu opravdanje za nekulturu. (nisi mnogo mladji od mene, ako si uopste)
P.P.P.P.P.S. Ovaj poslednji P...S. je tek da razbije monotoniju i da podseti na odlomak iz knjige Gospodar Prstenova (John Ronald Reuel Tolkien)

[Ovu poruku je menjao formeye dana 23.01.2006. u 00:23 GMT+1]
[ MilosSavic @ 23.01.2006. 14:38 ] @

Evo iskoristicu svoju zadnju priliku da lupnem jos po nesto i obecavam necu vise, bar u skorije vreme... Hvala Rajko na savetima ali to jednostavno nece moci, ovo drugo svakako, za otprilike jedno desetak minuta.

Vreme je da se polako privodi kraju i da se konacno stigne do poente...

Ajde prvo da se podsetimo sta to bese ljubav. Orginalan tekst je glasio:

"Ne moram da podsecam da racunari rade na osnovu matematickog modela i da, samim tim, taj model savrseno odgovara realnosti, za razliku od stvari koje srecemo u fizici koja je samo priblizni matematicki model realnosti."

Ono sto sam pokusao da ukazem u postu u kojem sam citirao ovo jeste da ti fiziku kao nauku, kao proces, dozivljavas pogresno, tj. od modela ka realnosti umesto suprotno, a da to sto racunarstvo "radi po matematickom modelu" savrseno odgovara realnosti UOPSTE NIJE TACNO ukoliko ta realnost nije sam RACUNAR. Medjutim realnost nije RACUNAR, realnost je "realnost - Zemlja je geoidnog
oblika?". Onda ti treba da pokazes da taj model savrseno odgovara realnosti jer ti iznosis tvrdnju, a ne ja, dokazi su na onome ko iznosi tezu a ne onome ko iznosi antitezu. Slazem se da je nemoguce dokazati to sto tvrdis uostalom i rekao sam da sa tog stanovista postoje instrumentalisti i realisti i ako se i ti slazes (a slazes se) to samo i opet samo znaci da matematicki model racunara ne moze savrseno odgovarati realnosti jer je to nemoguce dokazati *opet ukoliko ta realnost nije racunar a o tome kasnije jer je onda to besmislica* Drugo, hocu da kazem da moras biti veoma obazriv kada koristis rec realnost, posebno kada je u isti
kos strpana i fizika. A ukoliko je realnost RACUNAR onda je tvrdnja "racunar radi po
matematickom modelu i taj model savrseno odgovara realnosti" u stvari tvrdnja "racunar radi kao racunar" sto je besmislica.
E onda dolazimo na ono cuveno "Racunar radi po matematickom modelu""... E onda ja kazem RACUNAR NE RADI PO MATEMATICKOM MODELU, RACUNAR JESTE KONKRETNA PROSTORNO VREMENSKA REALIZACIJA MATEMATICKOG MODELA KOJI IMA SVOJE IME(TJURINGOVA MASINA) I KOJI JE FORMALNO MATEMATICKI DEFINISAN, sto je zvanicno postignut socijalni konsenzus po tom pitanju od strane ljudi koji se bave teorijskim racunarstvom.
Ajde ovako: recimo da sam ja prosecan citatelj ovoga foruma koji nema veze sa vezom i onda odjednom procitam recenicu tipa "Racunar radi po matematickom modelu" i onda ja tebe mogu da pitam da mi to pojasnis, tj. da mi kazes sta to zapravo znaci da racunar radi po matematickom modelu, sta znaci "RADITI PO" i sta je to matematicki model. A onda mogu da pitam i po kom to matematickom modelu racunar radi (posto nisi precizirao, da li radi po bilo kom ili samo po nekim odredjenim), zatim da li ih ima vise i da li medju njima postoji neki koji su medjusobno ekvivalentni. Cela zavrzlama nastaje oko tog glagola "RADITI
PO", ajde reci mi sta znaci "RADITI PO", desice ti se da u intuitivnim pojasnjenjima ovog pojma upadnes u kontradikciju, upadnes u petljicu (sto je u tom kontekstu isto sto i kontradikcija), upadnes u beskonacnu regresiju (sto je u tom kontekstu opet kontradikcija) ili da opet uvedes neki dodatni algoritam da bi samim algoritmom objasnio algoritam ili efektivnu proceduru sto se opet svede na kontradikciju. U stvari ono sto ja pokusavam da kazem jeste da recenica "Racunar radi po matematickom modelu" nema nikakvog smisla ukoliko se pre toga striktno ne naznaci da je racunar posledica matematickog modela koji se zove Tjuringova masina a posto je i to suvisno (jer to je ono (p => q) i (q => p) a to je p = q))
jednostavno se kaze onako kao sto sam ja i rekao a sto je najispravnije i najpreciznije opet ponavljam sa stanovista konsenzusa koji je postignut po pitanju na relaciji model-racunar.
Ti pominjes iskljucivo matematicki model, e onda odgovor na pitanje koji je to matematicki model kojim se moze modelirati racunar jeste to je Tjuringova masina. Postoji jos nekoliko matematickih modela racunara ali se moze pokazati ekvivalentnost medju modelima. Kada upotrebljavam izraz Tjuringova masina ja mislim na matematicki model racunara. Ako mi dozvolis da citam izmedju redova tvoju tacku 5, mogu slobodno da ti kazem da ti nemas nikakvu predstavu o tome sta je matematicki model, te onda mogu opet slobodno da kazem da ti
o teoriji modela i algoritama nemas nikakvo predznanje da bi onako OLAKO mogao da kazes ono za sta sam ja rekao da je najveca glupost u ovom topicu (to je onaj orginalan tekst) *nisam namerno hteo da koristim pogrdnije reci mada bi svakako bile korisnije*.
Implikacije itekako imaju veze sa vremenskim kontekstom, to sam pokusao da objasnim tamo gde mislis da sam iskljucio numeraciju, a to je sesta tacka, jer postoji vremenski sled u kome nastaju iskazi p i q, prvo nastaje p, pa onda q, tvoje teze su onda u formi (p => q) => (q => p), sto je naravno tacno jer je p = q (a to dozla boga ono sto ja uporno pokusavam da kazem), ali je u toj postavi p = q nesto sto je pod a), pod b) i pod c) *vidi tacku 6* u odnosu na q => p. Da ne postoji taj vremenski sled tvoje linearizovano izlaganje u tacki 1 i tacki 2 bi onda bilo u formi (p => q) i (q => p) sto je onda ekvivalentno sa p = q. Uostalom nisu isto Esherove ruke koje se medjusobno crtaju, jedna nacrtana ruka koja crta drugu ruku i jedna nacrtana ruka koja crta drugu ruku ali u drugoj ravni. Ja sam spomenuo sta je doslo pre i na osnovu toga pokusao da kazem isto ono sto si ti rekao samo malkice vise potpunije i preciznije.
Da slazemo se visak informacija. Zasmetalo je zato sto je bilo neprecizno i ostavilo
prostora za dve ili vise interpretacija a to je u nauci nedopustivo. Recimo da si rekao polu-istinu (a upravo ona druga polovina ostavlja prostora za jeftine manipulacije, neke od njih i ja koristim), a ja sam pokusao da je doteram do potpuno pravilno formulisane teze (a ne istine), onakve kakva ona otprilike egzistira u odgovarajucoj literaturi.
Ja ne citam izmedju redova, tvoj je propust ukoliko kazes nesto sto se moze na vise nacina interpretirati a svakako ne bi smelo. Preciznost izrazavanja je itekako bitna, ali se ovde konstatacije iznose od frlje, bez ikakve argumentacije ili bez referenciranja na neki RESPEKTABILAN IZVOR. I uopste ne postoji moj kontekst i tvoj kontekst, postoje neki iskazi koje su receni u nekom konktestu a koji nije ni moj ni tvoj. Ne postoje licni konteksti postoje licne interpretacije. Otuda ja stalno potenciram ono socijalni konsenzus.
Da se ne vracamo na godine, one i nisu bitne, vazno je ostati kulturan na forumu. (mada jesam mladji)

Za uvazenog gospodina Bozovica:
Vidis taj lik Hilbert cije ime tako ponosito izgovaras se za svog zivotnoga veka borio protiv ljudi koji govore kao ti. Da Hilbet koji je bio izraziti formalista moze da cuje tvoje reci upitao bi te a sta znaci to KAKO HOCES?!?!?!? Molim, racunar mozes modelirati logikom koju mozes da definises KAKO HOCES?!?!?! Ili ti to hoces da kazes da je racunar po svojoj logickoj strukturi BILO KOJA univerzalna a i ove manje opste algebre. A onda bi isti taj Hilbert procitao i ono BAS SVEGA!!! i pitao a sta je to BAS SVEGA onako formalno.
Kada neko kaze "Imas ODREDJENI aksiomatski skup" to u prevodu znaci "Ja ne znam koji je to skup ali sam u kafani nacuo da postoji"... Ajde definisi mi Hilbertovski formalno tu logiku koja je ista "i u racunaru" "i u matematici", a onda mi daj skup tih aksioma (pretpostavljam da je skup konacan i da su aksiome medjusobno nezavisne, ha). Ili bar referencu gde se ti podaci mogu naci.
E pa vidis od Hilberta, Kantora, Gedela, Tjuringa, Cerca, Posta i Markova (a ne samo od Hilberta koji btw tu ima najmanje role) a na visevekovnim izgradjivanim korenima matematike nastade ovo o cemu mi pricamo. Otkud Tjuring, e pa on je bio najveci vizionar u toj skupini i on je u uspesnom pokusaju da resi halting problem iskoristio ideje Kantora, koje je takodje iskoristio i Gedel i konstruisao opet manje vise srecno kao nus-produkt njegovog istrazivanja matematicki model racunara, mehanizam koji moze da racuna nekakve funkcije videcemo kasnije kakve.
DOKAZ ZA STA?!?!?!?!? Da li je to savremena verzija dokaza da su "ALGORITMI U MATEMATICI" izomorfni sa "PROGRAMIMA U KOMPJUTERU".
Je li to savremena verzija ovoga: "Neka je matematicki problem M neresiv, a mozes napisati program koji ga resava imas kontradikciju, jere na osnovu programa P imas algoritam (matematicki) za resavanje problema M"... Na osnovu programa P imas algoritam A za resavanje problema M?! Nesto mi se cini da bi prvo morao da imas algoritam A da bi uopste mogao da govoris o egzistenciji programa P, a ne obrnuto, te da na osnovu toga ne mozes da pokazes da je nesto kontradiktorno. I egzistiranje problema koji moze biti resen izvrsavanjem nekog algoritma ili izvrsavanjem nekog racunarskog programa uopste ne igra nikakvu ulogu u
izomorfizmu ova dva. Jednostavno, KONKRETAN RACUNARSKI PROGRAM JESTE MATERIJALNO PROSTORNO VREMENSKA REALIZACIJA KONKRETNOG ALGORITMA (a sto mi ovo nesto deluje poznato) i nije potrebno dokazivati izomorfizam izmedju ova dva pojma, ali ga je bitno ustrojiti na srecu ovog materijalnog.
Da li ti znas da taj dokaz ne postoji, ne zato sto jeste ili nije trivijalan, NEGO ZATO STO NIJE POTREBAN, jer opet ponavljam ONO DRUGO NASTAJE IZ ONOG PRVOG. E da si u tokovima sa savremenim teorijskim racunarstvom koje nastade jos cetrdesetih godina prosloga veka i koje se od tada manje vise ne promeni, znao bi da su "ALGORITMI U MATEMATICI" po nikada oborenoj Cerc-Tjuringovoj hipotezi (odatle ono socijalni konsenzus) REKURZIVNE FUNKCIJE (a rekurzivne
funkcije nastaju iz tri primitivne(nula funkcije, sledbenik funkcije, projekcije) primenom seme kompozicije funkcija, seme proste rekurzije i seme minimalizacije), a da se racunarski programi implementiraju na arhitekturama koje mogu da izracunavaju rekurzivne funkcije. Te su stoga racunarski programi materijalizovani zapisi rekurzivnih funkcija (a to nema ama bas nikakve veze za Hilbertovom logikoma i nekakvim "kvazi" opstim algebarskim sistemima, sve se prijatelju moj moze relativizovati ali ti ides predaleko).
Sto se tice potrebnih knjiga iz analize i algebre... Analiza se kao matematicka disciplina ne bavi teorijskim racunarstvom, a i algebra na tom polju trenutno ne daje bas najbolje rezultate i da su trenutno metode eksperimentalne matematike te koje tu najvise pravi progresa (a sto ima itekako veze sa konkretnim racunarstvom jer se same karakteristike toga sto se zove masina ili algoritam ili program upravo porucavaju racunarskim simulacijama tj. racunarskim programima, a to je onaj vrh samoreferentnog istrazivanja). I kada kazem ovu zadnju recenicu ne izgovaram je kao neko ko se u svoje slobodno i radno vreme bavi matematikom, nego ko se bavi racunarstvom ali onim teorijskim (sto u ovim vremenima i nije bas toliko popularno) i ko je prosao osnovne kurseve iz metoda eksperimentalne matematike koje uglavnom predaju fizicari (otuda onako burno reagovanja). Rado cu odgovoriti na sva tvoja pitanja, kada ti prvo odgovoris na onih mojih sest, ili bar polovinu. Ukoliko je dokaz tvoj, mislim da ja nisam kompetentan i da bas i ne bih da gubim i ovo malkice viska vremena na proveravanju njegove korektnosti. Da krajnje je vreme da se rehabilituje taj index, cisto da se ostane u tokovima. Mada evo ipak da ne ostanes uskracen za odgovor, operacija moze da bude prebrojivo mnogo ukoliko je n iz N. Da li si zadovoljan odgovorom, ili ja to nesto tu nisam dobro skapirao (opet bar dva ha ha)...

I na kraju da zakljucimo: Zalosno je sto je lavinu bajtova ovde izazvao topic koji potpuno off-topic. To je onaj drugi, onaj prvi svakako nije. Da pojasnimo:
Sto je najgore ja jesam u RIMU, ali u RIMU u kome je sistem vrednosti totalno poremecen i koji samo steti svojim gradjanima i koji uopste i ne treba da postoji. Zato i pokusavam da budem varvarin. Moj prvi post je bio post koji je trebalo ozbiljno procitati, sve ostalo je manje vise mlacenje prazne slame, gomila sranja i medjusobnog nerazumevanja, pogresnih interpretacija i "licnih konteksta". Sve posle tog posta je kako se to latinski kaze korpus de nesto da je taj post, da je ta "filozofija" potpuno ispravna. Racunarska intuicija se ne razvija na forumu, barem ne kada je to razvijanje u njegovom pocetnom stadijumu. Mladjane generacije koje pocese da se bave racunarstvom u vreme kada je internet postao cudo i ono
sto neki sa veoma velikom greskom zovu Globalna riznice znanja i mehanizmi savrsene socijalne neverbalne interakcije ili nesto tome slicno ocekuju da ce resenje za sve probleme koje imaju na tom putu razvijanja racunarske intuicije naci na forumu. Kao da je to nesto tek tako, kao da to nesto samo po sebi ne iziskuje trud, patnju, suze, beskrajno lozenje, iskrene manifestacije srecu i licnu satisfakciju. Medjutim oni nisu svesni cinjenice da ljudi koji daju odgovore
uopste nisu kompetentni da to cine. A ti ljudi koji se toboze prave pametni i savete, smernice, objasnjenja i resenja daju sakom i kapom opet ponavljam onako intuitivno od frlje, bez ikakve ispravne argumentacije i pozivanja na kvalitetne reference ustvari samo cine MEDVEDJU USLUGU ljudima koje opsluzuju. I samo uticu da se njihova intuicija razvije u pogresnom smeru. Da budemo konkretni: na ovom forumu nema trenutno ni jedne osobe koja se ozbiljno bavi racunarstvom kao naukom, niti osobom koja se bavi specijalizacijom ovog foruma a to je teorija algoritama i ko moze biti kvalitetan autoritet. Ni jedna, ali ama bas ni jedna.
Pored toga da se uociti jedan specifican fenomen: na ovom forumu egzistiraju pojedinci koji se bave takmicarskim radom, koji su procitali ili citaju iste knjige, koji se bave skupom istih problema, koji fenomenalno razmenjuju svoje ideje i koji manje vise komuniciraju iskljucivo medjusobno. A ono sto je najbolje jeste da se oni RAZUMEJU. Medjutim ni oni iako se u neku ruku bave fundamentom ne mogu biti korektni autoriteti. Autoriteti moraju biti ljudi koji se bave teorijom algoritama, koji nesto objavljuju, koji imaju IMPACT faktor koji im je veci od duzine polnog splovila u odgovarajucim jedinicama mere (unapred izvinjenje svim onim koji ce se posle ovoga osetiti ugrozeno). Ostatak populacije ne samo da se medjusobno ne razume, nego u ovakvoj konstalaciji i nema nikakve sanse da se razume. Te ovaj forum kao ovakav nema svrhu postojanja. Stoga jedan konstruktivan predlog: da se ovaj forum ukine jer svakako ne postoje ljudi koji bi posredstvom njega mogli razmenjivati nekakve konstruktivne ideje ili da se transformise u
forum "Zadaci sa takmicenja". Svi nezadovoljni ce u neku ruku vec migrirati na odgovarajuce forume. Sada bi nekao mogao reci: ok, ako ti se ne svidja a ti idi, i ja i hocu, ali sta mogu kada sam prisiljen da u vecoj ili manjoj meri saradjujem sa ljudima kojima je ovaj Rim jedini izvor edukacije, bilo da su to ljudi koji zajedno sa mnom studiraju, bilo da su to poznanici iz ISP. Ovaj RIM jeste jedan ogroman GRAND SHOW, jedna teska pornografija... Mislim da cemo ovime uciniti uslugu i sebi i drugima. HA

[ bojan_bozovic @ 23.01.2006. 16:12 ] @
Nismo culi za polivalentne logike?

Ne uvidjas da kompjuter operise samo sa skupovima i brojevima?
[ formeye @ 24.01.2006. 08:44 ] @
Rec "realnost" u toj recenici se odnosila na "racunar u realnosti" sto nije tesko zakljuciti iz iste.
2. "Realnost je nemoguce opisati Tjuringovom masinom" je ono sto je nedokazivo, a sta ti tvrdis, za razliku od toga da racunar "radi po"/"je ... implementacija" matematickog modela. "Uzmes" matematicki model, proveris da li aksiome iz matematicke teorije vaze i to je dokaz.
Doticna recenica koja tebi stvara problem nije ekvivalentna recenici "racunar radi kao racunar" nego "a <=> b, samim tim je b <=> a". Ova recenica nije logicki neispravna i sadrzi korisnu informaciju da je "a <=> b".
Citat:
sto je zvanicno postignut socijalni konsenzus po tom pitanju od strane ljudi koji se bave teorijskim racunarstvom

Nije.

Ako ti mene mozes da pitas sta znaci "raditi po", isto tako mogu ja tebe pitati sta znaci "KONKRETNA PROSTORNO VREMENSKA REALIZACIJA MATEMATICKOG MODELA". (mogao bih da te pitam za svaki termin iz ove sintagme posebno - sta je prostor, sta je vreme, sta je realizacija, kako je konkretna...)
Citat:
desice ti se da u intuitivnim pojasnjenjima ovog pojma upadnes u kontradikciju, upadnes u petljicu (sto je u tom kontekstu isto sto i kontradikcija), upadnes u beskonacnu regresiju (sto je u tom kontekstu opet kontradikcija)

Pre svega, ne bih objasnjavao nista intuitivno. Po struci sam matematicar, tako da intuicije ovde nema.

Po n-ti put, matematicki model na kome je zasnovan savremeni racunar NIJE Tjuringova masina.

"(p => q) i (q => p) a to je p = q" ovo je netacno. Da si napisao p <=> q, ok, ali p = q ne vazi.

Citat:
Ti pominjes iskljucivo matematicki model, e onda odgovor na pitanje koji je to matematicki model kojim se moze modelirati racunar jeste to je Tjuringova masina.

Kao sto rekoh, nije. Opet na osnovu manjka znanja iz oblasti o kojoj pricas, pridajes odredjenim terminima pogresno znacenje.

Citat:
mogu slobodno da ti kazem da ti nemas nikakvu predstavu o tome sta je matematicki model, te onda mogu opet slobodno da kazem da ti
o teoriji modela i algoritama nemas nikakvo predznanje

UR masine, Tjuringova masina, rekurzivne funkcije, ... su neke od matematickih teorija koje su medjusobno ekvivalentne u smislu njihove izrazajnosti. To stoji. ALI, ni jedan od ovih nije ekvivalentan matematickom modelu po kome rade danasnji racunari.
Mislim da ovo pokazuje ko od nas nema veze sa matematickom teorijom

Evo ti jedna kratka pricica koja ce ti pokazati gde je problem u tvom razumevanju.
Pricaju dva prijatelja, Pera i Laza (ti imas problem kao Laza)
Pera: Svoju prvu zenu sam upoznao u Beogradu
Laza: A drugu?
E sada, da li je Pera ikad spomenuo da ima neku zenu osim prve? Nije.

Citat:
interpretacije. Otuda ja stalno potenciram ono socijalni konsenzus.

Socijalni konsenzus koji ne postoji nigde osim u tvom univerzumu...

Citat:
... ono biti kulturan socijalno i ne kotira bas najbolje ...

Citat:
... Zato i pokusavam da budem varvarin. ...

Malkice upadas u protivrecje (kontradikciju) - nisi kulturan jer se to socijalno ne kotira najbolje (po tebi), a ovde si nekulturan zato sto smatras da socijalno kotiranje na ES-u pogresno?

P.S. Ciklus u dokazu, ni u kom smislu, nije kontradikcija...
[ ntojzan @ 24.01.2006. 12:40 ] @
Dobro, jesam ja zaista jedini kome smeta sto su zadnjih 13 postova totalno off-topic!?

Evo ga jos jedan moj za brisanje. ;-)
[ boki @ 24.01.2006. 13:34 ] @
Jeste off ali je konstruktivna diskusija tako da ne bih brisao... Voleo bih da mogu da prebacim te postove u zasebnu temu ali nazalost ne postoji takva mogucnost...
[ formeye @ 24.01.2006. 14:44 ] @
Meni smeta, to sam vec napomonjao.
Ali i dalje stojim iza toga da ih ne treba brisati.

Citat:
boki: Jeste off ali je konstruktivna diskusija tako da ne bih brisao... Voleo bih da mogu da prebacim te postove u zasebnu temu ali nazalost ne postoji takva mogucnost...

To bi bilo dobro...
[ MilosSavic @ 24.01.2006. 14:59 ] @

Ok, ali stvarno ovo je jace od mene...

Gospodinu Ivanu Cukicu, matematicaru:

Prvo cu Vas citirati: "Izvinjavam se zbog provokacije", a onda cemo nastaviti dalje...
Drugo trudicu se da na sve ono sto ste vi naveli odgovorim, za razliku od Vas koji bezite kao djavo od krsta od vise od 90% onoga sto ja kazem.

Ajdemo jos jednom da Vas podsetimo sta ste vi to rekli:
"Ne moram da podsecam da racunari rade na osnovu matematickog modela i da, samim tim, taj model savrseno odgovara realnosti, za razliku od stvari koje srecemo u fizici koja je samo priblizni matematicki model realnosti."

Ovako, prvo ne smemo da pobegnemo od cinjenice da je u tekstu upotrebljena sledeca konstrukcija: "Ne moram da podsecam" koja je krajnje sugestivna i hoce da kaze da je to sto se dalje kaze opste poznata stvar oko koje se ne treba raspravljati i da se samim tim onaj ko je to rekao ne dovede u situaciju da se njegove reci preispituju *nesevestan odbrambeni mehanizam kada nismo sigurni u svoje reci*. I to ne bilo kakve reci, KRUPNE reci, i to RECI koje se izgovaraju pred auditorijumom za koji sam vec naveo kakav je i kave sve posledice ovako KRUPNE reci mogu da imaju po te ljude. Ok, to je mali uvod.

Ajmo dalje:
Da li Vi to tvrdite da "SAMIM TIM sto nesto radi po matematickom modelu" mora da savrseno odgovara realnosti? Onda ukoliko ste se DOPREZICIRALI i opet izrekli konstrukciju koja je istog tipa kao sa pocetka teksta, a to je konstrukcija "sto nije
tesko zakljuciti iz iste" (nemojte Vise to da radite, nije dobro po onoga koji govori, prvo NEKULTURNO je za sta se Vi zalazete, a nije ni arogancija, ni samoljublje, ni..., drugo neprecizno je, ako nije tesko zakljuciti dajte recite koji je to sled umnih padavina kojim se to zakljucuje, jer ne znate kome se obracate, opet jedan dokaz zasto sve ovo ne treba da postoji), Vasa recenica onda glasi ovako:
"(Sugestivna konstrukcija) racunari rade na osnovu matematickog modela i da, samim tim, taj model savrseno odgovara racunarima u realnosti". MOLIM?!?! STA?!?! KAKO??!?! Sta nam kazuje ta recenica, apsolutno nista, samo nas zbunjuje i ne znamo sta je tu deda, a ko je tu tata. A dodatno nas onda zbuni ona neistina u vezi sa fizikom koja je netacna, a na osnovu koje rasudujemo i o izrecenim stvarima vezane za racunare jer su reci "matematicki model" i "realnost" upotrebljeni u tom kontekstu. Sta se desi na kraju, neko ko ne zna o cemu se tu zapravo radi ima na osnovu vasih reci potpuno drugaciju sliku od one koje treba da
ima.
Trece, Vi ne znate po tacno kom matematickom modelu radi racunar (da znate rekli bi ste koji je to model), samim tim ne mozete tvrditi da to sto racunar radi po matematickom modelu znaci da SAMIM TIM taj model savrseno odgovara realnosti, jer opet vi ne ZNATE koji je to MODEL. Recenica je nepotrebna jer ako je realnost racunar u realnosti onda znamo da je to tacno jer je racunar nastao na osnovu matematickog modela, na sta sam ja i ukazao. A ako je nesto nepotrebno kazano to ne znaci da je nesto kazano na dva ili vise nacina.
Koji je to matematicki model racunara? Koji je to matematicki model po kome radi SAVREMEN racunar? (to je pitanje koje je vama upuceno, ali ja cu svakako na njega odgovoriti). Reci cu Vam po n!-ti put to je TJURINGOVA MASINA. I to je i je prvi, svi ostali matematicki modeli po kojima radi racunar su ekvivalentni sa ovim.
Drugo, zabrinjavate me, postajete kao gospodin Bozovic:
Sta znaci "uzmes" matematicki model. Drugo koji matematicki model, trece koje aksiome i na cemu ih proveravas. I molim Vas, a cega je to DOKAZ.
DA li zelis opet da ti ponovim sta si ti rekao?
Molim Vas gospodine Cukicu matematicaru, ako kazete da NIJE, molim Vas onda mi recite nesto u korist te argumentacije, ako nista dajte mi bar reci koji je onda to model. Ja Vam mogu reci da sam to o cemu pricam procitao u Ceitinovim i radovima njegovih naslednika, a potom da sam identicne reci cuo i usvojio od dvojice univerzitetskih profesora matematike koji se recimo bave ovime o cemu se ovde pise i diskutuje. Samim tim sto ste dali odgovor na ovo pitanje Vi ne dovodite u pitanje postojanje socijalnog konsenzusa, a o tome malkice kasnije.
Ok, evo: "racunar je konkretna prostorno vremenska realizacija matematickog modela koji se zove Tjuringova masina" znaci: da imamo matematicki formalno definisan model (a to je TM, za matematicko formalnu definiciju pogledati jedan od sledecih izvora: "Formalni jezici i teorija automata", autori Crvenkovic, Madraz, fakultetski udzbenik, gde je i ta formalna definicija dosledno citirana iz mnogo znacajnijih i autorativnijih izvora koji su dati na kraju te knjige) i da na osnovu
njega kao uzora koga se drzimo dosledno konstruisemo racunar koji je materijalna pojava u svetu u kome zivimo i koji nas okruzuje i zato kazemo konkretna prostorno vremenska realizacija. Tjuringova masina ima beskonacnu traku sto je nemoguce
realizovati/implementirati u prostorno vremenskim okvirima u kojim se implementira a u kojem smo mi po rodjenju postavljeni.

Onda je suvisno davati dodatne informacije buduci da je cela stvar konkretno objasnjena, za razliku od vase koja je neprecizna i nedorecena, i u neku ruku suvisla i netacna.
Intuicije u matematici nema, veoma pohvalno za jednog matematicara. E pa gospodine matematicaru ukoliko do sada niste iskusili manifestaciju svoje konkretne intuicije nikada nece postati pravi matematicar. Druga stvar, vidimo kako je prosao Rasel, kako prolaze formalisti (o da li je ovde neko spominjao Gedela i ono sto je on uradio formalistima). Stvar je gospodine matematicaru, da vam kaze jedan neuki racunardzija: Matematika je "kvazi-nauka" samim tim sto nema jasno izdiferenciran
metod, koji cini da to nesto bude nauka. Stoga se matematicari u svom radu u velikoj meri oslanjaju na svoju licno-sopstvenu intuiciju. Ukoliko pak hoce objasne nesto do cega su dosli svojom intuicijom rade to na formalan nacin do nivoa koji je dalje intuitivno jasan toliko da ne moze biti dvojakih interpretacija, jer nemamo formalno izgradjenu bazu iz koje mozemo izvesti ono sto gospodin Bozovic tvrdi, a to je AMA BAS SVE. Veoma je bitno matematicarima i ko im pocetke te intuicije "ugradi", tj. od koga i kako nauce da izgradjuju svoju matematicku intuiciju. Verujte, ne bih voleo da sam na vestu vasih ucenika/buducih ucenika, a rado bih voleo da jednog dana procitam jedan Vas rad gde cete vi biti strogo do kraja formalni.
Po n+1 put, jeste, ako tvrdite suprotno, recite koji je to model.
Hvala, uvazavam korisnu primedbu. Zato prepravite sve one = sa <=>. Medjutim. zalosno je sto ste se Vi hvatate za to spram svih ovih iskucanih bajtova, posebno kada matematicarima cesto nije bitna ta cinjenica, jer su svesni konteksta. Ako su p i q iskazi iz L racuna, tj. iskazna slova iskaznih formula, bice nam iz konteksta jasno da = znaci isto sto i <=> jer operator = u tom racunu ne postoji.
Kao sto rekoh, dajte mi VAS MATEMATICKI MODEL RACUNARA, iliti da budem u VASEM ELEMENTU, dajte mi MATEMATICKI MODEL PO KOME RACUNAR RADI.
Vec sam u prethodnom postu gospodinu Bozovicu ukazao na znacenje termina ODREDJENI. Molim Vas recite mi koji konkretno termini i koje konkretno znacenje. Da ne bude ono NACUO SAM U KAFANI.
E pa vidite te matematicke teorije koje pominjete su u stvari matematicki modeli racunara koje su medjusobno ekvivalentne i to ne u smislu svoje IZRAZAJNOSTI, nego u smislu svoje IZRACUNLJIVOSTI. Sve one mogu da RACUNAJU REKURZIVNE FUNKCIJE (vec sam rekao sta su) i to je KRAJ. E pa vidite gospodine Cukicu, prvo je nastao taj rekrzivan racun, zatim Tjuringove masine, zatim Univerzalna tjuringova masina, zatim masine Markova i Posta, a onda su se pojavile registarske masine. Ceo taj sled jeste posledica pojave Turingove masine. A matematicki modeli savremenih racunara jesu upravo ono sto vi zovete UR, nadam se da to znaci Univerzalna registarska masina i to je matematicki model savremenog racunara. I pokazano je (jedan od izvora su knjige Ahoa u kome mozete naci podrobnije reference) da je matematicki model registarske masine ekvivalentan matematickom modelu tjuringove masine. Uostalom nije model
registarske masine pao sa neba, niti ga je neko otkrio kao da je on vec postojao i kao da nije imao nikakve veze sa sledom istorijskih procesa i socijalnim konsenzusom. Matematicki model tjuringove masine je bila inspiracija za nastanak.
Po n-ti put vas onda molim recite mi "PO KOME MATEMATICKOM MODELU RADI RACUNAR". A onda cu opet da vas citiram: "Mislim da ovo pokazuje ko od nas nema veze sa matematickom teorijom". Onda cu da budem jos malkice drzak i recicu da vi to NE ZNATE.
Kada smo krenuli na "viceve" i recimo da ste vi PERA, a da sam ja LAZA, onda bi dijalog mogao i da se nastavi ovako:
Pera: "Ko je tebi ikada rekao da sam se ja zenio drugi put?"
Laza: "Vidis, Pero, ja Laza, citam knjige, razvijam svoju racunarsku intuiciju ali ne na forumima i kao racunar rukovodim se potpuno deterministickim zakonima, te tako i donosim svoje zakljucke, te na osnovu njih i postavljam svoja pitanja i dajem konkretne argumentacije. Kad tad sam znao da ces da se ozenis ponovo jer je tvoja prva zena bila ruzna i glupa. Osim toga kresnuo sam je jer sam tvoj najbolji prijatelj i znam da se lose JE*E i znao sam kad tad da ces je ostaviti. Posto sam znao da si porodicni tip, jer ti treba podrska porodice da bi uradio stvari koje jesi, znao sam da ces kad tad ponovo da se ozenis kada ostavis ovu prvu. I najveca stvar ZALOSNO je sto sam ja to znao pre tebe"... E tu je tvoj problem, ne zelis/ne mozes da stvari sagledas sa jednog veceg nivoa jer si "umetnik" zen budista iliti sta god, nisam zapamtio. Ogranicavas se samim tim sto po svojoj filozofiji ukidas lepote prirodnoga jezika i ne izgradjujes senzibilitete za nesto sto samo po sebi nije true/false, ali se moze modelirati samo tako da bude true/false.
Socijalni konsenzus postoji u mom i u univerzumu ljudi koji se bave naukom. Svaka, ali bas svaka definicija je posledica socijalnog konsenzusa. Nauka je subjektivna stvar, ukoliko je zelimo uciniti objektivnom moramo imati socijalni konsenzus. Svo ono stampanje radova i citiranje istih da bi radovi bili u razlicitim hijerarhijama jeste postizanje socijalnog konsenzusa. Da nema socijalnog konsenzusa mi ovde i sada ne bi mogli da pricamo o ovoj temi.
Izgleda da Vas nisam razumeo: pojasnite mi sta znaci da je socijalno kotiranje na ES-u pogresno? Da li vi to postizete i socijalni konsenzus i van foruma. Niko mi nije kakvo je moje socijalno kotiranje na ES-u, ja sam samo cuo da sam nekulturan.
I vidite da ste jednim delom upravu (sto ne znaci da je ono kontradikcija jer te Eserove ruke nisu u istoj ravni), postao sam kulturan, persirao sam Vam, i kada god sam napisao Vam, upotrebio sam veliko slovo V. Jel JEBI GA, sa kulturnima mozes samo kulturno.

Gospodinu Bojanu Bozovicu, coveku koji ce ponovo da se upise na Matematicki fakultet:
Ocigledno je da u diskusiji izmedju nas dvojice neke stvari nestimaju, sto je opet dokaz onoga sto sam tvrdio u prvom postu.
Ocigledno je da se ne RAZUMEMO. Niti da POKUSAVAMO da se razumemo. Ja ovde kucam ko stoka, iznosim nesto, na sta vi nemate nikakve konkretne primedbe, za razliku od mene koji ima milion primedbi, i na sve to vi dodjete i postavite jedno pitanje: "Nismo culi za polivalentne logike?". Na sta cu ja da budem kulturan i da odgovorim (za razliku od Vas koji niste odgovorili ni na jedno pitanje, za razliku od Vas koji niste rekli nista kada sam ja rekao nesto sto nema veze sa vezom odgovarajuci na Vase pitanje u proslom postu, za razliku od Vas koji nije rekao nista na moja krajnje korektna pitanja koja dovode u pitanje Vas dokaz): "Ne nisam". Sto znaci da sam ja Vama odgovorio na dva pitanja, a vi meni ni na jedno. Na pitanja se ne postavljaju pitanja. Pitanja nisu odgovori na postavljena pitanja. Na pitanja se daju odgovori. Pitanja nisu izgovor za neznanje, pitanja nisu dokaz. Ajde ja cu biti jos malkice drzak pa cu Vas pitati: Sta su to polivalente logike? I onda drugo najvaznije pitanje: Objasnite u koji kontekst cele ove price vi njih stavljate, sta ste njima objasnili i sta ste njima pokazali. Vi hocete da kazete da samim tim sto mi postavljate pitanje "Sta su to polivalentne logike" dajete odgovor da je Vas dokaz tacan ili da Vas Hilbert da je ziv ne bi kritikovao. Ja imam konkretne primedbe, buduci da ste uceniji od mene (samim tim sto znate neke stvari za koje ja nisam cuo a to su Hilbertova logika, polivalentne logike i tako dalje i tako dalje i tako dalje), molim Vas da mi konkretno odgovorite, ne vise na sest, nego sada na citavih 14 *slovima cetrnaest* pitanja, ima ih i vise ali to je ono sto sam uspeo da prebrojim brzim pregledom mojih tekstova. Ukoliko to ne zelite onda je to opet dokaz da ovaj FORUM ne treba da postoji, ukoliko ne znate, recite to ali JASNO I GLASNO i nemojte zamajavati ostatak Rimljana.
Zatim dalje. Ne uvidjam da kompjuter operise samo skupovima i brojevima. Ajde molim Vas otvorite mi oci, pojasnite mi to, ili mi makar odgovorite na sledeca pitanja *nadam se da nisam drzak sto ih postavljam*: Da li racunar moze da OPERISE misaonim konceptima? Da niste mozda mislili na matematicki model racunara? Ali ni on ne operise misaonim konceptima, on samo te iste
koristi da objasni neki fenomen realnosti. Samim tim sto je matematicki model on mora negde i nekako ukljucivati nesto iz skupova i brojeva jer su to dovoljno opste matematicke kategorije na koje smo prisiljeni u matematickom radu jer nemamo
druge, jer nemamo ni losije, jer nemamo ni bolje. Drugo posto ste nam rekli da su to prirodni brojevi, pitanje je sa kojim konkretno "skupovima operise racunar". I molim Vas to je ono sto sam naglasio i u prethodnom postu: nemojte siliti stvari
relativizujuci ih, izbegavati odgovore i po diskusiju postavljati beskorisna pitanja *sem ukoliko necete moj autoritet da dovedete u pitanje, ali vam onda svakako ne bi bilo problem da na moja pitanja odgovorite*. Sta je ovde relativizacija, pobogu sve stvari koje bilo kako operisu i koje bilo kako se trudili da ih objasnimo "operisu" pomocu BROJEVA i pomocu SKUPOVA, jer je matematika TAKVA KAKVA JE i JEDINI jezik koji mozemo da upotrebimo kada pokusamo NESTO DA OPISEMO u
NAUCNO-POZITIVISTICKOM SMISLU. Stoga mozete reci: ves masina operise pomocu skupova i brojeva, ok ne uvidjam ni to. Zaista za nekoga ko misli da treba da rehabilituje svoj index PRETERUJETE.

Gospodinu Ntojzanu:
nazalost i meni smetaju, ali nisam ja kriv sto me vuku za jezik i ne znaju da prekinu. Uostalom meni smeta i ceo topic koji je sam po sebi off-topic i sto je najcrnje meni smeta ceo ovaj forum, ali mi na zalost ne smetaju ljudi koji ga poseceuju i
sa kojima imam stvarnih socijalnih kontakata a jedan je upravo Prpi (tebi baram ne moram da persiram jer znam koliko si kulturan :))

Na kraju zakljucak:
U nedogled, u nedogled. Jos jedan dokaz da forum ne treba da postoji ako stvari postavimo na sledeci nacin: Recimo da je Gospodin Cukic teza1, gospodin Bozovic teza2, ja antiteza1, ja antiteza2, a da sinteze nema (jer svi smo po malo upravu), mogu samo reci SINTEZU ali za onaj moj prvi post: Ovaj forum ne treba da postoji....
[ bojan_bozovic @ 24.01.2006. 21:25 ] @
@Savic

Gospodine Savicu, da li znate sta je Turingova masina? Sto se tice aksiomatskog skupa, ovde cemo da ga izvedemo induktivno, pre 11 god. sa ovo ucio, pa se nadam da mi nece neko zameriti na ev. gresci.

1. Neka su A,B supovi A^B (a presek B) je skup C cEA^cEB => cEC (cEC ako je cEA i cEB)
AUB je skup C cEAVcEB => cEC (cEC ako je cEA ili cEB)

2. Neka su A,B skupovi A<=B (B je sadrzano u A) ako bEB => bEA (ako za svako bEB b elemenat B povlaci b elemenat A)

3. Neka je A<=B i B=>A onda je A=B Naime onda bEb => bEA i aEA => aEB tj. nema a iz A koje nije u B i b iz B koje nije u A.

4. Prazan skup: definisimo skup U (univerzum) koji sadrzi svaki skup kojim operisemo. Neka je skup 0UA=A za svako AEU onda je 0 prazan skup. Da vidimo sta jos vredi.

(AUB)^C=A^CUB^C (asocijativnost unije ka preseku, tj sabiranja prema mnozenju)
AU0=A (0 je neutral za sabiranje na ovom skupu)
AUB=BUA (komutativnost sabiranja)
A^B=B^A (komutativnost mnozenja)
A^0=0 (prazan skup je nula za mnozenje na ovom skupu)

Ovo sledi iz gornje 4. Moze da se pokaze.

5. Pojam preslikavanja. Preslikavanje F:A->B (koje slika A u B) pridruzuje svakom a iz A neko b iz B. A je skup definisanosti ili domen B je skup slika ili kodomen. a iz A je original, a F(a) iz B je slika.

6. Injektivno preslikavanje. Preslikavanje F je injektivno onda i samo onda ako razlicitim elementima iz skupa definisanosti A pridruzuje razlicita b iz skupa slika B

7. Surjektivno preslikavanje. Preslikavanje F je surjektivno ako za svaki elemenat iz skupa slika B postoji original iz skupa definisanosti A.

8. Bijektivno preslikavanje. Preslikavanje F je bijektivno onda i samo onda ako je injektivno i surjektivno.

9. Kompozicija. Neka F slika A u B a G slika B u C. FoG je novo preslikavanje koje slika A u C. Naime, za svako a iz A postoji b iz B da je F(a)=b i za svako b iz B postoji c iz C da je G(b)=c pa za svako a iz a postoji c iz c da je G(F(a))=c.

10. Inverz funkcije. Neka F:A->B (F slika A u B). Ako postoji G: koje slika B u A da je G(F(a))=a za svako a iz A onda je G iverz F. Da postoji inverz funkcije F nuzno je i dovoljno da je F bijektivno.

Neka je F injektivno. Razlicitim elementima iz A pridruzuje razlicite slike iz B tj. nema elementa iz b da ima vise od jednog originala iz A.

Neka je F surjektivno tj. za svako b iz B postoji original iz A. Upravo ta f-ja koja preslikava B u A zadovoljava da je inverz F.

Da pokazemo i da je dovoljno. Neka F ima inverz G. Samim tim je F surjektivno, jer za svako b iz B postoji original u A, s obzirom da skup definisanosti G obuhvata celo B. F je i injektivno, jer razlicitim elementima iz A pridruzuje razlicite slike iz B. Da nije tako, imali bi smo makar jedno b iz B sa vise originala u A, a G zadovoljava uslov da razlicitim originalima iz b pridruzuje razlicite slike iz A.

11. Pojam unarne operacije. o je unarna operacija na A onda i samo onda ako je preslikavanje koje slika A u A. Pise se o:A->A ili oaEA (oa pripada A). Tipican primer je operator negacije u logici.

12. Dekartov proizvod. Neka su A i B skupovi. AXB je novi skup koji sadrzi parove {{a1...an},{b1...bn}} gde je a1...an iz A a b1...bn iz B (uredjene dvojke)
slicno za AXA1...XAn gde su A1..An skupivi (uredjene n-torke)

13. Pojam binarne operacije. Neka o slika AXA u A. o je binarna operacija na A.

14. Pojam binarne relacije. Binarna relacija r slika AXA u B podskup AxA

15. Induktivni skup. Neka je aEA, imamo binarnu operaciju na * na A i a*a pripada A. Neka za svako a1EA a1*a pripada A. A je skup prirodnih brojeva N.

.....

itd itd za nastavak, molim, knjiga iz analize I i algebre I i II za matematicki ;-) Dovoljno je od mene. A sto se Turingove masine tice, evo sta je http://en.wikipedia.org/wiki/Turing_machine Dakle, mi smo govorili o osnovnim osobinama skupova i brojeva kojima kompjuter manipulise, jer kompjuter ne manipulise drugim stvarima. Slika koju vidite na ekranu je niz brojeva u memoriji koji opisuju vrednost boje svakog piksela. ;-) Slicno, svaki prozor koji otvorite u OS koji koristite (Windows, UNIX, Macintosh) je predstavljen skupom svojih osobina (broj koji ga identifikuje, dimenzije, broj dugmadi itd. koje su, molim odgovorite, kako predstavljene?) . Dakle, ovde se NE govori o Turingovoj masini!!!
[ MilosSavic @ 24.01.2006. 21:27 ] @
Ja se izvinjavam ali nisam ostao dosledan jer imam jos nesto da dodam:

E pa vidite gospodine matematicaru kontradiktorni ste u tacki 2. Ako kazete
da je racunar implementacija matematickog modela, nema potrebe da se taj
isti matematicki model uzima i da se proveravaju aksiome iz matematicke
teorije (ako pri tome kada kazete teorija mislite na model) jer je ZABOGA
taj racunar nastao na osnovu toga modela, te je samim tim njegova materijalna
prostorno vremenska konkretna realizacija dokaz da taj model "sljaka" u nasoj
realnosti. Jos jedan pokazatelj da Vi nemate veze sa vezom na relaciji
model - stvarnost. Jedno pitanje koje sam postavio je krajnje na mestu: Na cemu
proveravate te aksiome, na necemu sto ste konstruisali na osnovu tih aksioma.
I to je dokaz cega, dokaz da racunar postoji iako ga zaista VIDIMO da radi i da
vrti nas omiljeni Linux.

Zatim dalje, doticna recenica nije ekvivalentna sa "a ekv b samim tim b ekv sa a"
Vi hocete da kazete da je Vasa recenica: "Ne moram da podsecam da racunari rade na osnovu matematickog modela i da, samim tim, taj model savrseno odgovara realnosti, za razliku od stvari koje srecemo u fizici koja je samo priblizni matematicki model realnosti" u stvari TAUTOLOGIJA. Ne bih bas rekao. Mozda ste pobrkali i mislili na one linearizovane recenice. Ali onda ona moja "racunar radi kao racunar" nema veze sa tim dvema i tu Vam pada argumentacija. Uostalom ona je jos pala u prethodnom postu.

U prethodnom postu sam zaboravio da kazem da je i glagol "radi po" upotrebljen
u kontekstu u kome ide i nastavak recenice koji se bavi fizikom. U tom kontekstu
glagol "radi po" se moze shvatiti kao opisuje. Teorija/model opisuje nesto. Ali
matematicki model racunara ne opisuje racunar on jeste do jer za njega znamo da je nastao iz njega. Za razliku od toga vidite sta znaci kada kazem "jabuka pada i to
radi po Njutnovom zakonu gravitacije". E to je nesto sto se ne moze pokazati. Jer
jabuka moze da "radi i po" Ajnstajnovim zakonima. Zato je preciznije i bolje stvari
objasnjavati upotrebljavati glagol jeste. Tu nemamo problema sa kontekstom.

Zatim da jos dodam zasto stalno naglasavam KONKRETNA PROSTORNO VREMENSKA REALIZACIJA.
Zato sto racunar postoji u nasem prostoru, nasi programi u izvrsavanju imaju i
vremensku dimenziju, medjutim matematicki model racunara iliti TM (Tjuringova masina) ima beskonacnu traku i zato stalno moramo naglasavati to KONKRETNA PROSTORNO VREMENSKA REALIZACIJA, bar do trenutka dok to svima ne postane jasno.

Zatim, IZRAZAJNOST. E vidite nisu ekvivalentne u smislu svoje izrazajnosti. Izrazajnost je staticka kategorija, vi u mozete da napisete rekurzivnu funkciju i mozete da napisete program i to nisu stvari koje mogu da se porede u smislu izrazajnosti jer te dve stvari nemaju iste leksicke i sintaksne elemente. Ali kada pokusate da izracunate rekurzivnu funkciju ili da izvrsavate program na neki input, dobijate stvari koje su ekvivalente i to samo u smislu IZRACUNLJIVOSTI.

Da, slazem se, ali beskonacni ciklus u dokazu jeste kontradikcija, uostalom kao
i beskonacna regresija. Kada sam rekao beskonacna regresija, mislio sam da cete
podrazumevati i ono beskonacni ciklus.

Hvala
[ bojan_bozovic @ 24.01.2006. 21:47 ] @
Citat:
Ja se izvinjavam ali nisam ostao dosledan jer imam jos nesto da dodam:

E pa vidite gospodine matematicaru kontradiktorni ste u tacki 2. Ako kazete
da je racunar implementacija matematickog modela, nema potrebe da se taj
isti matematicki model uzima i da se proveravaju aksiome iz matematicke
teorije (ako pri tome kada kazete teorija mislite na model) jer je ZABOGA
taj racunar nastao na osnovu toga modela, te je samim tim njegova materijalna
prostorno vremenska konkretna realizacija dokaz da taj model "sljaka" u nasoj
realnosti. Jos jedan pokazatelj da Vi nemate veze sa vezom na relaciji
model - stvarnost. Jedno pitanje koje sam postavio je krajnje na mestu: Na cemu
proveravate te aksiome, na necemu sto ste konstruisali na osnovu tih aksioma.
I to je dokaz cega, dokaz da racunar postoji iako ga zaista VIDIMO da radi i da
vrti nas omiljeni Linux.


Postoji i skup. Spil karata u ruke. dalje, gde to vidis kontradikciju u tacki 2 ja sam podskup oznacio sa <=? Molicu, citirajte, da ne bude ovako, pa ce da vidimo.

Citat:
Zatim dalje, doticna recenica nije ekvivalentna sa "a ekv b samim tim b ekv sa a"
Vi hocete da kazete da je Vasa recenica: "Ne moram da podsecam da racunari rade na osnovu matematickog modela i da, samim tim, taj model savrseno odgovara realnosti, za razliku od stvari koje srecemo u fizici koja je samo priblizni matematicki model realnosti" u stvari TAUTOLOGIJA. Ne bih bas rekao. Mozda ste pobrkali i mislili na one linearizovane recenice. Ali onda ona moja "racunar radi kao racunar" nema veze sa tim dvema i tu Vam pada argumentacija. Uostalom ona je jos pala u prethodnom postu.


Citirajte. Ovo sto sam boldovao je neki logicki zakljucak?

Citat:
U prethodnom postu sam zaboravio da kazem da je i glagol "radi po" upotrebljen
u kontekstu u kome ide i nastavak recenice koji se bavi fizikom. U tom kontekstu
glagol "radi po" se moze shvatiti kao opisuje. Teorija/model opisuje nesto. Ali
matematicki model racunara ne opisuje racunar on jeste do jer za njega znamo da je nastao iz njega. Za razliku od toga vidite sta znaci kada kazem "jabuka pada i to
radi po Njutnovom zakonu gravitacije". E to je nesto sto se ne moze pokazati. Jer
jabuka moze da "radi i po" Ajnstajnovim zakonima. Zato je preciznije i bolje stvari
objasnjavati upotrebljavati glagol jeste. Tu nemamo problema sa kontekstom.


Da matematicki model gore savrseno opisuje rad racunara.

Citat:
Zatim da jos dodam zasto stalno naglasavam KONKRETNA PROSTORNO VREMENSKA REALIZACIJA.


U kom prostoru i kom vremenu?

Citat:
Zato sto racunar postoji u nasem prostoru, nasi programi u izvrsavanju imaju i
vremensku dimenziju,


Dokazujte da imaju vremensku dimenziju.

Citat:
medjutim matematicki model racunara iliti TM (Tjuringova masina) ima beskonacnu traku

Moze te operacije da se implementiraju kako hoces, i bez trake. Tesko nam je da zamislimo (apstrahujemo) stvari, pa se drzimo konkrektnog a ne apstraktnog? Dalje Turingova masina nema veze sa logikom teorijom brojeva i teorijom skupova. Zamena teze.

Citat:

i zato stalno moramo naglasavati to KONKRETNA PROSTORNO VREMENSKA REALIZACIJA, bar do trenutka dok to svima ne postane jasno.


Opet se ponavljate.

Citat:

Zatim, IZRAZAJNOST. E vidite nisu ekvivalentne u smislu svoje izrazajnosti. Izrazajnost je staticka kategorija, vi u mozete da napisete rekurzivnu funkciju i mozete da napisete program i to nisu stvari koje mogu da se porede u smislu izrazajnosti jer te dve stvari nemaju iste leksicke i sintaksne elemente.


Izomorfni su. Ne drzi se konkretnog.

Citat:
Ali kada pokusate da izracunate rekurzivnu funkciju ili da izvrsavate program na neki input, dobijate stvari koje su ekvivalente i to samo u smislu IZRACUNLJIVOSTI.


Sad cu ja da se ponovim. Spil karata u ruke.
[ MilosSavic @ 24.01.2006. 22:11 ] @
Gospodine Bozovicu,
da li ste vi procitali moj prethodni post? Ocigledno da niste, ili ste ga procitali
ali ga niste razumeli. Ocigledno je i da niste odgovorili ni na jedno od mojih pitanja,
ali evo ja cu opet odgovoriti na svako Vase:

Znam sta je Tjuringova masina i to veoma dobro. Ukoliko Vi ne znate sta je, dao sam
Vam odgovarajucu referencu. Definicija je malo duza i nemam zivaca da je kucam. I
opet ponavljam na pitanja se ne odgovara pitanjima. Ali da se ne ponavljamo procitajte
prethodno prethodni post.

Da li Vi pod pojmom aksiomatski skup podrazumevate aksiomatsku teoriju skupova. Ako
je podrazumevate ovo nisu aksiome tog skupa, niti ta aksiomatika ima ikakve veze sa
teorijskim racunarstvom. Ukoliko ne podrazumeva nego je aksiomatski skup u stvari
skup aksioma mogu da ponosno izjavim samo sledece:
Vidim koliko Vam je znanje matematike. AKSIOMATSKI SKUP SE NE IZVODI!!!! Aksiome se
ne izvode, aksiome nastaju jednom dubljom intuicijom iliti nekim dubljim/visim
razumevanjem/uopstavanjem, te se kao takve ne izvode. Drugo nesto mi se cini da
je vas aksiomatski skup beskonacan i da je vas aksiomatski skup matematika. Da li
samo pomenuo da ne treba lazno relativizovati stvari i da to sto smo prinudjeni da
koristimo matematiku nema nikakve veze sa onim o cemu diskutujemo.
Drugo nemojte NAS UCITI MATEMATIKU i to posebno ne onu IZ MATEMATICKE GIMNAZIJE.
Tu sam naucio skolujuci se u toj skoli. Drugo NAVEDITE REFERENCU onoga sto ste iz
prepisali, to je krajnje posteno po autore istih tih udzbenika. Mozete nam reci
stranu da se ne mucimo da listamo knjigu.
Zatim ono o cemu vi pisete nema nikakve veze sa teorijskim racunarstvom. Ok,
priznajem tamo se prica o nekakvim rekurzivnim funkcijama. Ali mislim da nam
definicija funkcije nije potrebna kada o nekim stvarima raspravljamo na ovakvom
nivou, mislim da svim znamo te definicije, pa cak i ja, gle cuda.
Drugo umesto sto trosite vreme i tastaturu na pisanje stvari koje su opste poznate
i koje se uce u GIMNAZIJI, mogli bi ste da potrosite to VREME da odgovorite na
neko od mojih pitanja. Ali ne, sta vi ovime hocete da kazete, hocete da kazete
da vi znate sta je to bijektivno preslikavanje. Kome je to bitno, nikome, ponajmanje
ne meni.
I sta vi hocete da kazete da je taj aksiomatski skup koji je u stvari MATEMATIKA
OPET UKOLIKO NE RAZUMETE DA VAM KAZEM: JA IMAM KONKRETNA PITANJA, MOLIM VAS
DAJTE MI KONKRETNE ODGOVORE AKO ZNATE, A AKO NE ZNATE NEMOJTE PISATI NESTO
STO NEMA VEZE SA OVIM OFF-TOPICOM.
Ne mi nismo govorili o osnovnim osobinama skupova i brojeva, MI SMO GOVORILI
O MATEMATICKOM MODELU RACUNARA i A POSEBNO SA VAMA SAM RAZGOVARAO O EKVIVALENCIJI
POJMA ALGORITAM I PROGRAM. Ovo sto vi pisete nema nikakve veze ni sa jednim ni sa
drugim....
Slika koju vidim na prozoru nije niz brojeva, nego jedan FIZICKI PROCES. U
memoriji nemam brojeve, u memoriji imam neke impulse. E vidite to je
materijalno. Za razliku od toga u matematickom modelu racunara isti taj ne operise
ni skupovima ni brojevima. Taj operise nad svojom azbukom za koju je dovoljno da
bude dvoelementna jer se viseelementne mogu kodirati dvoelementnom. Recimo da
matematicki model racunara operise sa {|, _} sto Vam je nadam se jasno ukoliko
ste procitali ono sto pise na wikici. I to je bio odgovor na vase pitanje. Ali
posto sam svestan da to necete razumeti (jer je odgovor dovoljno opst) onda cu vam
dati i parafrazu za vas konkretni slucaj.
Svaki prozor koji otvorim u bilo kom operativnom sistemu je predstavljen fizickim
procesom za koji ja ne znam koji je jer se ne razumem dovoljno u digitalnu elektroniku,
ali svakako da jeste, inace ta nauka ne bi ni postojala.
Drugo kompjuter ne manipulise prozorima, dugmadima i slicnim stvarima, njime manipulisu
programi, a to je vec jedan drugi nivo, ali svakako nesto sto je manje od ovoga nivoa
apstrakcije na kojem smo mi. Jedno je kako operativni sistem kao program tretira prozor
a drugo je kako isti taj racunar tretira prozor. Uostalom racunari i postoje da bi smo
taj isti prozor mogli opisati programom i to upravo koristeci jezik brojeva i jezik
skupova, tj. koristeci jedan jezik koji je nastao iz matematike i koji na osnovu toga i
vuce neke osobine iz te "kvazi" nauke, polu umetnosti. Ali to ne znaci da racunar operise
skupovima i brojevima. Opet ponavljam matematicki modeli racunara operisu odgovarajucom
vec navedenom dvoelementnom azbukom, a konkretne materijalne realizacije impulsima iliti
tim fizickim stvarima o kojima ja nista ne znam.
DAKLE, da jos jednom ponovim, OVDE SE I STALNO GOVORI O TJURINGOVOJ MASINI, tj.
MATEMATICKOM MODELU RACUNARA, a NE O MATEMATICI. Nadam se da Vam je to sada jasno.
Vidite na vecinu Vasih pitanja sam i sam odgovorio. Ali bih svakako voleo da cujem
opet odgovor ali od Vas, da vidim da li ste razumeli. A znacu ako ste prepisali. To se
ne moze sakriti.
I na kraju, gospodine BOZOVICU, sto dozvoljavate da pravim MAGARCA OD VAS. Ne zasluzujete
vi to, bez lazne skromnosti.

P.S U medjuvremenu video sam da ste jos nesto napisali. Na to cu Vam odgovoriti sutra, sada mi vreme istice. Ali koliko sam uspeo da preletim, opet cete ispasti MAGARAC....
[ MilosSavic @ 24.01.2006. 22:26 ] @

Imam jos par minuta pa cu samo na brzaka...
Izgleda da ste Vi pogresno odgovorili na ono sto je bilo upuceno gospodinu Cukicu,
te njegova tacka 2. (tacka gospodion Cukica) nema nikakve veze sa vasom tackom 2.
Mislim da to dovoljno govori na to koliko ste vi koncentrisani kada citate nesto. Citate nesto sto nema nikakve veze sa onim sto ste vi rekli a poistovecujete ili pronalazite vase reci u tome. Jednom recju VI STE IZGUBLJEN SLUCAJ....
Nema potrebe da citiram nesto sto niste razumeli i sto nema nikakve veze sa onim na sta vi odgovarate.
Na to SAVRSENO sam vec izneo milion argumentacija gospodinu Cukicu... Prvo to procitajte u prethodnim postovima. Tu se o tome pisalo i nasiroko i nadugacko...
U nasem prostoru i u nasem vremenu. To jest u nasem materijalnom svetu koji nas okruzuje.
Samim tim sto instrukciju A izvrsi posle instrukcije B program ima vremensku dimenziju.
"Te operacije mogu da se implementiraju kako hoces" je recenica koja je netacna.
Da li vi mozete nesto da izracunavate a da nemate memoriju. Isto tako masina ne moze bez trake. Ali VI NE ZNATE STA JE TO TJURINGOVA MASINA, stoga nemojte se dodirivati stvari koje ne znate.
PA JA SAM SVE VREME ZA TO DA SE DRZIMO KONKRETNOG, ZATO I PRICAM O Tjuringovim masinama, NE RELATIVIZUJEM STVARI KAO VI, tj. ne drzim ih u domenu koji je apstraktniji kao sto je logika i teorija skupova, jer svakako to o cemu pricamo ne treba da bude tamo.
Niko nije tvrdio da nisu izomorfni i izomorfizam nema nikakve veze sa izrazajnoscu kakvim ja razumevam tam pojam, ukoliko se uzme u obzir razlicitost leksiskih elemenata jednog i drugog. Medjutim i te kako je bitna za izracunljivost.

SADA CU JA OPET DA PONOVIM: Sto iznova i iznova dozvoljavate da pravim magarca od Vas. Ne zasluzujete vi to.
[ bojan_bozovic @ 24.01.2006. 22:28 ] @
@Milos Savic

Molim, fizicki proces. Koji? O kom fizickom procesu u kompjuteru govoris? Koji je relevantan za funkcionisanje racunara? (Hint:Babbage ova masina) Ovo nema veze sa teorijskim racunarstvom? Molim. Kompjuter operise samo sa, inicijalno, prirodnim brojevima. Ne operise sa fizickim velicinama koje se mogu samo aproksimirati. Da do aksioma se dolazi i induktivno.

Hajde da vidimo ovako. Uzevsi skupove sudova U(A) gde je A u obliku {0,1} uz operatore konjukcije, disjunkcije i negacije {^,V,-} i U(B) gde je B {true,false} uz iste operatore i isti aksiomatski skup recimo 0-15 gore. Da li mozes imati ijedan sud koji je razlicit? Mozes li logicki doci do drugacijeg zakljucka? ;-) To je sustina. BTW samo gore da se ubaci i komplement skupa pa je algebra sudova izomorfna sa algebrom skupova, zato je nisam ni navodio.

Izvini, sto se minimalnog skupa aksioma tice iz koga se matematika moze izvesti v. recimo od Hilberta radove iz teorijske logike. Nemam bas doktorat, a i mnogo sam zaboravio u zadnjih 11 godina, a ti se pretvaras da imas. Pa zato moramo po seljacki da diskreditujemo sagovornika u nedostatku argumenata. Toliko. BTW mozes da konstruises racunar bez poznavanja Turingove masine (ona se izvodi iz 1-15) ;-)

[Ovu poruku je menjao bojan_bozovic dana 24.01.2006. u 23:45 GMT+1]
[ formeye @ 24.01.2006. 22:39 ] @
A.A.S. Hvala na persiranju :) Necu ti persirati, posto si rekao da si mladji
A.S. Nemoj da se pozivas na stvari koje si pisao Bozovicu jer ih nisam citao (ne citam stvari koje su upucene nekom drugom)

"*nesevestan odbrambeni mehanizam kada nismo sigurni u svoje reci*"
Ne to je fraza koja se koristi kad smatramo da tvrdnja koju iznosimo je toliko ocigledna, da bi je i neuki stagod shvatio.

"konstrukcija "sto nije tesko zakljuciti iz iste""
Moj jedini problem u ovoj situaciji je cinjenica da ne poznajem ljude kojima pisem, tako da smatram (potpuno neosnovano) da su u stanju da zakljuce stvari koje sam ja u stanju da zakljucim.

"Sta nam kazuje ta recenica"
Recenica nam kazuje da "racunari rade na osnovu matematickog modela". Ako, kojim slucajem, neko nije shvatio sta to znaci, drugi deo recenice "taj model savrseno odgovara racunarima u realnosti" pokusava da objasni na drugi nacin.

Sto se tice fizike, potpuno je nebitno da li je proces isao "realnost -> model" ili "model -> realnost" (napomena da nijedno od ta dva NISAM implicirao), jedino bitno je da matematicki model koji fizika koristi da opise realnost ne odgovara realnosti, nego ga samo aproksimira.

"odgovara realnosti, jer opet vi ne ZNATE koji je to MODEL"
Racunar je nastao na osnovu matematickog modela. Ako je racunar nastao na osnovu matematickog modela, onda matematicki model savrseno odgovara realnom racunaru. Iz ove dve recenice, primenom modus ponensa, dobijamo: "Matematicki model savrseno odgovara realnom racunaru".
Kao sto vidis, doticne recenice su logicki ispravne CAK iako nismo ni definisali koji je to model u pitanju. Samim tim, da bih odbranio svoju tezu, apsolutno je nepotrebno, a samim tim i visak informacija, spominjati koji je to model.

"Tjuringova masina ima beskonacnu traku sto je nemoguce realizovati/implementirati"
Ovim si sam sebi obrazlozio zasto TM *nije* model po kome rade danasnji racunari. (napisao si da pojasnim ono "NIJE") (1)
Jos jedna stvar, nije na meni da dokazem da tvoja teza ne vazi (ovo za TM i racunare), nego je na tebi da dokazes da vazi.

"Druga stvar, vidimo kako je prosao Rasel, kako prolaze formalisti"
Rasel je, da se izrazim umetnicki, pokrenuo ogromnu lavinu koja je zamalo srusila celu tadasnju matematiku. Posle toga su stvari ispravljene i *formalno zasnovane* tako da je lavina se slegla, a sve je ostalo na svom mestu.

"Matematika je "kvazi-nauka" samim tim sto nema jasno izdiferenciran"
Ako je matematika "kvazi-nauka" sta su onda ostale "nazovi nauke" koje koriste u sebi matematicke metode?
Sta znaci "znanje"? (definisi mi)

"nacin do nivoa koji je dalje intuitivno jasan"
Opet pokazujes fundamentalno nepoznavanje materije. Nije do nivoa koji je "dalje intuitivno jasan", nego do nivoa aksioma i osnovnih pojmova (potraziti u recniku matematickih termina). A aksiome i osnovni pojmovi ne moraju biti intuitivno jasni. (primer aksioma paralelnosti za geometriju Lobacevsoga)

"Po n+1 put, jeste, ako tvrdite suprotno, recite koji je to model."
Kao sto rekoh, na tebi je da dokazes da to JESTE model po kojem...
(znam da ces ovde da se uhvatis na to da izbegavam da kazem koji je model u ptanju, ali u tom slucaju ces samo da pokazes da nisi dorastao pitanju koje sam ti postavio, jer, kao sto sam vec napomenuo, za odrzavanje moje teze za koju se ti kacis, apsolutno je nebitno konkretizovanje modela)

"to ne u smislu svoje IZRAZAJNOSTI, nego u smislu svoje IZRACUNLJIVOSTI"
Prvo, sta znaci "izracunljivost matematicke teorije", posto je o matematickim teorijama rec.
Izrazajnost je termin koji se koristi u mnogo vise oblasti nego izracunljivost.

"E pa vidite gospodine Cukicu, prvo je nastao taj rekrzivan racun, zatim Tjuringove masine, zatim Univerzalna tjuringova masina, zatim masine Markova i Posta, a onda su se pojavile registarske masine. Ceo taj sled jeste posledica pojave Turingove masine."
Precesto upadas u kontradikcije. Prvo tvrdis da implikacija ima veze sa vremenskim redosledom. Pa tvrdis da je rekurz. racun dosao pre TM. A onda tvrdis da je taj sled posledica TM.
Vidim da ti je strasno lako da vidis nepostojece protivrecje kod drugih, a da ti ne smeta ni u jednom trenutku sto ti imas pravih protivrecja.

Ne znam da li si primetio, ali uspeo si da dokazes da ni jedan od tih modela nije model po kom racunar radi - prvo si dokazao da TM nije mpkrr ((1)), a sad si jos i napisao da su svi ovi modeli ekviv sa TM. Cestitam. (a upao si i ovde u kontradikciju tvrdeci da TM jeste model...)

Aho je u pravu kada tvrdi ekvivalentnost medju tim modelima, ali nigde ne spominje da po tim modelima radi racunar.

"Ogranicavas se samim tim sto po svojoj filozofiji ukidas lepote prirodnoga jezika i ne izgradjujes senzibilitete za nesto sto samo po sebi nije true/false, ali se moze modelirati samo tako da bude true/false."
Lepote prirodnog jezika su cinjenica da me svako moze shvatiti kako on zeli, bez obzira na to sta kazem? (primer: TI)

"Socijalni konsenzus postoji u mom i u univerzumu"
Socijalni konsenzus da je racunar konkretna vremen......... Tjuringove masine ne postoji nigde osim u tvom univerzumu.
(P.S. I nije SVAKA definicija soc. kon.)

"znaci da je socijalno kotiranje na ES-u pogresno"
Procitaj malo bolje *svoje* tekstove pa ces da vidis gde si pretproslog puta upao u crnu jamu protivrecnosti. (Opet u stilu chan budistickog umetnika)
Kako si krenuo, ne nameravas da izadjes iz nje?

Tvoj "vic", kako si ga nazvao, je samo pokazatelj onoga sta tvrdim - da sta god ja da napisem, ti ces to apsolutno pogresno protumaciti i odatle zakljuciti milion stvari koje nisu logicke posledice mojih tvrdnji.

Previse mi olaksavas posao - em pobijas sam sebe, em dokazujes moje tvrdnje... Hvala.

[Ovu poruku je menjao formeye dana 24.01.2006. u 23:42 GMT+1]
[ MajorFatal @ 24.01.2006. 22:56 ] @
Eh, da, ovaj, da nastavim ja gde sam stao, samo da pitam jos par stvari pa I Vi slobodno nastavite.

Citat:
Citat:
srki Gde si ti video da sam ja rekao “fajl broj n”?

U tvom postu od 14.01.2006. Druga recenica, zadnje tri reci.

Citat:
Citat:
srkiJa te samo pitam kako da znamo koji bitovi u tom kompresovanom fajlu predstavljaju broj n.

Pa ako ih ti upises valjda ti najbolje znas koji su. Imas fajl. Podatak n o duzini tog fajla upises u kompresovani fajl kao prvi podatak I odvojis nekakvim separatorom od drugog podatka (m) I to je cela mudrost ja stvarno ne znam sta tu ima toliko komplikovano.

Citat:
Citat:
formeye Prvo da ti odgovorim na "drugi moment":
Ako nizu od n - 1 elemenata dodas jedan bit, dobijas niz od n elemenata - sta si onda kompresovao? (pocetna poruka je bila n bitova).


Eeeeheej! Stoj! Pa ni ja tvoje: 2^(n-1) + 2^(n-2) +… nisam protumacio pogresno tj. da spajas nizove tih duzina pa bi dobio visestruko duzi niz od 2^n – 1 nego ispravno tj. da sabiras brojeve kombinacija koje su nizovi tih duzina u stanju da tvore. Jesam dodao 1 bit ali ne na pocetak niza duzine 2^(n-1) vec kao poseban entitet koji se tumaci u zavisnosti od prethodnog stanja na brojacu sto sam pokusao I da ilustrujem sa dva primera brojaca koji bi radili po tom principu, a sto mi uopste niste prokomentarisali.

Citat:
Citat:
formeye Tek kad si siguran da ti nisi u stanju da oboris svoju teoriju, tak je tada baci lavovima. :)

Lepo sto sebe nazivate lavovima, moja ocena bi ipak pre bila da su u pitanju babe koje samo traze izgovor da ne rade svoj posao. Ja pocinjem I da sumnjam da ste vi u stanju ovo da isprogramirate. Da ja pustim vas da se vratite onome sto najbolje znate da radite: resavanje skolskih zadataka I prezvakavanje programa koji su u 1000 varijanti vec isprogramirani tako da svud po internetu postoje vec napisani delovi koda I gotova resenja tako da kad napabircite dovoljno koda mozete da se pohvalite da ste “isprogramirali” 1001 varijantu programa za kompresiju slika.

Citat:
Citat:
bojan_bozovic recimo 2^32 bita i brojac 2^31 bit treba ti dakle po tvome 2^31 za brojac i 2^31 za poziciju. ;-) Sta je 2^31+2^31? ;-)

Iako ne razumem kako ovu tvoju racunicu povezujes sa modelom koji sam predlozio ipak cu ti odgovoriti na pitanje 2^31+2^31 = 2*2^31.

Citat:
Citat:
Srdjan Krstic Postoje 2^32 razlicite kombinacije sa 32 bita i to je ultimate truth, a ako bi na BILO KOJI NACIN (koeficijenti ili stogod) uspeo da predstavis vise od toga to bi znacilo, po Dirichlet-ovom principu (ili pigeon-hole, ako ti volja), da bar dva broja predstavljas istom sekvencom bitova, i samim tim, tvoj fajl postaje nemoguc za desifrovanje.

Pa ja sam I predlozio da se dva (I vise) fajlova predstavljaju istom sekvencom bitova s tim sto bi jednoznacnost sekvence bita bila odredjena povezivanjem sa prethodnom sekvencom bita sto bi omogucilo desifrovanje fajla. I posto mi to niko do sada nije prokomentarisao ponovicu: Potencijalni brojac bi pocinjao ovako:
0 .. 0
1 .. 1
2 .. 0
3 .. 00
4 .. 0
5 .. 01
6 .. 0
7 .. 10
8 .. 0
9 .. 11
10.. 0 Dakle niz ”0” bi se tumacio kao 0 ako nema prethodnog stanja na brojacu, kao 2 ako je prethodno stanje 1, kao 4 ako je prethodno stanje 00 itd… U postu od 18.01.2006. sam pokazao da se sa dva bitna mesta na taj nacin moze iskodirati 27 fajlova. Samo st ne znam da li to treba porediti sa brojem kombinacija koje se inace na klasican nacin dobijaju sa dva bitna mesta u tom slucaju uspeh je enorman 27 u odnosu na 4, ili sa 4 bitna mesta (jer pri kraju brojaca treba da se pamti 2 aktuelne I dve prethodne vrednosti) pa je odnos 27 prema 16, ili sa 4+3+2+1 bitna mesta pa nisam nista uradio jer je odnos 27 prema 31. Eto pokusao sam I sa cen budizmom pa ne ide: ne znam da li sam oborio svoju teoriju ili potvrdio a sto je najgore izgleda da nemam sa kime o tome ni da raspravim.

Citat:
Citat:
Srdjan Krstic 2. ruku na srce, malo je nervirajuce sto toliko kukas svakodnevno,

U pravu si, necu vise da kukam odsad cu da pretim: ako mi ne isprogramirate ovo zapalicu prostorije elitesecurity-ja I dici cu vam u vazduh sluzbeno vozilo.

Citat:
Citat:
MilosSavicUostalom meni smeta i ceo topic koji je sam po sebi off-topic

Izvini brate da sam znao da nekome moze I da zasmeta nikada ga ne bih pokretao. Al sad sta je tu je. A jel ti bas mnogo smeta? Ako je bas mnogo sto ne bi probao da ga zaobidjes? Evo ja ti obecavam da se necu ljutiti ako budes odsustvovao.
[ bojan_bozovic @ 24.01.2006. 22:58 ] @
Citat:
Iako ne razumem kako ovu tvoju racunicu povezujes sa modelom koji sam predlozio ipak cu ti odgovoriti na pitanje 2^31+2^31 = 2*2^31.


Tj. 2^32=2^32 hehehe, primecujes li kompresiju ;-)

Izvini Majorfatal, za bilo kakve tj random podatke to ti ne radi -- nikako -- v gore moras da imas bijekciju sa skupa ulaznih podataka A na skup izlaznih podataka B inace nemas dekompresiju. Primer npr. f-ja koja slika skup {"aaaa","bb"} u skup {"4a","2b"} ce da ti kompresuje, za random podatnke ne mozes da imas takvu funkciju, Najbolje sto imas je identicka f-ja tj f(a)=a za svako a (to je pohranjivanje falja bez kompresije - store) inace ti f-ja nece da bude i injektivna tj da za razlicito a1 i a2 iz skupa definisanosti A imas razlicite slike iz B primera imas koliko hoces, npr. spil karata ne mozes predstaviti jednom kartom.

[Ovu poruku je menjao bojan_bozovic dana 25.01.2006. u 00:09 GMT+1]
[ MajorFatal @ 24.01.2006. 23:10 ] @
Naravno da ne primecujem nego i dalje mi nije jasno iz tog tvog posta 2^31 koji brojac i 2^31 za koje pozicije? Povezi ako ti nije problem sa mojim modelom.
PS. Sva sreca sto niko nije video tvoju poruku pre nego sto si je izmenio, bas si se bio zaneo a?;)
[ srki @ 24.01.2006. 23:21 ] @
Citat:
MajorFatal: U tvom postu od 14.01.2006. Druga recenica, zadnje tri reci.

Nisi lepo razumeo recenicu. Treba da se shvati "..u fajlu predstavlja broj n". Mada nije sada to bitno.

Citat:
Pa ako ih ti upises valjda ti najbolje znas koji su.

Ali ne zna onaj ko treba da otpakuje fajl.
Citat:
Imas fajl. Podatak n o duzini tog fajla upises u kompresovani fajl kao prvi podatak I odvojis nekakvim separatorom od drugog podatka (m) I to je cela mudrost ja stvarno ne znam sta tu ima toliko komplikovano.

Pa napisi mi tacno kako to da uradim. Koji bajt (ili niz bajtova) zelis da ti predstavlja separator?
[ bojan_bozovic @ 25.01.2006. 06:49 ] @
Zato sto 2^n vrednosti razlicitih moras bas da prikazes sa 2^n vrednosti - spil karata ne mozes predstaviti sa 51 kartom. Ako imas 3 sedmice u hercu zaredom, mozes da stavis jedno papirce sa trojkom u spil ispred prve sedmice i dve uklonis (manje karata=kompresija). Isto je 101%. Nego, s obzirom da su dobri algoritmi za kompresiju znatno slozeniji (npr LZ) sto ti ne probas da nadjes neke algoritme za kompresiju pa da ih implementiras? Vec te to zanima vidim.

Ako imas mnogo vremena za gubljenje, uzmi sve vrednosti duzine n (tj 2^n njih, sve razlicite) pa probaj da kompresujes tvojom metodom npr vec 2^3 ili 2^4 ce da bude dosta - ne ide. Ne ide ni jednom metodom BTW. Ako nemas redundantnost - recimo niz koji se pionavlja, nema kompresije.

[Ovu poruku je menjao bojan_bozovic dana 25.01.2006. u 08:04 GMT+1]
[ formeye @ 25.01.2006. 11:30 ] @
Citat:
Eeeeheej! Stoj! Pa ni ja tvoje: 2^(n-1) + 2^(n-2) +… nisam protumacio pogresno tj. da spajas nizove tih duzina pa bi dobio visestruko duzi niz od 2^n – 1 nego ispravno tj. da sabiras brojeve kombinacija koje su nizovi tih duzina u stanju da tvore.

Ne spajas nizove.
Pre svega, u postu kad napisem niz, mislim na konacan niz:
Ajde da pokusam sto preciznije mogu da kazem postavku zadatka i problem.
Kompresija je funkcija f koja preslikava skup nizova W na sebe samog koja mora biti bijekcija.
Znaci, nikakvog spajanja, povezivanja nizova nema. Svakom nizu iz domena moras da dodelis tacno jedan (i nijedan vise) niz iz kodomena. Obelezimo sa W_n skup nizova takvih da je njihova duzina n, a sa M_n skup nizova cija je duzina manja ili jednaka n.
Unija kad n ide od 0 do beskonacno skupova W_n je W.

Dokaz koji si imao prilike da procitas je dokaz da ne postoji bijekcija koja slika W_n na uniju skupova W_0, W_1, ..., W_n-1 = M_n-1. Sto znaci da mora postojati bar jedan niz A_n iz W_n takav da f(A_n) ne pripada M_n-1. Sto dalje znaci da je za to A_n, f(A_n) duzine vece ili jednake od n. Tu je kraj.

Citat:
Lepo sto sebe nazivate lavovima, moja ocena bi ipak pre bila da su u pitanju babe koje samo traze izgovor da ne rade svoj posao. Ja pocinjem I da sumnjam da ste vi u stanju ovo da isprogramirate.

Izvini, ali moj posao NIJE implementacija algoritama za koje je dokazano da ne rade ono sto bi trebalo. Posalji ideju u Politiku, mozda objave clanak da je neko "nas" uspeo da napravi kompresiju random podataka kao sto su objavljivali da je neka baba smislila postupak za trisekciju ugla!

Citat:
Da ja pustim vas da se vratite onome sto najbolje znate da radite: resavanje skolskih zadataka I prezvakavanje programa koji su u 1000 varijanti vec isprogramirani

A mi tebe da pustimo da se vratis svom poslu - da trosis samo svoje, a ne i nase vreme, na besmislice koje ti, zahvaljujuci nedovoljnom poznavanju materije, deluju pametno.

Do sada si odrzavao komunikaciju na nekom nivou i trudio sam se da ti objasnim gde nisi u pravu. Posle ovog posta, gde se trudis da uvredis ljude koji zele da ti pomognu, slobodno od mene ne ocekuj vise nikakvu pomoc.

To sto zelis je dokazano da je nemoguce i kraj.

Over and out.

@yooyo
:)
[ ntojzan @ 25.01.2006. 11:52 ] @
@MajorFatal:

Da bi kompresovao random-like podatke, moras prvo definisati sta su to random-like podaci. Potom moras ustanoviti koliki je procenat tih random-like podataka u odnosu na ukupan broj podataka da bi ustanovio da li je uopste moguce napisati program koji ce moci da smanji random-like podatke a poveca ostale. Tek posto je taj uslov zadovoljen, mozes krenuti u izradu bilo kakvog algoritma. Inace uslov za to jeste da manje od 50% ukupnih kombinacija cine random-like podaci.

Inace razlika izmedju random-like i random podataka jeste sto random podaci podrazumevaju SVE moguce kombinacije, dok se pod random-like obicno podrazumevaju kombinacije koje se ne mogu kompresovati statistickim metodama.

Ako se budes malo vise posvetio izucavanju teme, shvatices da preko 99% kombinacija cine upravo random-like podaci, znaci svi pokusaji da se ti podaci kompresuju su unapred osudjeni na propast. Uopste nije bitno koji je algoritam u pitanju.
[ Nedeljko @ 30.10.2008. 11:13 ] @
Imam ja 100% korektan algoritam za kompresiju bilo kakvog niza bajtova sa sledecim osobinama:

1. Radi u konacnom vremenu za ma kakve fajlove bilo koje duzine.
2. Kada se fajl zapakuja, pa otpakuje, dobija se fajl identican polaznom.

Sta mislite, kako je to moguce.
[ mmix @ 30.10.2008. 11:24 ] @
Hmmm, sa 0% stepenom kompresije
[ Shadowed @ 30.10.2008. 11:31 ] @
Tako sto je stepen kompresije manji ili jednak nuli? :)
[ vlaiv @ 30.10.2008. 11:32 ] @
Uh, pa taj sa 0% kompresije je jednostavan.

Mislim da je Nedeljko u opstem slucaju mislio na negativan procenat.
[ Nedeljko @ 30.10.2008. 13:41 ] @
Svidja mi se kako razmisljate.

Da, nigde nisam rekao da komprimovani fajl mora biti kraci od originalnog. To je to.
[ misk0 @ 31.10.2008. 08:26 ] @
Nigdje nije receno da je voda mokra pa je to podrazumjevano... ako se kaze 'kompresovan' onda se smatra 'sazet, smanjen, umanjen' ili kako hoces. Uostalom, svi arhiveri vracaju fajl u byte identican koliko znam, tako da.... what's the point?
[ Nedeljko @ 31.10.2008. 12:42 ] @
Da, svi arhiveri vracaju fajl identican pocetnom, s tim da arhiva moze biti duza od polaznog fajla. Generisi (pseudo)slucajan niz vrednosti u opsegu 0-255 i upisi ih binarno u neki fajl, pa ga komprimuj cime god hoces i dobices arhivu koja je duza od samog fajla koji si komprimovao.
[ Nedeljko @ 31.10.2008. 13:00 ] @
Evo, pomocu programa

Code:

#include <fstream>
#include <cstdlib>

using namespace std;

int main() {
    const int bytes = 100000;
    ofstream out("random.bin");
    
    for (int i=0; i<bytes; ++i) {
    unsigned char value = rand();
    
    out.put(value);
    }
    
    return 0;
}


generisao sam fajl random.bin duzine 100,000 bajtova. Kada sam ga komprimovao bzip2 kompresorom, dobio sam fajl vece duzine za 807 bajtova. Naravno, rezultati ce zavisiti od generatora pseudoslucajnih brojeva, pocetnog seed-a i izabrane kompresije i njenih parametara.
[ MajorFatal @ 26.08.2011. 04:31 ] @
@bojan_bozovic

Citat: "Zato sto 2^n vrednosti razlicitih moras bas da prikazes sa 2^n vrednosti - spil karata ne mozes predstaviti sa 51 kartom."

Sa 2^n vrednosti kracih po broju upotrebljenih bita. Spil karata mozes predstaviti i 1 kartom ako je na primer posaljes u koverti preko okeana, tvoj sagovornik sa druge strane ce znati da treba da odigra partiju karata, a ako mu posaljes kockicu za jamb da treba da odigra partiju jamba. Spil karata mozes predstaviti i sa nekoliko karaktera: "S", "p", "i", "l", "k", "a", "r"... itd bas kao sto si ti u ovom postu pa ce sagovornik znati na sta mislis jer je spil karata za igranje opste poznata stvar, ono sto si hteo da kazes je da ne moze da se predstavi promesan spil karata sa jednom kartom ili sa 51., kartom odnosno ne spil vec redosled karata u njemu, pa sad opet zavisi, ako je spil tek stigao iz fabrike jos neraspakovan mozes jer su karte obicno u takvom spilu poredjane "po redu" (od manje ka vecoj, po znakovima), ili ako u takvom spilu fali 1. karta opet ces moci da rekonstruises spil: znaces i koja karta fali i gde joj je tacno pozicija, pa cak i ako vise karata nedostaje znaces ih sve koje su i gde su im pozicije, pa cak i ako sve nedostaju na osnovu informacije "nov spil karata" ti mozes da rekonstruises i zamislis kako to izgleda ili kupis ako hoces da igras, pa i kad je spil promesan mozes ponekad da ga rekonstruises npr: ako je neki profi krupije koji sece spil tacno na pola pa onda te dve polovine izmesa kao u onim filmovima iz Las Vegasa ako je to uradio kako treba znaces svaka karta gde je zavrsila vec na osnovu prve, ono sto si zaboravio da kazes u svom izlaganju je nesto kao: "dobro, pravedno, povoljno za igru" promesan spil karata, odnosno redosled karti u njemu se ne moze predstaviti 1. kartom ili 51. kartom, sad ti treba i neki idealni (matematicki idealan) "mesac" tj. krupije ili krupijerka u koga ces da imas poverenja da ce "dobro", po tvojoj proceni dobrog, da promesa karte, kako je br. kombinacija nacina na koji 1. spil karata moze da se promesa nekoliko biliona valjda, to je po pravilu "dovoljno dobro" za prosecnu partiju tablica, ali za profesionalne potrebe u kazinu recimo, verovatno si primetio da krupijei izmesaju desetak, petnaest spilova i sloze ih 1. do drugog, za potrebe poker aparata, mehanicke naprave koja bi trbalo da na posten nacin izmesa karte potrebno je smisliti random funkciju takvu da ne moze da bude "rekonstruisana" tj. da potencijalni igrac ne moze da uoci pravilo po kome su karte promesane i prikazuju se na ekranu, ipak s vremena na vreme okoreli pokerasi uspevaju da "zakucaju" poker aparat tj. da pogode svih 10. ili 12. ili vec koliko karata koje bi trebalo da su izabrane metodom "slucajnog izbora", sta mislis kako im to polazi za rukom, uocavaju "pravilo" ili dovoljan broj pokusaja? Redosled karata u dovoljno dobro promesanom spilu karata ne mozes predstaviti sa 1. kartom, ali to nema veze sa ovom temom o kojoj pisem. 2^n razlicitih vrednosti ako pod tim podrazumevas sve vrednosti iz nekog opsega, moras da prikazes sa 2^n vrednosti, ali u vezi sa ovim o cemu sam pisao mozes da upotrebis manji broj bita nego za prikazivanje originalnih vrednosti

Citat: "Ako imas 3 sedmice u hercu zaredom, mozes da stavis jedno papirce sa trojkom u spil ispred prve sedmice i dve uklonis (manje karata=kompresija)."

Pricamo o danasnjim, savremenim racunarima. Ne mozes da stavis papirce jer nije spil karata i papircica, vec spil karata, tj. to bi bilo kao da u "bit streamu" (nizu bita valjda) imas space (razmak) ili dvojku osim nule i jedinice, znaci ne moze.

Citat: "Isto je 101%."

Da je to sto si napisao ispravno, napisao bi ispravno tj. 100%. Ne pise se 101 nego lol :)

Citat: "Nego, s obzirom da su dobri algoritmi za kompresiju znatno slozeniji (npr LZ) sto ti ne probas da nadjes neke algoritme za kompresiju pa da ih implementiras? Vec te to zanima vidim."

Bas zato sto su slozeniji kao i danasnji programski jezici ili sam ja pogresno ucio.


Citat: "Ako imas mnogo vremena za gubljenje, uzmi sve vrednosti duzine n (tj 2^n njih, sve razlicite) pa probaj da kompresujes tvojom metodom npr vec 2^3 ili 2^4 ce da bude dosta - ne ide."

Odgovoreno na drugoj temi: http://www.elitesecurity.org/t...ompresija-random-like-podataka

Citat: "Ne ide ni jednom metodom BTW. Ako nemas redundantnost - recimo niz koji se pionavlja, nema kompresije."

U duzem random nizu ako je stvarno random (slucajan), neprestano se ponavljaju (tj. postoji redundantnost) kraci random nizovi. Nisu identicni pa da imas ponavljanje u statistickom smislu pa da brojis broj ponavljanja istog niza bita ili neke kodne reci vec su isti u jednoj svojoj osobini a to je da su takodje random kao i ceo niz neki delovi koda su manje random neki vise, ako bas mnogo skratis duzinu kodne raci kojom pregledas niz, uocices da mozda ti kraci nizovi vise i nisu toliko random tj. da ih prepoznajes po sadrzaju i tada ima mesta za statistiku i prebrajanje medjutim obicno ih tada ima i vise sto bi povecalo broj informacija za opisivanje originalnog fajla, ako produzis kodnu rec za pregledanje fajla uocices da ih sada ima manje ali su slozeniji za opisivanje. Jedini za sada dobar nacin je valjda taj LZ a on se shalta sa klasicnih metoda tamo gde moze tako da radi preko nekih prirucnih tamo gde je situacija sa bitima manje povoljna a neke delove koda jednostavno preskace i ne pokusava da ih kompresuje jer bi samo dobio losiji rezultat (za ove potrebe) tj. ekspanziju tog dela koda? Kontam i da bi LZ ili bilo koji bolji algoritam za kompresiju morao da uocava "trendove" u random nizu bita tj. da konstatuje duze ili krace delove koda koji odgovaraju gorenavedenim?
[ MajorFatal @ 26.08.2011. 04:43 ] @
Citat:
Nedeljko
...generisao sam fajl random.bin duzine 100,000 bajtova. Kada sam ga komprimovao bzip2 kompresorom, dobio sam fajl vece duzine za 807 bajtova. Naravno, rezultati ce zavisiti od generatora pseudoslucajnih brojeva, pocetnog seed-a i izabrane kompresije i njenih parametara.


Kakva je struktura novonastalog fajla od 100.807 bajtova? Da li je uredjene strukture pa je pogodan za klasicne nacine kompresije? Onda bi imao odlican rezultat : jos jednom bzip2 i dobices fajl velicine 10.000 bajtova.
Verovatno nije uredjen vec opet random? Ako na novonastali fajl od 100.807 bajtova ponovo primenis bzip2 dobices ponovo jos veci i opet random fajl? Ako bi postupak ponovio dovoljan br. puta (iteracija) mogao bi da dobijes i fajl od milion bajta koji je takodje random strukture? I to uvek istim postupkom bzip2? Da li bzip2 ima "inverz funkciju" tj. umesto recimo ponavljanja da prebraja promene ili tako nesto? Ako bi imao inverz i ako bi ti random fajl od milion bajta bio pocetni fajl za kompresiju uz pomoc dovoljnog broja ponavljanja mogao bi da ga svedes na 100.000 bajta? Tj. bar neki random fajl bi ipak mogao da se kompresuje? Ovakvom ili nekom drugom metodom. Ovo je jos jedan "namesten" primer jer vazi samo u 1. slucaju i za 1. specificni fajl ali je dobar za ilustraciju.
[ MajorFatal @ 29.08.2011. 00:49 ] @
Citat:
formeye: Ne spajas nizove.
Pre svega, u postu kad napisem niz, mislim na konacan niz:
Ajde da pokusam sto preciznije mogu da kazem postavku zadatka i problem.
Kompresija je funkcija f koja preslikava skup nizova W na sebe samog koja mora biti bijekcija.
Znaci, nikakvog spajanja, povezivanja nizova nema. Svakom nizu iz domena moras da dodelis tacno jedan (i nijedan vise) niz iz kodomena. Obelezimo sa W_n skup nizova takvih da je njihova duzina n, a sa M_n skup nizova cija je duzina manja ili jednaka n.
Unija kad n ide od 0 do beskonacno skupova W_n je W.

Dokaz koji si imao prilike da procitas je dokaz da ne postoji bijekcija koja slika W_n na uniju skupova W_0, W_1, ..., W_n-1 = M_n-1. Sto znaci da mora postojati bar jedan niz A_n iz W_n takav da f(A_n) ne pripada M_n-1. Sto dalje znaci da je za to A_n, f(A_n) duzine vece ili jednake od n. Tu je kraj.


Takodje, a nadam se preciznije, odgovoreno na drugoj temi, u postovima posle 18.06: http://www.elitesecurity.org/t...ompresija-random-like-podataka

Ovi 2^(n-1), 2^(n-2) itd... fajlovi (tj. "manji", "kraci" brojaci, tj. sve kombinacije koje su u stanju da naprave) opisuju (2^n)-2 razlicitih kombinacija jednake duzine iz originalnog opsega fajlova jednake duzine a kojih ima sve ukupno 2^n, preostala 2 fajla bi trebalo da se mogu zameniti, kodovati, kompresovati ili sta vec uz pomoc po dva razlicita fajla ali ovo se mozda moze izvesti u praksi u zavisnosti od osobina fajl sistema na kome bi se to radilo...

Citat:
formeye
A mi tebe da pustimo da se vratis svom poslu - da trosis samo svoje, a ne i nase vreme, na besmislice koje ti, zahvaljujuci nedovoljnom poznavanju materije, deluju pametno.

Do sada si odrzavao komunikaciju na nekom nivou i trudio sam se da ti objasnim gde nisi u pravu. Posle ovog posta, gde se trudis da uvredis ljude koji zele da ti pomognu, slobodno od mene ne ocekuj vise nikakvu pomoc.


-U pravu si, izvini...

Citat:
formeye
To sto zelis je dokazano da je nemoguce i kraj.


by Shanon pretpostavljam?

Citat:
formeye
Over and out.

@yooyo
:)


formeye: "Bilo kakva kompresija podataka je moguca ako i samo ako postoji visak informacija.
Ako su podaci slucajni (po definiciji slucajnosti), tada ne postoji visak podataka i, samim tim, kompresija je nemoguca."

Ako se slucajno predomislis navedi tu definiciju slucajnosti koju spominjes u zagradi "po definiciji slucajnosti".
[ MajorFatal @ 29.08.2011. 01:01 ] @
Citat:
ntojzan: @MajorFatal:

Da bi kompresovao random-like podatke, moras prvo definisati sta su to random-like podaci.


Nista ja ne moram :) A i zasto bih kad ima pametnijih i pismenijih ljudi od mene? (mada imao bih neke svoje ideje). Ako pregledas ovih par tema o kompresiji nacices nekoliko razlicitih vidjenja i tumacenja termina "random" i "random-like" cak si i ti dao jednu koja uopste nije losa, cak sta vise:
ntojzan: "Inace razlika izmedju random-like i random podataka jeste sto random podaci podrazumevaju SVE moguce kombinacije, dok se pod random-like obicno podrazumevaju kombinacije koje se ne mogu kompresovati statistickim metodama.

U trenutku dok ovo pisem "random-like" nije definisano (ili opisano) na wikipediji a i za termin "random" nije bas najsjajnija situacija: http://en.wikipedia.org/wiki/Random

Randomness has somewhat disparate meanings as used in several different fields. It also has common meanings which may have loose connections with some of those more definite meanings. The Oxford English Dictionary defines "random" thus:

Having no definite aim or purpose; not sent or guided in a particular direction; made, done, occurring, etc., without method or conscious choice; haphazard.
Closely connected, therefore, with the concepts of chance, probability, and information entropy, randomness implies a lack of predictability. Randomness is a concept of non-order or non-coherence in a sequence of symbols or steps, such that there is no intelligible pattern or combination.

Tj. u prevodu: "Bez svrhe, nije poslato u odredjenom smeru, napravljeno bez metoda odluke, hazarderski, nedostatak predvidljivosti, bez reda ili inteligentnog obrasca ponasanja"? Pa prilicno negativna definicija? Vise sta nije, nego sta jeste?

"Iskreno receno terminologiju "random-like" sam samo preuzeo sa comp-compress arhiva jer je najvise licilo na nesto cime se bavim vec duze vreme.

Citat:
ntojzan
Potom moras ustanoviti koliki je procenat tih random-like podataka u odnosu na ukupan broj podataka da bi ustanovio da li je uopste moguce napisati program koji ce moci da smanji random-like podatke a poveca ostale. Tek posto je taj uslov zadovoljen, mozes krenuti u izradu bilo kakvog algoritma.

Kao sto rekoh, nista ja ne moram, ima i pametnijih i spretnijih od mene a sasvim sigurno koji bolje programiraju.

Citat:
ntojzan
Inace uslov za to jeste da manje od 50% ukupnih kombinacija cine random-like podaci.


E da sam znao da je Shannon ne bi se toliko zamislio svojevremeno nad ovim sto si napisao, uz sve duzno postovanje Vi ponekad nekriticki prenosite neke stvari koje same po sebi nisu netacne ali ne mora da znaci da ne bi mogle da budu prosirene ili nadopunjene ili kritikovane ili gledane iz nekog drugog ugla, recimo. Ceo citat od Shannona:

The ratio of the entropy of a source to the maximum value it could have while still restricted to the same
symbols will be called its relative entropy. This is the maximum compression possible when we encode into
the same alphabet. One minus the relative entropy is the redundancy. The redundancy of ordinary English,
not considering statistical structure over greater distances than about eight letters, is roughly 50%.
This
means that when we write English half of what we write is determined by the structure of the language and
half is chosen freely. The figure 50% was found by several independent methods which all gave results in
-this neighborhood. One is by calculation of the entropy of the approximations to English. A second method
is to delete a certain fraction of the letters from a sample of English text and then let someone attempt to
restore them. If they can be restored when 50% are deleted the redundancy must be greater than 50%. A
third method depends on certain known results in cryptography.
Two extremes of redundancy in English prose are represented by Basic English and by James Joyce’s
book “FinnegansWake”. The Basic English vocabulary is limited to 850 words and the redundancy is very
high. This is reflected in the expansion that occurs when a passage is translated into Basic English. Joyce
on the other hand enlarges the vocabulary and is alleged to achieve a compression of semantic content.
The redundancy of a language is related to the existence of crossword puzzles. If the redundancy is
zero any sequence of letters is a reasonable text in the language and any two-dimensional array of letters
forms a crossword puzzle. If the redundancy is too high the language imposes too many constraints for large
crossword puzzles to be possible. A more detailed analysis shows that if we assume the constraints imposed
by the language are of a rather chaotic and random nature, large crossword puzzles are just possible when
the redundancy is 50%. If the redundancy is 33%, three-dimensional crossword puzzles should be possible,
etc.

"Inace uslov za to jeste da manje od 50% ukupnih kombinacija cine random-like podaci." - dakle to se odnosi na "standardan (svakodnevni) Engleski" jezik, koji se za moj ukus isuvise cesto pojavljuje i kod Shannona i kod McKoj-a (Dejvida Mekkeja (David MacKay), (ona treca knjiga sto mi je filmil preporucio je i dalje malo nedostupna on-line i i dalje je malo skupa), I sta sad? Da svi citamo Jojsa? (Koji je za svoje vreme bio kao super, a ovih dana je kao bas zastareo i nije vise toliko atraktivan, kazu kriticari?).

The redundancy of a language is related to the existence of crossword puzzles. If the redundancy is
zero any sequence of letters is a reasonable text in the language and any two-dimensional array of letters
forms a crossword puzzle. If the redundancy is too high the language imposes too many constraints for large
crossword puzzles to be possible. A more detailed analysis shows that if we assume the constraints imposed
by the language are of a rather chaotic and random nature, large crossword puzzles are just possible when
the redundancy is 50%. If the redundancy is 33%, three-dimensional crossword puzzles should be possible,
etc.

3D ukrstenice ne postoje jer bi bile necitljive, kako da citas slova po dubini ako ih ona ispred zaklanjaju? (mada na danasnjim racunarima, ko zna?) ali zato postoje osmosmerke kako na srpskom tako i na engleskom, nesto kao 3D ukrstenica prilagodjena za 2D engine (papir, ekran). Inace redundansa "svakodnevnog" srpskog je oko 70% bar tako kazu nasi strucnjaci za jezik?

Citat:
ntojzan
Ako se budes malo vise posvetio izucavanju teme, shvatices da preko 99% kombinacija cine upravo random-like podaci, znaci svi pokusaji da se ti podaci kompresuju su unapred osudjeni na propast. Uopste nije bitno koji je algoritam u pitanju.


Ako bi mi verovao da sam se bas dosta do sada posvetio proucavanju teme i takoreci sagoreo, bas vise ne mogu, rekao bih i da sto se velicina fajla povecava da i random-like i random podaci zauzimaju jos vise mesta ali i da veoma optimizovan fajl (kao src, bin, exe) veoma lici na veoma random fajl tj. nema ili ima veoma malo redundanse (ponavljanja) nizova bita, ali cemu, lakse je reci "dokazano je da je nemoguce"? i kraj i tacka i ostalo...
[ Cola @ 04.09.2011. 11:14 ] @
Jako zanimljiva tema moram priznati :)

Sećam se kada sam ja na kraju srednje došao do iste ideje za kompresiju podataka :)
dva danan nisam mogao spavati imao sam osećaj da sam otkrio sasvim nešto novo.
Sve je super izgledalo na ogromnim fajlovima da ih kompresujem pomoću 'brojača'. Tako kompresovani podaci bi se o5 mogli kompresovati i tako u nedogled. I sve mi je lijepo funkcionilao dok se nisam spustio na manje brojebe i nikako mi nije bilo jasno kako ne mogu njih da kompresujem.

Npr 4 bita 16 kombinacija kako njih da upišem u 3 ili manje bita.
Onda sam se bacio na matematiku da riješim misteriju i riješio je: Početna ideja mi nije bila dobra jer je 'brojač' predstavljao sam podatak.

Ako ništa bar sam se ta da dana osjećao kao milioner, kao neko ko je izmislio teleport ili nešto što bi se sa tim moglo uporediti.
[ Nedeljko @ 06.09.2011. 10:14 ] @
Pa, ne možeš ni velike random-like fajlove da komprimiješ. Imao si gomilu brojača, koje si negde morao da pamtiš, jer bez njih nema dekompresije.

Nije nikakav problem "komprimovati" niz tako da se ne može posle dekomprimovati.
[ MajorFatal @ 07.10.2011. 16:58 ] @
Sejo se malo muci dok razmislja :) a i imao sam nekih privatnih obaveza ovih dana.

Cola:

Citat:
Cola: Jako zanimljiva tema moram priznati :)


Pa priznaj ako bas moras :) Hvala za pohvalu, medjutim da li je tema zanimljiva ili ne to je off topic, zar ne?

Citat:
Cola
Sećam se kada sam ja na kraju srednje došao do iste ideje za kompresiju podataka :)


Neverovatno! A ja na pocetku srednje! Mozda smo se sretali po hodnicima? Jesi li bio kad je dolazio onaj rock band? :) Tvoja secanja iz srednje skole su off topic zar ne? :)

Citat:
Cola
Sećam se kada sam ja na kraju srednje došao do iste ideje za kompresiju podataka :)


Eh, sad, bas do iste ideje? Zapravo mislim da pokusavas da maznes moju sjajnu ideju i gotovo resenje decenijskog problema. Za tebe i onog BiF-a prvi put cujem, da li ste negde objavljivali svoja zapazanja? Ovde na ES-u mi je prethodnik bio neki sale [link ako nadjem] cini mi se, ili sallle ili tako nekako, ne mogu sad da trazim po linkovima, naci cu, a koji je dobro opisao i psihicko stanje prilikom razresavanja ovog problema "neka ideja koja uhvati i ne pusta", kao sto vidis po datumima objavljivanja tema bavim se ovim vec godinama.





Citat:
Cola
dva danan nisam mogao spavati imao sam osećaj da sam otkrio sasvim nešto novo..


Nije to nista, ja jednom 7 dana nisam spavao i zaglavio sam u bolnicu zbog toga, nemoj to da radis.

Citat:
Cola
Sve je super izgledalo na ogromnim fajlovima da ih kompresujem pomoću 'brojača'. Tako kompresovani podaci bi se o5 mogli kompresovati i tako u nedogled. I sve mi je lijepo funkcionilao dok se nisam spustio na manje brojebe i nikako mi nije bilo jasno kako ne mogu njih da kompresujem..


Eh, bas pomocu 'brojaca'? Ali hvala ti sto si 'brojac' stavio pod navodnike. Nije brojac u bukvalnom smislu u pitanju a nadam se da je do sada postalo jasno sta podrazumevam pod 'brojac': bilo kakvu konstrukciju, niz tranzistora, flip-flopova, prostor na magnetnoj traci... bilo cega sto moze da cuva i promeni stanje koje bi oznacavalo stanje nule ili jedinice. Pod 'fajl' sam podrazumevao bilo kakav niz bita nula i jedinica, najcesce smislen za onaj engine koji bi mogao da ga cita, a besmislen ili random za neki drugi engine, ili od pocetka u potpunosti random file koji je, opet, najcesce malo tezi za napraviti.
Kao sto sam vec nekoliko puta pisao [link] postoji donja granica u broju bita koji cine sadrzaj fajla za mogucnost kompresije, ispod kojeg broja dolazi do ekspanzije umesto do kompresije.
O 05 i 05 http://www.elitesecurity.org/t151770-1#1010244 http://www.elitesecurity.org/t151770-2#1012083 sam takodje vec pisao u nekoliko navrata http://www.elitesecurity.org/t158990-0#1202828 tako da 05 sigurno necu. Nije brojebe nego brojeve :)
[ MajorFatal @ 07.10.2011. 16:58 ] @
Citat:
Cola
Npr 4 bita 16 kombinacija kako njih da upišem u 3 ili manje bita..


Nikako, ako mene pitas, ali i o mogucnosti/nemogucnosti kompresovanja 4 bita sam takodje vec pisao http://www.elitesecurity.org/t158990-0#1223880 (pri kraju posta) ako nista sad comp compres ima novo poglavlje: unapredili smo i "caunting" argument nasa verzija glasi: "ne mogu 4 goluba da se natrpaju u 3 rupe"? "Counting argument" iliti "Pingeon hole argument" zvuci dosta mudro dok je na engleskom i dok ne procitas o cemu se tamo radi a to je da neki ljudi u raspravi dokazuju da 16 golubova ne moze da se smesti u 15 za to predvidjenih rupa? To i ne zvuci kao neka mnogo razumna rasprava bar ne za odrasle ili razumne ljude, zar ne?

Sto se tice primera sa 'fajlovima' duzine 3 bita (i manje za 'kompresovane' 'fajlove') koji sam koristio na onoj drugoj temi [krlp2] to je samo ilustracija, koncept nesto sto bi trebalo da pomogne da dokazem da je moguce kompresovati i random-like fajlove tj. sve fajlove, pod odredjenim uslovima naravno.
Ako si pazljivo citao mogao si da primetis da su na 8. fajlova kracih po broju bita upotrebljenih za njihovo opisivanje 'pretekle' jos 2 kombinacije koje ja nisam naveo 0_0 i 1_1 (hvala Shadowed) medjutim dok je podloga po kojoj pisemo jos uvek papir a 'engine' koji cita podatke nase oko, mozak itd. ima jos nekih 'kombinacija' kojim mogu da se opisu ona dva poslednja fajla tj:

_0_ i
_1_ su takodje savrseno legalne kombinacije pod uslovom kad bi recimo pojedinacni biti ili mesta predvidjena za njihovo upisivanje mogli da se citaju ili tumace kao posebne kombinacije,
kao na primer kad bi ona tablica istinosnih vrednosti duzine 3. bila upisana u neku tabelu u relacionoj bazi podataka pa kad bi nad pojedinacnim bitima mogao da se primeni view (pogled) (i kad bi view uvek bio fiksne duzine bez obzirz nad kolikom kolicinom podataka je primenjen), kako za sada nisam siguran da je to moguce u praksi ne bih da to predlazem kao resenje za realizaciju ove kompresije i dekompresije.

Takodje:
0__ i
1__ su takodje legalne kombinacije, jedino ne mogu da se upotrebe
__0 i
__1 jer su vec navedene na spisku 'kracih' fajlova kao prve dve kombinacije [link], takodje vaze i sve kombinacije od 2 bita upotrebljena ali na drugim pozicijama:

00_
01_
10_
11_ ako pazljivo prebrojis trebalo bi da dobijes 15. kombinacija od dva i jedan bit na razlicitim pozicijama i jos 8. kombinacija od po 3. bita, zajedno (ukupno) 23. kombinacije dovoljno za svih 16. kombinacija od po 4. bita, ili preciznije za svih 16. kombinacija jednakih po duzini medjusobno.

Problem sa papirom kao 'podlogom' po kojoj pisemo i okom, mozgom, itd. kao 'enginom' koji cita je sto za ove potrebe ima malo nezgodnu osobinu a to je da ovaj put papir ne moze
najuspesnije da opise stanje u racunaru u tom trenutku, mogu da napisem 'mesto rezervisano za bit' ali u praksi to mesto je uvek popunjeno ili nulom ili jedinicom tako da...uglavnom iz tog razloga sam odabrao za opisivanje ona poslednja dva 'fajla' sa spiska svih fajlova odredjene duzine kombinacije:

0_1 i
1_0 jer mislim da ako bi neko pokusao da isprogramira ovo u praksi da bi mu bilo mnogo lakse da se organizuje onako kako sam napisao a to je: posto pojedinacni fajlovi na onom 'crtezu' koji sam prilozio u stvari predstavljaju cele, kompletne neke fajlove, crtez predstavlja da dva pojedinacna fajla (u ovom slucaju prava fajla bez navodnika) moraju biti razliciti i zajedno kraci po broju upotrebljenih bita od odgovarajucih (pripadajucih) fajlova u punoj duzini a koje hocemo da kompresujemo.

Nagovesto sam da je teren malo klizav i da je potrebna koncentracija.

Citat:
Cola
Onda sam se bacio na matematiku da riješim misteriju i riješio je: Početna ideja mi nije bila dobra jer je 'brojač' predstavljao sam podatak..


To vazi ( i 'countin argument' uopste ) za fajlove jednake medjusobno po 'duzini' tj. broju upotrebljenih bita a ako je i 'brojac' tako konstruisan, ali ako se bavis matematikom mozes slobodno da prilozis tu svoju racunicu u okviru ove teme :) bas me zanima kako si racunao nesto sto je zi:: svojevremeno ispisao u jednoj recenici http://www.elitesecurity.org/t93798-0#604994


Citat:
Cola
Ako ništa bar sam se ta da dana osjećao kao milioner, kao neko ko je izmislio teleport ili nešto što bi se sa tim moglo uporediti.


Dva dana :) A nisi se osjecao kao bilijarder? :) Kad isprogramiras softwer koji je ekvivalent 'filozofskom kamenu mudrosti' http://www.hutter1.net/ai/aixigentle.pdf mocice i teleport i vremeplov i djunta sa sitnim nutom, naravno to nek ti uradi onaj ko ti je rekao da moze :)
[ MajorFatal @ 07.10.2011. 16:59 ] @
Citat:
Nedeljko: Pa, ne možeš ni velike random-like fajlove da komprimiješ. Imao si gomilu brojača, koje si negde morao da pamtiš, jer bez njih nema dekompresije.

Nije nikakav problem "komprimovati" niz tako da se ne može posle dekomprimovati.


Zasto bi pamtio sve 'iteracije' do kojih je dolazilo u medjuvremenu ako ti uvek isti algoritam daje uvek iste rezultate pocevsi od istih pocetnih vrednosti? Zasto bi pamtio gomilu brojaca?

Dovoljna ti je bilo koja iteracija do koje bi dolazilo u medjuvremenu i algoritam tj.program za kompresiju/dekompresiju? Polazis od prvog random (ili random-like fajla) Rf1 velicine 100.000 bajta, primenjujes na njega algoritam bzip2 (ili neki drugi ) nazvacemo ga A1 (algoritam1) dobices veci fajl od pocetnog koji je najverovatnije ponovo random strukture bar gledajuci iz ugla bzip2 tj. A1 tj. primenjenog algoritma, novi fajl je velicine 100.807 bajta, nazvacemo ga Rf2 (random fajl 2), ponovo bzip2 (A1) dobices Rf3 (jos veci od pocetnog i od Rf2 primeti i da imas prirastaj jer pocevsi od 100.807 uvecanje za recimo 10% je vece (u broju bajtova) nego kad kreces od 100.000 bajta) itd... ponovo bzip2 vise puta dobijaces sve vece fajlove koji su takodje random strukture Rf4, Rf5, Rf6.. Rf1000. 1000.- ti fajl po redu bi mogao da ima i milion bajta ili vec zavisi od toga koliko puta je primenjen bzip2. Ako bi postojao inverz algoritma bzip2 (A2 recimo) i ako bi nam Rf1000 fajl od milon bajta bio pocetni fajl random strukture uz pomoc inverza bzip2 (A2) mogli bi smo uz dovoljan broj primena tog algoritma da smanjimo Rf1000 na Rf1, tj sa milion bajta na 100.000 bajta, jedino sto ne bi mogli je da idemo ispod 100.000 bajta jer niko ne garantuje da bi inverz bzip2 (A2) bio uspesan nad takvim rasporedom bita u Rf1, takodje u nekom trenutku neki od predvidjenih random fajlova recimo Rf538 bi mogao da ima takav raspored bita koji lici na neku uredjenu strukturu ili je jako slican fajlu pogodnom za statisticke nacine kompresije, u tom slucaju bzip2 ce da odradi svoj posao kako treba i Rf539 ce biti manji od Rf538, mada verovatnoca da se desi ovako nesto je veoma mala mada nije ni nemoguce...

Medjutim, posto ovo skoro pa nista ne dokazuje osim da je pojedine random fajlove (Rf1000) moguce kompresovati i to pod uslovom da postoji bzip2 inverz, da ne bi gurali raspravu u pogresnom smeru...
[ MajorFatal @ 07.10.2011. 17:00 ] @
Na primer 'sadrzaj fajla' tj. duzina 7. bita. Uglaste zagrade 'glume' fajl sistem: Pokusacu da dokazem da je moguce nacinom koji sam predlozio kompresovati sve fajlove iz jednog opsega i ujedno da predlozim nacin za izvodjenje toga u praksi na danasnjim racunarima sa danasnjim fajl sistemima: Svih 'fajlova' duzine 7.bita ima tacno 2^7 tj. 128. fajlova sve ukupno.
126. 'fajlova' se moze zameniti kombinacijama bita duzine 1., 2., 3. .. 6. bita jer: 2^1=2 + 2^2=4 + 2^3=8 + .. 2^6=64 = 126. Preostala dva 'fajla' duzine 7. bita (a pod rednim brojevima 127. i 128.) mogu se 'zameniti' (kompresovati, kodovati...) sa po dva fajla duzine 1. bit a da pri tom oba ta fajla budu jasno razgraniceni od strane fajl sistema odnosno operativnog sistema pod kojim se to radi:

Slikom:

1.) [0000000] -> [0]
2.) [0000001] -> [1]
3.) [0000010] -> [00]
4.) [0000011] -> [01]
5.) [0000100] -> [10]
6.) [0000101] -> [11]
7.) [0000110] -> [000]
itd...
.
.
.
125.) [1111100] -> [111110]
126.) [1111101] -> [111111]
-----------------------------------
127.) [1111110] -> [1][0]
128.) [1111111] -> [0][1]

Da ne pisem bas svih 128. kombinacija od po 7. bita :) Svaki fajl ima svoj 'heder' i 'futer' (pocetak i kraj). Dakle za svih 128. razlicitih kombinacija bita duzine 7. tj. 'fajlova' duzine 7. bita pronadjeno je 128. razlicitih kombinacija kracih po broju upotrebljenih bita. Ima 126. 'jednostrukih' fajlova i dva 'dupla' fajla ( koji se sastoje od po dva 'fajla' duzine 1. bit ).
[ MajorFatal @ 07.10.2011. 17:01 ] @
7. bita za 'sadrzaj fajla' je odabrano da bi za 'poslednja 2' 'fajla' moglo da se napise i ovako:


-----------------------------------
127.) [1111110] -> [[1][0]]
128.) [1111111] -> [[0][1]]

Sada su i 'poslednja 2' 'fajla' zapakovana u svoje zagrade i potencijalni engine moze da ih razgranici od okoline kao posebne fajlove a da unutra pronadje po dva posebna fajla.
Za sada vizuelno deluje da ima kompresije jer je na spisku fajlova sa desne strane svaki zapis kraci, medjutim dve uglaste zagrade ako bi bile deo nekog fajl sistema mogle bi da budu 'teske' i 15Kbita recimo, u tom slucaju ako bi neko racunao gde je donja granica u velicini fajlova za postojanje ovakve kompresije morao bi da uzme u obzir da su sa desne strane upotrebljena tri para zagrada tj. 2 * 15Kbit (zagrade) + 7 bita bi morala biti najmanja velicina (duzina) 'sadrazaja fajla' koji moze da se kompresuje.


[Ovu poruku je menjao MajorFatal dana 07.10.2011. u 18:26 GMT+1]

[Ovu poruku je menjao MajorFatal dana 07.10.2011. u 18:27 GMT+1]
[ MajorFatal @ 19.10.2011. 10:08 ] @
Ona 'poslednja 2' fajla bi mogla da se koduju (kompresuju) i ovako:

127.) [1111110] -> [ ]
128.) [1111111] -> [ [0]]

1 'prazan fajl' tj. samo heder i futer bez 'sadrzaja' u bitima i jedan fajl sa sadrzajem od 1. bita koji je opet zapakovan u veci fajl, tada bi donja granica kompresije bila na 15Kbita + 7. bita (samo 1 par zagrada tj. heder, futer zapakovani u fajl u slucaju drugog fajla) ali za potrebe objasnjavanja eventualne izvedbe ove kompresije u praksi ja ipak predlazem 'duple' ili bolje reci 'visestruke' fajlove kao u prethodnim postovima.
[ MajorFatal @ 19.10.2011. 10:09 ] @
U iskrenoj nadi da prethodne redove neko nije protumacio kao da tvrdim da 7. bita moze da se kompresuje...

Posle ovoga jedino sto jos preostaje da se vidi je da li odredjeni OS i fajl sistem podrzavaju (omogucavaju) postojanje fajlova duzine samo 1 bit (zbog duplih 'fajlova' na crtezu sa desne strane ciji je sadrzaj po dva fajla velicine 1 bit ), ukoliko to nije slucaj tj. ukoliko i tu postoji neka donja granica u velicini fajla na primer X bita (mogu da pretpostavim recimo da je 1 bajt najmanja moguca velicina fajla na nekom fajl sistemu ako je tako bilo lakse za izvedbu ljudima koji su ga pravili) u tom slucaju broj bita potreban za obelezavanje 2 para uglastih zagrada (tj. dva hedera i futera za pojedinacne fajlove) + 2X (velicina sadrzaja u bitima 2 fajla sa desne strane zapakovana u 1 'dupli' fajl) + 7 bita bi bila donja granica za velicinu sadrzaja fajla koji moze da se kompresuje ovom metodom. SVAKOG fajla iznad te granice.
[ BiF @ 20.10.2011. 16:42 ] @
Bespotrebno kompliikujes sa file-sistemom.
Na kraju sve moras da svedes na nule i jedinice: nema uglastih zagrada, razmaknica itd.
Otvori notepad, otkucaj jedno slovo, i snimi taj fajl na disk, pa onda idi na properties tog fajla. Obrati pažnju na "Size" i "Size on disk"

Pozdrav i želim ti sve najbolje u kompresiji.
[ Stijak @ 27.10.2011. 00:27 ] @
he he he - smiješno mi sve ovo... Kao što ti neko već reče kakve uglaste zagrade - kakve gluposti - sistem pamti samo nule i jedinice... Čak i kada je sadržaj fajla manji - moraš uzeti koliko podataka zapamti file sistem vodeći računa o tim file-ovima... I da su podaci u nekom nizu nula jedinica i ti tu moraš skontati šta je nula, šta je jedinica, šta je početak file-a šta kraj, kako se koji file zove i gdje se nalazi... Kod ovog tvog sistema kompresije sedam bitova ničega toga nema - sem što si lupio neke uglaste zagrade... I ti sad misliš da bi kod većih brojeva došlo do kompresije - tj. težina file sistema postala manja - ali ne baš...

Inače - ako zanemariš podatke koji se nalaze u file sistemu - evo ti odličnog kompresionog algoritma - snimaš u file-ove samo jedinice - kada se god pojavi nula - file na tom mjestu presječeš i povećaš numeraciju kojom označavaš te file-ove... Dekompresor kasnije samo spoji te file-ove i doda koliko nula treba...

Znači ako su kompresovani fileovi ekstenzije data 10110001011110100 kompresuješ kao 1.data u kome se nalazi 1, 2.data u kome se nalazi 11, 5. data u kome se nalazi 1, 6.data u kome se nalazi 1 7.data u kome se nalazi 1111 i 8.data u kome se nalazi 1 i 10.data koji je prazan... To onda možeš pojednostaviti pišući samo broj jedinica - pa ti npr. 7.data ti bude 100 (binarna četvorka za 4 jedinice) - pa to možeš pojednostaviti i npr umjesto 7.data pisati 7.1.data u kome je 1 i 7.3.data koji je prazan... i tako od 19 bitova dobiješ samo 5... He he - a praveći sve ove file-ove si potrošio nekoliko kilobajta u filesistemu (što se ne može teorijski izbjeći, ali se može umanjiti - i u najboljem slučaju bi opet bilo više nego ovih 11 bite-ova koliko je razlika) i ko zna koliko još u zaokružavanju file-ova u sektore.

Ili još bolji sistem - podatke napišeš u imena praznih file-ova i pretvoriš ogroman file kompresijom u ništa... pa ovaj moj file gore snimiš kao 10110001011110100.data (može i efikasnije u hex ili nekom jačem encoding-u - ali nije sad bitno - i ako je previše za jedno ime - podjeliš i smisliš način da ih numerišeš... ;) Kako je ovo dobro ;) Čak i kada ideš na propertires piše file on disk 0! Ha ha ha - mislim da sam nadmašio tvoju ideju...

A inače - ne kontam zašto ti treba pomoć drugih - ne treba ti ni program za to - treba ti samo moćan digitron koji može da radi sa velikim brojevima takav ti je i windowsow, imaš ih po netu koliko hoćeš, imaš jedan na http://www.wolframalpha.com/ (samo treba naučiti komande... Iznalupaš se cifara - da bude dovoljno dugačak da bi tvoja metoda radila (preko 32 - da dobiješ neki kvazirandom broj i pokušaš skontati način da to kompresuješ svojom metodom......

Znači naprimer 1307652984 (mada će tebi trebati veći brojevi) izvadiš logoritam po dva, pa skontaš koloko ti je još ostalo, pa logoritam od ostatka po 3, pa sve tako i ručno to sve središ - zapišeš brojeve koje moraš zapamtiti poslije kompresije - to bi bili cjelobrojne vrijednosti ovih logoritama... I vidiš da li je to duže ili kraće od originala... Koliko kontam ti bi file skraćivao kao 1^x + 2^y + 3^z +... pa moraš pamtiti ove x,y,z...

[Ovu poruku je menjao Stijak dana 27.10.2011. u 01:56 GMT+1]
[ MajorFatal @ 17.12.2011. 00:47 ] @
Al' sam zabagovo ;) vise od mesec dana za 1. odgovor...

Citat:
BiF: Bespotrebno kompliikujes sa file-sistemom.
Na kraju sve moras da svedes na nule i jedinice: nema uglastih zagrada, razmaknica itd.
Otvori notepad, otkucaj jedno slovo, i snimi taj fajl na disk, pa onda idi na properties tog fajla. Obrati pažnju na "Size" i "Size on disk"

Pozdrav i želim ti sve najbolje u kompresiji.


Citat:
BiF: Bespotrebno kompliikujes sa file-sistemom.


1.) U ovoj poruci: http://www.elitesecurity.org/t158990-1#2890236 sam pokusao da na najjednostavniji i najkraci nacin izlozim ideju pa ako mislis da nije mnogo komplikovano, u svakom slucaju ne pominje se fajl sistem.

2.) Mozda bespotrebno komplikujem sa fajl sistemom, ali kako da fajlove razdvojim od fajl sistema, engine-a koji ih cita, kompresora/dekompresora, os-a? Bez toga ni fajl ne postoji vec je samo gomila nabacanih bita? U svakom slucaju za 2^N - 2 fajlova jednakih duzina moguce je naci 2^N - 2 kombinacije bita krace po duzini. Preostaju jos 2 fajla koja ne moraju da dozive ekspanziju vec mogu da ostanu iste duzine kao i originalni fajlovi koje bi trebalo da zamene. Za sve duzine fajlova iznad 8. bita to je vise od 99,9% fajlova koji se mogu kompresovati i manje od 0,1% fajlova koji ne mogu. Sa povecanjem broja bita koji ucestvuju u duzini fajla, procenat fajlova koji ne bi mogli da se kompresuju meri se promilima pa jos manjim delovima procenta...

3.) Do uvodjenja zagrada da glume fajl sistem je doslo tako sto sam u jednom trenutku pogresio i poceo da poredim duzinu 'dvostrukih' fajlova sa sadrzajem 'jednostrukih' a takodje 'kompresovanih' umesto sa originalnim, i tako sto je Nedeljko nesto sto je trebalo da ilustruje fajl protumacio kao kodnu rec, i tako sto cim sam napisao space izmedju 2 'fajla' ljudi su pozeleli da ga koduju i tako sto...

Citat:
BiF
Na kraju sve moras da svedes na nule i jedinice: nema uglastih zagrada, razmaknica itd.


Za pocetak evo ti par uglastih zagrada i razmaknica: [ ] [[ ] ]], znaci ima ih, onda definisi to "sve" koje pominjes jer ne verujem da si mislio i na nebo i na oblake kao u onom filmu "Matrix", te takodje svi podatci na kompjuteru su vec u vidu nula i jedinica tako da je i taj deo price odradjen.

Citat:
BiF: Otvori notepad, otkucaj jedno slovo, i snimi taj fajl na disk, pa onda idi na properties tog fajla. Obrati pažnju na "Size" i "Size on disk"


Hvala za savet ali samo si jos zaboravio da kazes sta bi trebalo da zakljucim iz tog malog eksperimenta? Size: 1. byte, Size on disk: 8. KB (kodovanje ASCII jelte), ako izbrisem i to jedno slovo: Size: 0. byte, Size on disk: 0. byte (sto je nemoguce jer negde moraju da postoje podaci i da postoji fajl i da je txt ekstenzije i gde sam ga snimio itd...), ako upisem 2. slova: Size: 2. bytes, Size on disk: 8. KB (i dalje, isto kao kad je jedno slovo u pitanju) ali ako dva fajla od po 1. slovo tj. 1. byte snimim u folder velicina foldera nece biti 8KB kao sto sistem rezervise za fajl velicine 2. bajt-a, vec 16 KB (duplo vise) sto znaci da moraju da budu razdvojeni fajlovi svaki posebno i da se svakom posebno pristupa sto opet znaci da bi donja granica velicine kompresovanog fajla morala da bude 16 KB + 1 byte ako bi se radilo na windousima i ako bi velicinu foldera sa dva fajla unutra poistovetili sa 'spoljasnjim' uglastim zagradama koje sam nacrtao oko ona dva 'dvostruka fajla' na jednom od skorasnjih 'crteza' tj. to bi bila i najmanja moguca duzina sadrzaja originalnog fajla koji moze da se kompresuje...

Citat:
BiF: Pozdrav i želim ti sve najbolje u kompresiji.


Hvala! Hvala i sto se nisi naljutio za onu 'prozivku' od pre par poruka ("nisam cuo za BiF-a" ;) drago mi je da upoznam 'kolegu', ako me sta cudi da nema i vise ljudi koji su se bavili ovom problematikom, meni je ovo tako zanimljiva glavolomka da me vec godinama drzi.
[ Mihajlo Cvetanović @ 17.12.2011. 17:25 ] @
Apsolutno sve na hard disku mora da se pretvori u namagnetisane čestice koje drže informaciju. Jedna namagnetisana čestica može da drži samo jedan bit informacije, to jest jedna čestica može da predstavlja ili nulu ili jedinicu. Čestica ne može da predstavlja ni otvorenu ni zatvorenu zagradu, niti bilo šta drugo što nije nula ili jedinica. Da bi predstavio i svoje zagrade i bilo šta drugo u fajl sistemu moraš nekako da ih konvertuješ u niz nula i jedinica. Ne možeš da preskočiš tu konverziju simbola u niz nula i jedinica, jer se na hard disku fizički vide samo nule i jedinice.

Niko se nije bavio ovim problemom na ovaj način, jer problem ne može da se reši na taj način. Kome god da ispričaš svoje rešenje reći će ti isto. To nije rešenje.
[ MajorFatal @ 18.12.2011. 15:36 ] @
Jasno mi je to ali mi nije jasno iz cega si ti zakljucio da ja ne mislim da je tako? U ovoj poruci http://www.elitesecurity.org/t151770-5#2966226 sam napisao da svi oni podaci koje sam ilustrovao zagradama mogu da imaju i 15 KB podataka tj. sve ono sto ne spada u sadrzaj fajla tj. sluzi kao opis fajla ili nacina raspakivanja, bzip2 fajl ima 4. uvodna bajta koja sluze tome, takodje sam objasnio kako bi taj deo fajla ucestvovao u ukupnoj racunici, zagrade su tu samo da ilustruju da ako originalni fajl ima zaglavlje ima i kompresovani pa se porede ili samo sadrzaji tih fajlova ili svi ukupni podaci koji ucestvuju prilikom raspakivanja fajla, ali zaista je nebitno, za 99% fajlova moguce je naci krace ekvivalente, za ona preostala dva bitno je da ne mora da dodje do ekspanzije dakle kompresija random fajlova je moguca ili bar moguca za 99% fajlova.
[ Mihajlo Cvetanović @ 18.12.2011. 19:57 ] @
Izvini, izgubio sam te.
[ Nedeljko @ 18.12.2011. 22:12 ] @
Slušaj ovako:

Ako želiš da komprimuješ proizvoljan niz bitova tako da se posle komprimovani oblik može dekomprimovati i dobiti original, onda različitim nizovima bitova na ulazu moraju odgogvarati različiti nizovi bitova na izlazu.

Ako želiš da komprimovani oblik nikada ne bude duži od nekomprimovanog, onda

prazan niz bitova moraš komprimovati njime samim.

Nizova dužine 1 ima 2. Obzirom da si na komprimovanje praznog niza već potrošio prazan niz, ostaje ti da nizove dužine 1 komprimuješ nizovima dužine 1, čime ćeš i njih sve potrošiti.

Nizova dužine 2 ima 4. Obzirom da si nizove dužine ne veće od 1 već potrošio, nizove dužine 2 moraš komprimovati nizovima dužine 2. Time ćeš i njih sve potrošiti.

Nizova dužine 3 ima 8. Obzirom da si nizove dužine 2 i manje već potrošio, nizove dužine 3 moraš komprimovati njima samima, čime ćeš i njih sve potrošiti.

I tako dalje.

Stoga bilo kakva transformacija koja dopušta vraćanje originala i koja ne produžava nijedan niz bitova, neće nijedan niz bitova skratiti.
[ MajorFatal @ 19.12.2011. 18:00 ] @
Citat:
Mihajlo Cvetanović: Izvini, izgubio sam te.


Ma nema problema.

Citat:
Nedeljko: Slušaj ovako:

Ako želiš da komprimuješ proizvoljan niz bitova tako da se posle komprimovani oblik može dekomprimovati i dobiti original, onda različitim nizovima bitova na ulazu moraju odgogvarati različiti nizovi bitova na izlazu.


Ne! Ne zelim! Ne zelim da komprimujem proizvoljan niz bitova tako da se posle komprimovani oblik može dekomprimovati i dobiti original, vec mislim da je moguce komprimovati 99,9% proizvoljnih nizova bita koji su duzi od odredjene granice u duzini niza bita tako da se posle komprimovani oblik može dekomprimovati i dobiti original.

Citat:
Nedeljko:  onda različitim nizovima bitova na ulazu moraju odgogvarati različiti nizovi bitova na izlazu.


...i kraci da bismo to mogli nazvati kompresijom.

Citat:
Nedeljko
Ako želiš da komprimovani oblik nikada ne bude duži od nekomprimovanog, onda

prazan niz bitova moraš komprimovati njime samim.

Nizova dužine 1 ima 2. Obzirom da si na komprimovanje praznog niza već potrošio prazan niz, ostaje ti da nizove dužine 1 komprimuješ nizovima dužine 1, čime ćeš i njih sve potrošiti.

Nizova dužine 2 ima 4. Obzirom da si nizove dužine ne veće od 1 već potrošio, nizove dužine 2 moraš komprimovati nizovima dužine 2. Time ćeš i njih sve potrošiti.

Nizova dužine 3 ima 8. Obzirom da si nizove dužine 2 i manje već potrošio, nizove dužine 3 moraš komprimovati njima samima, čime ćeš i njih sve potrošiti.

I tako dalje.


Kao sto rekoh, ne zelim, al ajde, ...itd nizova duzine 4 ima 16, nizova duzine N ima 2^N, ali ako bih uveo granicu za mogucnost kompresije recimo na 7 KB jer pretpostavljam da nikad niko ne bi otkucao 1 slovo u notpedu pa posle toga jos pozeleo da ga sacuva i kompresuje, nizova duzine krace od te granice ima: 2^7000 + 2^6999 +2^2998 + .. + 2^1 + 2^0 = mnogo, znaci svi oni ne bi mogli da budu komprimovani a svi nizovi bita iznad te granice duzine bita bi mogli kao sto danas popularnim metodama mogu da budu komprimovani nizovi koji nisu random a ne mogu oni koji su random ili random like.

Citat:
Nedeljko: Stoga bilo kakva transformacija koja dopušta vraćanje originala i koja ne produžava nijedan niz bitova, neće nijedan niz bitova skratiti.


Kao sto rekoh vise puta tokom ove tri rasprave koje sam pokrenuo produzavace nizove bita krace od odredjene granice a komprimovace one duze od te granicne vrednosti...
[ BiF @ 08.01.2012. 17:06 ] @
primer sa notepad-om pokazuje da ti se vise isplati da kompresovane podatke ubacis u jedan file, a ne u vise file-ova (2, 5, 50,...), jer ces tako ustedeti prostor. sto se tice uglastih zagrada i razmaknica, naravno da postoje u smislu u kom si ih ti naveo. hteo sam da ti kazem da i te uglaste zagrade i razmaknice moras da pretvoris u nule i jedinice.
[ MajorFatal @ 06.02.2012. 16:48 ] @
Citat:
Stijak:
he he he - smiješno mi sve ovo...

A meni nimalo.

Citat:
Stijak:
Kao što ti neko već reče kakve uglaste zagrade - kakve gluposti - sistem pamti samo nule i jedinice...


Rece BiF, ali izgleda da se nismo bas najbolje razumeli, ne zelim ja da u niz bita utaknem i poneku uglastu zagradu, svestan sam da bi i ta zagrada morala biti kodovana nulama i jedinicama, zagradama sam samo hteo da ilustrujem postojanje zaglavlja u kompresovanom fajlu i to da i taj deo fajla nosi neku kolicinu informacija te zauzima neki prostor te se mora uzeti u obzir kada se razmatra da li bi kompresija mogla da postoji ili ne, a ako da, u kolikoj meri, hvala ti za epitet, nisu gluposti nego pametne, mudre i skoro pa genijalne stvari ali si ti tupav jadan pa posto ne razumes cini ti se da su gluposti u pitanju, a "sistem" nek pamti sta hoce.

Citat:
Stijak:
Čak i kada je sadržaj fajla manji - moraš uzeti koliko podataka zapamti file sistem vodeći računa o tim file-ovima...


Negde je fajl napisano tako, a ponegde kao 'fajl' pod znacima navoda pa obrati paznju...dakle nisu uvek fajlovi u bukvalnom smislu te reci u pitanju, pogotovo ne takvi da bi OS mogao ili morao da ih vidi kao fajlove. Verovatno je na tim mestima trebalo da koristim izraz: 'niz bita'.

Citat:
Stijak:
I da su podaci u nekom nizu nula jedinica i ti tu moraš skontati šta je nula, šta je jedinica, šta je početak file-a šta kraj, kako se koji file zove i gdje se nalazi...


Pa recimo ako bih imao niz od 20. bita a u zaglavlju takvog fajla podatak: 7,5,8. znao bih da se u nizu od 20. bita krije 3. "fajla" od po 7. bita, 5. bita i 8. bita, "sistem" ne mora da ima nista sa tim ovo bi dekompresor morao da zna, da pravilno protumaci i dekompresuje fajl, a taman posla da im svima dajem imena.

Citat:
Stijak:
Kod ovog tvog sistema kompresije sedam bitova ničega toga nema - sem što si lupio neke uglaste zagrade...


Sistem kompresije 7. bitova?? Lupio??? Opet ti hvala za epitet. Kad te lupim videces sve zvezde i "sistem kompresije sedam bitova" tamo gde ga nema :) Vrati se na ovu poruku: http://www.elitesecurity.org/t151770-5#2974005 i procitaj pocetak poruke, i sad kao u monopolu nekoliko polja (poruka) unazad i eto te u zatvoru, sad ti treba 2. sestice da bi izasao.

Citat:
Stijak:
I ti sad misliš da bi kod većih brojeva došlo do kompresije - tj. težina file sistema postala manja - ali ne baš...


Pa sad, to sam ja slucajno imao notepad na kompu pa su rezultati ispali takvi kakvi su, ali da sam recimo imao Blender i otvorim dokument upisem 1. slovo i sacuvam, pa odem na propretis: Size: 67. KB, Size On Disk: 68. KB, kao sto vidis sa povecanjem fajla kolicina osnovnih podataka koji su potrebni za opisivanje atributa tog tog fajla postaje zanemarljivo mala u odnosu na velicinu samog fajla, tj. 1KB na 67KB, a za 1.bit je bilo 7KB.
[ MajorFatal @ 06.02.2012. 16:48 ] @
Citat:
Stijak:
Inače - ako zanemariš podatke koji se nalaze u file sistemu -

Ne zanemarujem nego bas naprotiv uzimam u obzir.

Citat:
Stijak:
evo ti odličnog kompresionog algoritma - snimaš u file-ove samo jedinice - kada se god pojavi nula - file na tom mjestu presječeš i povećaš numeraciju kojom označavaš te file-ove... Dekompresor kasnije samo spoji te file-ove i doda koliko nula treba...


Bas je odlican, samo... koliko nula treba dodati? Moras i taj podatak da pamtis ako hoces da rekonstruises originalni fajl.
Deluje mi kao da si hteo da niz bita razdvojis na mnogo manjih "fajlova" koji su svi iste strukture ispred nule pa ih slede jedinice i da onda otseces sve "leading zero" (vodece nule) ali ovde nule ne ucestvuju samo kao brojcana vrednost nego su neka kodirana informacija tako da ne mozes tek tako da ih odseces ili bar ne a da ne znas (ne pamtis) koliko ih je bilo, a informacija koliko je nula bilo bi opet zauzimala neki prostor u kompresovanom fajlu.
I to nije jedini deo rezona koji ne valja kod tvog predloga, cak i da mogu da se zanemare podaci koji su predvidjeni da ih procita file sistem i da ne moras da pamtis broj nula koje si odsekao sta ces sa fajlovima koji imaju mnogo vise jedinica nego nula? Recimo fajl se sastoji od 98% jedinica i samo 2% nula, iskoriscenje za takav fajl kod ovog tvog predloga bi bilo 2% tj. fajl bi kompresijom skratio za samo 2%. Inace pravljenje vise fajlova na mesto jednog ne mora uvek da bude problem, ima fajlova za koje bi zamena bila samo 2 nova fajla recimo, a u vezi ovog tvog sistema "najnezgodniji" fajl bi bio strukture 01010101... itd tj. naizmenicno nule i jedinice bas bi bilo mnogo seckanja na manje fajlove duzine 1. bit.
Inace bas mi nije jasna logika kojom si se vodio kad si ovo napisao, recimo da mozes da zanemaris podatke koje potrosi svaki fajl u file sistemu i da tebi neko kaze: "evo ti odlicnog kompresionog algoritma - snimas u file-ove samo nule - kad god se pojavi jedinica - file na tom mestu preseces i povecas numeraciju kojom oznacavas te file-ove...Dekompresor kasnije samo spoji te file-ove i doda koliko jedinica treba..."? sta bi mu rekao tj. zasto nije moguce tako?[/quote]

Citat:
Stijak:
Znači ako su kompresovani fileovi ekstenzije data 10110001011110100 kompresuješ kao 1.data u kome se nalazi 1, 2.data u kome se nalazi 11, 5. data u kome se nalazi 1, 6.data u kome se nalazi 1 7.data u kome se nalazi 1111 i 8.data u kome se nalazi 1 i 10.data koji je prazan... To onda možeš pojednostaviti pišući samo broj jedinica - pa ti npr. 7.data ti bude 100 (binarna četvorka za 4 jedinice) - pa to možeš pojednostaviti i npr umjesto 7.data pisati 7.1.data u kome je 1 i 7.3.data koji je prazan... i tako od 19 bitova dobiješ samo 5... He he - a praveći sve ove file-ove si potrošio nekoliko kilobajta u filesistemu (što se ne može teorijski izbjeći, ali se može umanjiti - i u najboljem slučaju bi opet bilo više nego ovih 11 bite-ova koliko je razlika) i ko zna koliko još u zaokružavanju file-ova u sektore.


Dva puta si "pojednostavio" 7.data pa ti to nece raditi :) Tvoj sistem kompresije 7. bita je isuvise dobar, moras da smislis neki malo manje efikasan da bi radio :)

Citat:
Stijak:
Ili još bolji sistem - podatke napišeš u imena praznih file-ova i pretvoriš ogroman file kompresijom u ništa... pa ovaj moj file gore snimiš kao 10110001011110100.data (može i efikasnije u hex ili nekom jačem encoding-u - ali nije sad bitno - i ako je previše za jedno ime - podjeliš i smisliš način da ih numerišeš... ;) Kako je ovo dobro ;) Čak i kada ideš na propertires piše file on disk 0! Ha ha ha - mislim da sam nadmašio tvoju ideju...


Naravno da jesi. Da i ja nekom jednom kazem: "Tvoja ideja je vec obradjena na comp.compress" :)

This assumes of course that the information available to the decompressor is
only the bit sequence of the compressed data. If external information such as a
file name, a number of iterations, or a bit length is necessary to decompress
the data, the bits necessary to provide the extra information must be included
in the bit count of the compressed data. Otherwise, it would be sufficient to
consider any input data as a number, use this as the file name, iteration count
or bit length, and pretend that the compressed size is zero. For an example of
storing information in the file name, see the program lmfjyh in the 1993
International Obfuscated C Code Contest, available on all comp.sources.misc
archives (Volume 39, Issue 104).
[ MajorFatal @ 06.02.2012. 16:50 ] @
Citat:
Stijak:
A inače - ne kontam zašto ti treba pomoć drugih - ne treba ti ni program za to - treba ti samo moćan digitron koji može da radi sa velikim brojevima takav ti je i windowsow, imaš ih po netu koliko hoćeš, imaš jedan na http://www.wolframalpha.com/ (samo treba naučiti komande... Iznalupaš se cifara - da bude dovoljno dugačak da bi tvoja metoda radila (preko 32 - da dobiješ neki kvazirandom broj i pokušaš skontati način da to kompresuješ svojom metodom......


Da, da, caskom cu da proverim sve brojeve vece od 2^32.
Nema potrebe sada je tu najmocniji digitron: Nedeljko, on ima sistem kako da svaki rezultat svakog zadatka sve de na 42. tako da ce biti:
Fajl proizvoljne duzine i sastava x (puta) Nedeljkova racunica = 42. (bita, duzina fajla :)

Citat:
Stijak:
Znači naprimer 1307652984 (mada će tebi trebati veći brojevi) izvadiš logoritam po dva, pa skontaš koloko ti je još ostalo, pa logoritam od ostatka po 3, pa sve tako i ručno to sve središ - zapišeš brojeve koje moraš zapamtiti poslije kompresije - to bi bili cjelobrojne vrijednosti ovih logoritama... I vidiš da li je to duže ili kraće od originala... Koliko kontam ti bi file skraćivao kao 1^x + 2^y + 3^z +... pa moraš pamtiti ove x,y,z...


Clan 1^x cu sigurno da zadrzim :) on ce mnogo da doprinese kompresovanom obliku fajla :)

Citat:
BiF: primer sa notepad-om pokazuje da ti se vise isplati da kompresovane podatke ubacis u jedan file, a ne u vise file-ova (2, 5, 50,...), jer ces tako ustedeti prostor.

U jedan fajl je i ubaceno i taj jedan sam nazvao "visestruki" (dvostruki) jer se pojedini delovi niza bita u njemu tumace kao posebne dodatne kombinacije.

Citat:
BiF
sto se tice uglastih zagrada i razmaknica, naravno da postoje u smislu u kom si ih ti naveo. hteo sam da ti kazem da i te uglaste zagrade i razmaknice moras da pretvoris u nule i jedinice.

Umesto uglastih zagrada tamo gde sam ih pisao zamisli nizove bita kakve hoces i koliki ti odgovaraju za opisivanje kompresovanog fajla i sve je ok.
Kad tu kolicinu bita saberes plus "sadrzaj" fajla dobices donju granicu velicine kompresovanog fajla. Kad mogu windousi da naprave folder i da u njemu dva posebna fajla i da sve to bude 16KB mozes i ti kompresovan fajl u kome ce biti dva posebna "fajla", ako je najmanji moguci prostor koji bi takvo sto zauzimalo 16KB najmanji moguci fajl koji bi mogao da se kompresuje na taj nacin bio bi dugacak 16KB + 1. bit.
[ Nedeljko @ 06.02.2012. 20:44 ] @
Pisao ti reč "fajl" pod znacima navoda ili ne, on mora biti zapamćen na fizičkom nosiocu, a taj fizički nosilac je konačan niz bitova, koji mogu menjati vrednost. Napravi ti svoj fajl sistem, kakav god hoćeš, ali ćeš morati da znaš gde jedan fajl počinje, a gde se završava itd. Za to su takođe potrebno da budu zabeležene neke dodatne informacije. To sve moraš uzeti u obzir, tako da ako ti ne odgovaraju postojeći fajl sistemi, onda prvo opiši svoj.

Dakle, imaš dva diska. Na jednom je tačno jedan fajl koji zajedno sa svim pratećim informacija zauzuma m bitova. Drugi disk je potpuno slobodan. Treba ti program koji će sadržaj prvog diska da upiše na drugi disk tako da se na osnovu sadržaja drugog diska može restaurirati sadržaj prvog diska, ako bi se recimo taj sadržaj obrisao. Pritom će sadržaj drugog diska zauzimati n bitova zajedno sa svim fajlovima i ostalim potrebnim informacijama. Ti tvrdiš da to možeš da uradiš tako da bude n<m bez obzira na strukturu fajla sa prvog diska samo pod uslovom da je npr. m>100.

Dakle, sve ti se svodi na to da od jednog niza nula i jedinica napraviš drugi niz nula i jedinica, odnosno da bespotrebno komplikuješ priču uvođenjem više fajlova, jer ti se opet sve svodi na to da od jednog fajla praviš drugi fajl. Za oba diska se mogu napraviti njihove slike zauzetih delova u vidu fajlova (jedan disk, jedan fajl). Nije problem da se dopusti da fajl ne bude proizvoljno dugačak niz bajtova, već bitova ako ti tako više odgovara.
[ negyxo @ 06.02.2012. 21:01 ] @
@MajorFatal

Mnogi su ti vec kroz razne primere objasnili da to sto hoces da ne mozes da uradis - i ne mozes. Da sam na tvom mestu i da me zaista mnogo zanima kompresija, ja bi se fokusirao na kompresiju na ne-random podatke. Od njih ces nesto mozda i nauciti i mozda uspeti da namestis nesto korisno, ovako samo gubis vreme na nesto sto je nemoguce. Cisto mali hint - reci koje se upotrebljavaju se nalaze poprilicno u jednom opsegu, kao i neke kombinacije reci - mozes pogledati na netu dictionary based algoritme, malo dalje ako pustis mastu na volju javice ti se mnoge nove ideje, imaces posla posle na razmisljanje koliko hoces :-)
[ MajorFatal @ 10.02.2012. 05:55 ] @
Citat:
Nedeljko:
Pisao ti reč "fajl" pod znacima navoda ili ne, on mora biti zapamćen na fizičkom nosiocu, a taj fizički nosilac je konačan niz bitova, koji mogu menjati vrednost. Napravi ti svoj fajl sistem, kakav god hoćeš, ali ćeš morati da znaš gde jedan fajl počinje, a gde se završava itd. Za to su takođe potrebno da budu zabeležene neke dodatne informacije. To sve moraš uzeti u obzir, tako da ako ti ne odgovaraju postojeći fajl sistemi, onda prvo opiši svoj.


U svim ovim porukama:

http://www.elitesecurity.org/t151770-5#2974833
http://www.elitesecurity.org/t151770-5#2979060
http://www.elitesecurity.org/t151770-5#3013226
http://www.elitesecurity.org/t151770-5#3027974

ljudi su mi skretali paznju na to o cemu ti pricas, a u ovoj poruci:

http://www.elitesecurity.org/t151770-5#3013776

sam valjda najkompletnije odgovorio. Ne vidim potrebu za ponavljanjem? Ali cu dodati jos samo ovo:

Citat:
Nedeljko:
...ali ćeš morati da znaš gde jedan fajl počinje, a gde se završava itd. Za to su takođe potrebno da budu zabeležene neke dodatne informacije.


Ali postoji ekvivalencija, i za originalni (pocetni, onaj koji treba da se kompresuje) fajl takodje mora da se zna gde pocinja a gde zavrsava, pa su za to takodje potrebne da se zabeleze neke dodatne informacije, zato sam uglaste zagrade koje bi trebalo da ilustruju te dodatne informacije crtao i sa leve i sa desne strane crteza tj. i oko originalnog fajla i oko kompresovanog oblika.

Nigde, nijednom recju nisam rekao da mi ne odgovaraju postojeci fajl sistemi?

Citat:
Nedeljko:
Dakle, imaš dva diska. Na jednom je tačno jedan fajl koji zajedno sa svim pratećim informacija zauzuma m bitova. Drugi disk je potpuno slobodan. Treba ti program koji će sadržaj prvog diska da upiše na drugi disk tako da se na osnovu sadržaja drugog diska može restaurirati sadržaj prvog diska, ako bi se recimo taj sadržaj obrisao. Pritom će sadržaj drugog diska zauzimati n bitova zajedno sa svim fajlovima i ostalim potrebnim informacijama. Ti tvrdiš da to možeš da uradiš tako da bude n<m bez obzira na strukturu fajla sa prvog diska samo pod uslovom da je npr. m>100.


Neverovatna stvar ali, Stijaku sam na ono "Smijesno smi sve ovo" hteo da odgovorim: meni nimalo, osim..., jedino..., ako... pa bila je tu jedna ekipa od onih sa "CompCommpress" koji su fajl kompresovali na jednoj masini a dekompresovali na drugoj, u cilju da dokazu da su postigli kompresiju, nista mi nije bilo smesnije od toga sto nisu mogli da se razumeju sta im je fajl, sta nesto sto sam nazvao 'sadrzaj fajla' a sta fajl sa zaglavljem, sta engine koji ga cita u izvornom obliku a sta engine za kompresiju/dekompresiju i koje podatke o fajlu sadrzi OS i da li isti spadaju u fajl ili izvan njega. Takodje je valjda smesna kad ne bi bila tuzna 'filozofska' rasprava ako imaju fajl od 20Mega ali nemaju kompresor, pa kad na masinu snime kompresor koji sam zauzima recimo 40Mega i onda uz pomoc njega kompresuju gorepomenuti fajl na 2Mega da li su dobili kompresiju obzirom da sada kompresor i novonastali kompresovani fajl zauzimaju ukupno 42Mega tj. vise nego pocetni fajl sam??? Od svega je najtuznije sto kao posledica slicnih rasprava i nerazumevanja tematike sada na wikipediji na onom konkursu za kompresiju zahtevaju samoraspakujucu arhivu? Posto treba da se kompresuje 100Mega da ne bi neko isporucio kompresor od 110Mega u kome je kompletna arhiva od 100Mega pothranjena pa kad dobije za kompresiju fajl od 100Mega materijala sa wikipedije mogao bi da ga "kompresuje" i na velicinu od 1.bit a prilikom dekompresije da samo isporuci onih originalnih 100Mega koje vec ima pothranjene u sebi? Paranoja! I sad neko ko bi isprogramirao dobar kompresor/dekompresor velicine recimo 40Mega a koji bi arhivu od 100Mega sazvakao na recimo 1,2Mega ne moze da ucestvuje jer se zahteva samoraspakujuca arhiva?
[ MajorFatal @ 10.02.2012. 05:55 ] @
Citat:
Nedeljko:
Dakle, imaš dva diska. Na jednom je tačno jedan fajl koji zajedno sa svim pratećim informacija zauzuma m bitova. Drugi disk je potpuno slobodan. Treba ti program koji će sadržaj prvog diska da upiše na drugi disk tako da se na osnovu sadržaja drugog diska može restaurirati sadržaj prvog diska, ako bi se recimo taj sadržaj obrisao. Pritom će sadržaj drugog diska zauzimati n bitova zajedno sa svim fajlovima i ostalim potrebnim informacijama. Ti tvrdiš da to možeš da uradiš tako da bude n<m bez obzira na strukturu fajla sa prvog diska samo pod uslovom da je npr. m>100.


Dakle, imam 1. disk, sta ce mi dva? I posle tvrdite da ja komplikujem? Dakle imam 1. disk i na njemu OS, engine za kompresiju/dekompresiju i 1. fajl, kad taj jedan fajl kompresujem uz pomoc kompresora trebalo bi da se dobije fajl manji od onog pocetnog sto moze da utvrdi OS ili bilo koji fajl menager, kad se isti dekompresuje trebalo bi da se dobije originalni fajl, sta ce mi dva diska za nesto tako jednostavno?

Citat:
Nedeljko:
Ti tvrdiš da to možeš da uradiš tako da bude n<m bez obzira na strukturu fajla sa prvog diska samo pod uslovom da je npr. m>100.


Pa da mogu da uradim vec bih uradio?
Ja tvrdim i stojim iza toga a i Vi mozete da potvrdite da za duzinu niza bita m=153 recimo, postoji 2^153 razlicitih fajlova, od toga (2^153)-2 imaju razlicite i krace ekvivalente tj. mogu da se kompresuju, preostala 2.fajla mogu da imaju razlicite ekvivalente medjusobno, i od svih ostalih, ali ne i krace. Ne vidim nikakvu ekspanziju tu, a kompresija je moguca? Bez obzira na strukture pocetnih fajlova?

Inace hvala za definiciju: "Bez obzira na strukturu pocetnih fajlova", upravo se o tome ovde radi, i sam bih to tako formulisao, pomislice neko na osnovu naslova ili iz rasprave da hocu da kompresujem random podatke, kome bi to ikad zatrebalo osim za neke eksperimente, hocu da mogu da kompresujem podatke sa nekim razumnim stepenom kompresije a da me ne zanima da li su podaci izvorno slika, muzika, film, random podaci ili neki jako optimizovan program.

Citat:
Nedeljko:
Dakle, sve ti se svodi na to da od jednog niza nula i jedinica napraviš drugi niz nula i jedinica, odnosno da bespotrebno komplikuješ priču uvođenjem više fajlova, jer ti se opet sve svodi na to da od jednog fajla praviš drugi fajl.


Zasto ne mogu da za 1. originalni fajl napravim 2. kompresovana fajla? Ako ce ta dva u zbiru da zauzimaju manje prostora nego pocetni, zasto ne bih mogao? Jos ako prvi od ta dva ima uputstva da 'pogleda' da li postoji 'parnjak' tj. drugi fajl sa istim imenom ali razlicitom ekstenzijom, ili istim imenom i dodatkom _2 u produzetku pa se posle prvog i drugi dekompresuje i zajedno daju rezultat: originalni fajl? Ili jos bolje taj posao da proveri da li postoji jos jedan fajl da obavi dekompresor?

Ne samo da mi ne smetaju danasnji fajl sistemi ili OS-evi vec je ovo upravo i moguce zbog toga sto i OS i engine za kompresiju znaju po nesto o fajlu tj. deo informacija odlazi na njih.

Odnosno ako je pocetni fajl dovoljno veliki, toliko da mogu da ga zamenim sa dva manja fajla, ako je recimo velicine N, mene vise ne zanima njegova struktura jer znam da svih (2^N)-2 fajlova mogu da zamenim sa pojedinacnim 'jednostrukim' manjim (kracim po broju bita upotrebljenih) fajlovima, a preostala 2. fajla mogu da zamenim sa po dva kompresovana fajla koji su u zbiru manji od originalnog fajla. To je dokaz da je za neke velicine fajlova kompresija bilo kakvih podataka pa i random podataka moguca U PRAKSI.

Citat:
Nedeljko:
Za oba diska se mogu napraviti njihove slike zauzetih delova u vidu fajlova (jedan disk, jedan fajl). Nije problem da se dopusti da fajl ne bude proizvoljno dugačak niz bajtova, već bitova ako ti tako više odgovara.


Pa, odgovaralo bi bitova kad vec moze, hvala za info od koristi je. :)
[ MajorFatal @ 10.02.2012. 05:56 ] @
Citat:
negyxo:
Mnogi su ti vec kroz razne primere objasnili da to sto hoces da ne mozes da uradis - i ne mozes.


Navedi 1. od tih raznih primera?

Citat:
negyxo:
Da sam na tvom mestu i da me zaista mnogo zanima kompresija, ja bi se fokusirao na kompresiju na ne-random podatke.


Nee moozem :) Nije definisano na wikipediji sta su to random podaci pa ne mogu znati ni sta su to "ne-random" koje ti pominjes, a ako se malo bolje zapitas videces da ni ti ne znas...

Citat:
negyxo:
Od njih ces nesto mozda i nauciti i mozda uspeti da namestis nesto korisno, ovako samo gubis vreme na nesto sto je nemoguce. Cisto mali hint - reci koje se upotrebljavaju se nalaze poprilicno u jednom opsegu, kao i neke kombinacije reci - mozes pogledati na netu dictionary based algoritme, malo dalje ako pustis mastu na volju javice ti se mnoge nove ideje, imaces posla posle na razmisljanje koliko hoces :-)


Hvala za hint. Citao sam nesto malo, koliko mogu da razumem. Kod lzv a on je dictionary based za sada mi se ne svidja to sto se na pocetku pravi tabela sa svih 265 integera, pa onda pregleda fajl i trazi nizove bita duzine 8, pa ih menja odgovarajucim integerima? Tako ako nadje slovo A menja ga kodom za broj (integer) 65., a u sustini niz bita 01000001 menja tim istim nizom: 01000001? No dobro onda trazi kombinacije od po 2. slova ili nizove od po 16. bita i kako nikad nisu svi iskorisceni iz celog moguceg opsega menja ih odgovarajucim integerima po redu? Zvuci dobro u teoriji, ali zasto je onda lzv-d (ako se tako zove) uspesniji od lzv-a, lzv-d posle osmobitnih kodnih reci prelazi na devetobitne pa desetobitne itd. redom? Deluje da ima vise redundanse tamo gde je razlika u duzini niza bita koji se pregleda za 1. bit nego za celu duzinu kodne reci koju ljudi najcesce koriste - jos osam bita na onih prvih 8. i duzinu kojom najcesce koduju bilo koji prirodni izvor signala? Zasto se onda ona tabela na pocetku ne pravi od najmanje moguce duzine kodne reci 1. bit? Eto to mi na primer nije jasno kod dictionary based ako sam uopste dobro skapirao (ili bar otprilike) kako to funkcionise.
[ Nedeljko @ 10.02.2012. 07:10 ] @
Citat:
MajorFatal: Pa da mogu da uradim vec bih uradio?


O čemu onda pričamo? Ni ti ni mi ostali ne mislimo da to možeš da uradiš. U čemu je onda spor?

Uzgred, možeš ti i jedan fajl od gigabajt da komprimuješ sa deset miliona fajlova od kojih nijedan nema ni bajt sadržaja, koristeći samo prateće informacije kao što je na primer ime fajla, ali to nije to.
[ negyxo @ 10.02.2012. 10:02 ] @
Citat:
MajorFatal:Navedi 1. od tih raznih primera?


Ah, pa imas bukvlano prvih par postova sa pocetka teme... ali necu da ulazim u te vode, definitivno nisam uporan toliko :-)

Citat:

Nee moozem :) Nije definisano na wikipediji sta su to random podaci pa ne mogu znati ni sta su to "ne-random" koje ti pominjes, a ako se malo bolje zapitas videces da ni ti ne znas...


http://en.wikipedia.org/wiki/Random_sequence

Meni je sasvim dovoljno ovo i od toga bi poceo:

Citat:

Kolmogrov's definition of a random string was that it is random if has no description shorter than itself via a universal Turing machine



Sto se tice dictionary-based kompresije, nema tu nista preterano specijalno - zamenjujes cesto koriscene sekvence bitova sa manjom sekvencom bitova i to je to. Fazon je samo da namestis sto bolji algoritam koji ti detektuje ta ponavljanja i zatim kreiras dictionary koji je nista vise nego jedna ogromna maping tabela.
[ MajorFatal @ 22.02.2012. 14:47 ] @
Ala Vi spinujete :) Mislim bas imate cudan nacin rasprave.

Citat:
Nedeljko: O čemu onda pričamo? Ni ti ni mi ostali ne mislimo da to možeš da uradiš. U čemu je onda spor?

Spor je u tome sto nisam ni tvrdio da bilo sta mogu da uradim, nego da je moguce da se uradi, da je izvodljivo, ostvarljivo u praksi itd..., kada sam napisao "Pa da mogu da uradim vec bih uradio" samo sam hteo da Vam skrenem paznju da me vec po drugi put i to u kratkom vremenskom roku nabedjujete za nesto, prvi put je bilo "Ako ti ne odgovaraju fajl sistemi - opisi svoj" , a hteo sam i da Vam potvrdim da bi hipoteticka situacija koju ste predstavili bila manje vise dobra ilustracija toga sto bih hteo da postignem ali uz male izmene:

Za ovako postavljene stvari:

Citat:
Nedeljko:
Dakle, imaš dva diska. Na jednom je tačno jedan fajl koji zajedno sa svim pratećim informacija zauzuma m bitova. Drugi disk je potpuno slobodan. Treba ti program koji će sadržaj prvog diska da upiše na drugi disk tako da se na osnovu sadržaja drugog diska može restaurirati sadržaj prvog diska, ako bi se recimo taj sadržaj obrisao. Pritom će sadržaj drugog diska zauzimati n bitova zajedno sa svim fajlovima i ostalim potrebnim informacijama. Ti tvrdiš da to možeš da uradiš tako da bude n<m bez obzira na strukturu fajla sa prvog diska samo pod uslovom da je npr. m>100.


...ne samo da ja ne mogu da uradim (sto nisam ni tvrdio) vec ne bih mogao ni da potvrdim da mislim da je moguce, ostvarljivo itd... jer osim sto smatram da je uvodjenje 2. diska bespotrebno komplikovanje (i to samo iz razloga da bi se razumeli o cemu pricamo, kao da dosad nije jasno: o mogucnosti kompresije random-like podataka) vec i mislim da su neprecizno postavljene stvari pa da kao takve ne mogu da se potvrde da su moguce tj. izvodljive u praksi:

Zaboravili ste da napomenete gde bi bio pothranjen program koji ce da sadrzaj prvog diska upise na drugi disk "tako da se na osnovu sadržaja drugog diska može restaurirati sadržaj prvog diska, ako bi se recimo taj sadržaj obrisao. Pritom će sadržaj drugog diska zauzimati n bitova zajedno sa svim fajlovima i ostalim potrebnim informacijama, tako da bude n<m bez obzira na strukturu fajla sa prvog diska samo pod uslovom da je npr. m>100"

1.) Samo na prvom disku: NE MOZE, jer ako se sadrzaj prvog diska obrise sta ili ko ce da restaurise podatke?
2.) Samo na drugom disku: NE MOZE, jer bi ovo bilo slicno kao onaj uslov o samoraspakujucoj arhivi, ne bi bilo u radu poredjenje sadrzaja prvog i drugog diska kada je drugi dodatno opterecen programom za restauriranje podataka.
3.) Na oba diska, moze, ali onda mora da se promeni i ova recenica iz:

Citat:
Nedeljko:
Za oba diska se mogu napraviti njihove slike zauzetih delova u vidu fajlova (jedan disk, jedan fajl).


u: Za oba diska se mogu napraviti njihove slike zauzetih delova u vidu fajlova(jedan disk, jedan fajl, jedan program)

4.) Na nekom trecem disku van ova prethodna dva, moze, ali pogledajte koliko to dodatno komplikuje vec bespotrebno zakomplikovan model, pored prethodna dva diska koja ste Vi predlozili sada bi tu bio i treci?

Za varijante pod 3.) i 4.) mogu da potvrdim da mislim da su ostvarljive u praksi cak sta vise mislim da imam matematicki, logicki dokaz da je to moguce.
Za varijante 1.) i 2.) mislim da nisu vredne raspravljanja.
[ MajorFatal @ 22.02.2012. 14:49 ] @
Citat:
Nedeljko: Uzgred, možeš ti i jedan fajl od gigabajt da komprimuješ sa deset miliona fajlova od kojih nijedan nema ni bajt sadržaja, koristeći samo prateće informacije kao što je na primer ime fajla, ali to nije to.


Sto se mene tice ako potvrdite da moze bar jos jedan fajl duzine gigabajt da se komprimuje sa nekim drugim setom od deset miliona fajlova to potvrdjuje da je moguca kompresija random like fajlova i random fajlova u praksi, to jest svih fajlova iz razloga sto i preostalih (2^gigabajt)-2 fajla duzine gigabajt bi mogli da se kompresuju sa po jednim kompresovanim fajlom, pa makar i "to ne bilo to" i donja granica za mogucnost postojanja kompresije bila na duzini fajla od jedan gigabajt.

Kako ste odabrali vrednosti 1. Gigabajt i 10. miliona fajlova, da li moze fajl od Megabajt da se komprimuje sa 10.000 fajlova ili od 1.Kb sa 10 razlicitih fajlova, gde je donja granica?

Uzgrad, u grupi resenja koja bi mogla da se okarakterisu kao moguce ali "to nije to": mogu i da uvedem jos jednu ekstenziju za kompresovane fajlove, tako bih dobio jos jedan set od (2^N)-2 fajlova koji mogu da mi posluze kao kompresovana verzija originalnih fajlova. Sa dve ekstenzije imao bih: 2*(2^N)-4 fajlova na raspolaganju za kompresiju originalnog seta od 2^N fajlova. Svakog takvog seta duzine N.

Ali zasto bih kad imam i savrseno legalno i legitimno resenje: Bar dve distribucije nula i jedinica se nikad nece pojaviti kao originalni fajlovi: ona sa svim nulama i ona sa svim jedinicama: bas iz razloga postojanja OS-a i fajl sistema jer za njihove potrebe da bi fajl uopste postojao moraju da se koduju vise od jedne osobine fajla: ime, estenzija, duzina itd... tj. svi atributi, kako je za taj zadatak neophodna bar jedna nula i bar jedna jedinica tj. od oba simbola najmanje po jedan tako da sada imamo 2^N-2 originalna fajla i 2^N-2 kracih kombinacija bita koje bi mogle da posluze kao kompresovane verzije pocetnih fajlova tj. postoji 1-1 preslikavanje. Da li je to potreban i dovoljan uslov da bi kompresija mogla da postoji u praksi ili samo potreban?
[ Nedeljko @ 22.02.2012. 18:04 ] @
To nije to zato što i imena tih fajlova moraju negde da se pamte.

Ako ne bi bilo ograničenja za dužinu imena fajla, lepo bih mogao da napravim fajl čije bi ime bilo heksadekadni zapis fajla koji se komprimuje i gotovo, ali to nije praktično, jer time ne štedim prostor na disku. Biće zauzeto više prostora nego originalnim fajlom. Zato se problem tako ne formuliše.

Gde bi bio pohranjem program, nebitno je. Može da bude u memoriji računara, samo da može da komprimuje i dekomprimuje fajl.
[ Nedeljko @ 22.02.2012. 18:07 ] @
Citat:
MajorFatal: Spor je u tome sto nisam ni tvrdio da bilo sta mogu da uradim, nego da je moguce da se uradi, da je izvodljivo, ostvarljivo u praksi itd...


A na osnovu čega onda tvrdiš da to može da se uradi kad ni sam ne znaš kako?