Ez a poszt a ott folytatódik, ahol a feb. 29-i előadást befejeztük, őse a tavalyi Gyönyör a tömör poszt. Aktuális, hogy a "elit képzést" felvevő hallgatók soraiban immár felütötte a fejét a kétségbeesés. Olyan jelekben nyilvánul ez meg, mint például: "nem értem a könyvet". Nincs ezzel az érzéssel semmi gond, azért jelentkezik, hogy tegyél ellene: többet olvasd a könyvet, többet programozz, beszélj kérdéseidről a binomoddal, dobd be itt a blogon stb.! Ez az érzés tk. meg fog menteni a bukástól, de azért nem akarom túlnyugtatni az olvasót. Mert az teljesen rendben van, hogy most még nem ért valamit, de az nincs rendben, hogy e mellett nem csinálja a kiadott feladatokat: sem a választhatókat, sem a sima, sem a hallgatói laborkártyákat! Szóval ne féljetek, de a félelmeteket csakis a megértés és a tudás tudja eloszlatni; élvezzétek a programozást, még akkor is, ha nehezebben jönnek a sikerélmények, magában a programozás "csinálásában" is találhatjátok meg az örömötöket és a dolgok jóra fordulnak, sőt talán még a források is lefordulnak :)
Pillanatkép a 2012. márc. 7-i előadásból:
Konkrét tanácsom pedig, hogy gyertek felkészülten a laborra, ami azt jelenti, hogy a poszt publikálása után dolgozzátok is fel azt, íme jöjjön hát akkor most jóelőre az anyag:
man compress:
DESCRIPTION de már jópár éve lejárt a szabadalmi oltalom, egyik eredmény: a gif visszaszorult, a png elterjedt. (A Lempel-Ziv-Welch algoritmust használja a gif formátuma, sok tömörítő, például a compress, gzip, zip.)
The compress utility shall attempt to reduce the size of the named files by using adaptive Lempel-Ziv coding algorithm.
Note: Lempel-Ziv is US Patent 4464650, issued to William Eastman, Abraham Lempel, Jacob Ziv, Martin Cohn on August 7th, 1984, and assigned to Sperry Corporation.
Lempel-Ziv-Welch compression is covered by US Patent 4558302, issued to Terry A. Welch on December 10th, 1985, and assigned to Sperry Corporation."
Az algoritmus remek leírását találjuk a Rónyai-Iványos-Szabó Algoritmusok könyvben. Alább egy naivabb implementációt adunk a Tusnády: Sztochasztikus számítástechnika című könyv alapján: jön a 0-1 sorozat, betűnként olvassuk, ha olyan rész jön, ami még "nincs a zsákban", akkor "letörjük és be a zsákba":
00011101110 -> 0 00 1 11 01 110
a tördelést egy bináris fával könnyen meg tudjuk valósítani:
/
0 1
0 1 1
0
Így használd:
[norbi@sgu C]$ more b.txt
00011101110
[norbi@sgu C]$ gcc z.c -o z -std=c99
[norbi@sgu C]$ ./z < b.txt
00011101110
---------1
------------0
------1
---/
---------1
------0
---------0
A kód immár nem csak képpel:
#include <stdio.h> #include <stdlib.h> #include <unistd.h> typedef struct binfa { int ertek; struct binfa *bal_nulla; struct binfa *jobb_egy; } BINFA, *BINFA_PTR; BINFA_PTR uj_elem () { BINFA_PTR p; if ((p = (BINFA_PTR) malloc (sizeof (BINFA))) == NULL) { perror ("memoria"); exit (EXIT_FAILURE); } return p; } extern void kiir (BINFA_PTR elem); extern void szabadit (BINFA_PTR elem); int main (int argc, char **argv) { char b; BINFA_PTR gyoker = uj_elem (); gyoker->ertek = '/'; BINFA_PTR fa = gyoker; while (read (0, (void *) &b, 1)) { write (1, &b, 1); if (b == '0') { if (fa->bal_nulla == NULL) { fa->bal_nulla = uj_elem (); fa->bal_nulla->ertek = 0; fa->bal_nulla->bal_nulla = fa->bal_nulla->jobb_egy = NULL; fa = gyoker; } else { fa = fa->bal_nulla; } } else { if (fa->jobb_egy == NULL) { fa->jobb_egy = uj_elem (); fa->jobb_egy->ertek = 1; fa->jobb_egy->bal_nulla = fa->jobb_egy->jobb_egy = NULL; fa = gyoker; } else { fa = fa->jobb_egy; } } } printf ("\n"); kiir (gyoker); extern int max_melyseg; printf ("melyseg=%d", max_melyseg); szabadit (gyoker); } static int melyseg = 0; int max_melyseg = 0; void kiir (BINFA_PTR elem) { if (elem != NULL) { ++melyseg; if (melyseg > max_melyseg) max_melyseg = melyseg; kiir (elem->jobb_egy); for (int i = 0; i < melyseg; ++i) printf ("---"); printf ("%c(%d)\n", elem->ertek < 2 ? '0' + elem->ertek : elem->ertek, melyseg); kiir (elem->bal_nulla); --melyseg; } } void szabadit (BINFA_PTR elem) { if (elem != NULL) { szabadit (elem->jobb_egy); szabadit (elem->bal_nulla); free (elem); } }
3 kisbajnokság
Annak, aki először megmondja, hogy a esr.fsf.hu/hacker-howto.html lap bitenként nézve milyen mély ilyen "Ziv-Lempel" fát épít fel. Tipp: írj egy dump progit, ami 0-1 karakterekben kiköpi a bináris bemenetét és tedd ezt:
[norbi@sgu C]$ wget http://esr.fsf.hu/hacker-howto.htmlezt már megeszi a fenti kód, csak ki kell íratnod a mélységet. (Ne feledd: a laborteljesítés feladata olyasmi lesz, hogy binárisan kell majd feldolgoznod a bemenetet, pontos specifikáció majd később.)
[norbi@sgu C]$ cat hacker-howto.html|./d >hacker-howto.html.01
[norbi@sgu C]$ more hacker-howto.html.01
A program a 4. laboron kerül terítékre, de már a harmadikon szerepel majd az említett dump:
A laborok teljesítésének egyik szükséges feltétele
Idézet az 1. előadásból:
Labor teljesítésének további szükséges feltétele egy saját program
bemutatása a laborközösség előtt, a félév közepén. A feladat kötött:
adok egy karakterekre (0,1 betűkre) működő algoritmust, azt kell
átírni, hogy bináris bemenetre (0, 1 bitekre) működjön (lásd 3 előadás
és labor). A félév végén pedig egy saját robofocis fejlesztés
bemutatása.
Illetve idén már csak a C++ változat lesz védhető, de éppen ezért addig még van néhány előadás.
A karakterekre működő LZW fa építő most szerepelt, de binárisra úgy engedtük rá, hogy azt először az iménti dump progival karakteres 0,1 állománnyá alakítottuk. Most majd olyat kell írnod, ami kapásból binárisat dolgoz fel! Íme a specifikáció:
Állomány: BNbeadando.c (saját monogram, ékezetes betű nincs)
Parancssor: ./BNbeadando input_fájl_neve -o kimeneti_fájl_neve (ha nem így indítják, kiírja, hogy így kellene használni és leáll)
Kimenet: tartalmazza a 0,1 bináris LZW fát, majd a fa mélységét, végül a fa ághosszainak szórását (utóbbi a negyedik laboron is téma)
(Lesz néhány teszt állomány megadva, ahol előre meg lehet nézni, hogy megfelelően működik-e a kifejlesztett progitok. Aki előre akar dolgozni, itt a poszt, illetve az SVN-ben fent van a d.c, z.c természetesen, a linkelt posztban a fájlnév változott, ezt használd: ftp://ftp.ncbi.nlm.nih.gov/genomes/H_sapiens/CHR_02/hs_alt_HuRef_chr2.fa.gz ennek mélységéért adok 3 trófeát az elsőnek, s ha a hivatkozott poszt szerint a d.c "meghekkelésével" az első sort kidobja, az így kapott mélységért még +2-t.)
Egyéb trófeák:
- 10/2 Szigorúan titkos
- 2/6 (+1) Alternatív tabella (+1 minden bajnoki forduló után, ha a wikire is feltöltöd, azért 2 fős, hogy ellenőrizzék egymást, a wikire csak jó számolást töltsünk fel, ellenőrizzük progijainkat a korábban kitett tabellákra)
- 20/2 fordíts kernelt a Linuxodon (l. 3. ea. megfelelő fóliái)
- 3/2 készíts olyan kernelmodult, amely kiírja, hány processz van (l. 3. ea. megfelelő fóliái)
- 3/2 készíts olyan rendszerhívást, amely kiírja, hány processz van (l. 3. ea. megfelelő fóliái)
- 3/3 készíts olyan kernelmodult, amely kiírja az összes processz néhány általad választott jellemzőjét a PCB-ből (l. 3. ea. megfelelő fóliái)
- 3/2 készíts olyan kernelmodult, amely kiírja hogy melyik a következő szabad állományleíró (l. 3. ea. megfelelő fóliái)
- 10/5 írd meg a Linux top parancsát (a PP 89-től alapján, akkor 5 pont, ha legalább ncurses-es)
Kis help a Linux kernel hacking megkezdéséhez itt.
Többen jelezték, hogy belezavarodtak a hallgatói laborkártyákba, ezért tekintsük át, mit kell ennek kapcsán tudni felmutatni a 03.05 hét laborján:
- az első 4 fejezetből a 3 kérdés
- az első 4 fejezetből a binom 3 kérdésének megismerése, megtárgyalása
- a referencia kézikönyv részből a 3 kérdés
- a referencia kézikönyv részből a binom 3 kérdésének megismerése, megtárgyalása
- s ha már fellapoztuk a könyvet adjunk ki egy aktuális további feladatot: az 5. és 6. fejezetből is kérném a saját három kérdést (ez a "Mutatók és tömbök" és a "Struktúrák" fejezetek)
nem kell papíron, sokkal jobb, ha elektronikus, de be kell tudni mutatni kérésemre!
Az utolsó 100 komment: