Szántó Ádám

Vissza a főoldalra

Szerdán délelőtt (május 21.) lehet utoljára házit pótlólag beadni, 9.45-10.00-ig a H épület II. emeletén, és két órán belül vissza is adom. (Ez már csupán 4 embert érint.) Ugyanakkor és ugyanott adom vissza a már kijavított házikat, aki beadott és szeretné látni, jöhet.

Minden feladat 2 pontot ér. A feladatok 60%-át kell teljesíteni.

Összesen 37+5 pontot lehetett szerezni. 22 ponttól van meg a 60%.

AKINEK MÉG NINCS MEG, az szerda reggel a szokott időben-helyen odaadhatja, bejövök számítógépes grafika, vagymi, előtt.

Az e hétre beadott házit is beleszámítva 22 pontra emelkedett a 60%-os küszöb. Néhányan már adtak be pótházit, nekik nagyjából meg is lett a pontszámuk. Viszont még mindig több mint a feletek bukásra áll, szóval amíg tart a szorgalmi időszak, meg lehet keresni feladatokkal az órarendem alapján, meg mailben is, de ne nagyon halogassátok!

Feladat: n=317940011, e=77537081, n faktorizálása Wiener támadás alapján
Kaptok a lánctört szeleteiből egy tippet t/d-re. Ezt tesztelni kell. A teszthez viszont t-t és d-t közvetlenül akarjátok felhasználni, ez már bajosabb, ugyanis csak a hányadosuk van a kezetekben. Csak akkor megy, ha a kettő relatív prím, ezt viszont senki nem bizonyította/említette, aki 2 pontot kapott. Tehát tekintsék a 2 pontosok is úgy, mintha 1 pontot kaptak volna!

FONTOS! Mivel a félév vége felé közeledik, lehetővé tesszük a javítást azoknak, akiknek nincs meg a 60% (=21 pont). Ez jelenleg kábé a csoport 2/3-át érinti. Adjatok be legközelebbi előadásra pótlólag tetszőleges korábbi feladatokból annyit, amennyit kell (ami pontot már egyszer megkaptatok, azt mégegyszer nem osztom ki, de ha pl. 1 pontot kaptatok egy feladatra, akkor hajthattok még a 2-re), és olyan jól, hogy ne tudjak belőle levonni. (Persze nem ez a cél. :) Ha neadjisten nem sikerül, még mindig van egy lehetőség, de ne arra játsszatok. És ne másoljatok, főleg rosszat ne!

1. feladat: N_L(0, 0)
Ment.

2. feladat: N_L(a, 0)
Ezt a Pascal-háromszöges izét szerintem kábé senki nem ismeri, aki lemásolta, de egyébként én sem. Ha nekem kellett volna megírni a házit, akkor azzal játszottam volna, hogy megmutatom, hogy a 0-t adó x-ek száma ugyanannyi, mint az 1-t adó x-ek száma, mégpedig úgy, hogy párba állítom őket. A bijekció pedig a következő: fogom azt a helyet, ahol a-ban először szerepel 1-es, mondjuk ez a_i. Ezen a helyen az x változó értékét megbököm, x_i helyébe 1-x_i-t írok és belátom, hogy ez injektív és szürjektív. Nem sokkal egyszerűbb?

2. feladat: N_L(a, b) szummája minden a-ra
No, én ezt egyelőre nem értem, de állítólag a táblázatos izéből ki lehet hozni, amit tanultatok!

Apropó táblázatos izé. Az a két ember, aki ezt használta a házijában, egyelőre *-pontot kapott rá a táblázatban. Hétfőn adjátok be újra ugyanazt a papírt, csak tegyétek mellé az érthető magyarázatot is, hogy mi az a táblázat! És ne úgy, hogy "szerintem", hanem, hogy tényleg mi, mert arra szeretném a pontot adni.

Meg voltam elégedve, mert lényegesen kevesebb másolást tapasztaltam, csak így tovább! Jutalmul ebben a körben nem osztottam 0 pontot.

2. feladat: GF(9) összes elemének a minimálpolinomja
Alapvetően azt használtátok, hogy az egy konjugáltosztályba tartozó elemekhez tartozik egy közös minimálpolinom, csak ahhoz ugye kell egy primitív elem, ahhoz pedig egy primitív polinom, ami tiszta macera. Annyira azért nem macerás, ahogy csinálták egyesek, hogy 6 polinomosztást elvégeztek, hogy bizonyítsák, hogy tényleg az a legkisebb n. Elég az, hogy a talált gyök primitív, azaz a hatványai kiadják az egész GF(9)-et. De az tényleg kell - és aki ennyit sem tett meg, az 1 pontot kapott.

De van egy még egyszerűbb megoldás. Ugyanis eleve: csak mik lehetnek a minimálpolinomok? Az elsőfokúak könnyűek. Tehát leírjuk a másodfokú, 1 főegyütthatójúakat, GF(3) felett az összeset: az csak 9 darab. Tetszőleges módon elkészítjük a testbővítést, majd végignézzük a 9 polinomunkat, hogy ki kinek a gyöke, és kész: ugyanezt a hármat fogjuk megtalálni.

Döntést hoztam másolás-ügyben. Legközelebb, ha csak a gyanú felmerül bennem, hogy valaki úgy másolt le valamit, hogy nem értette, 0 pontot adok. Cserében viszont megpróbálhatja szóban vagy írásban bebizonyítani, hogy tévedtem.

1. feladat: F₃ fölötti 8 hosszú ciklikus kódok száma
Mindenki tudta a lényeget, az egyetlen újdonság az, hogy egy polinom nem biztos, hogy irreducibilis, csak azért, mert nincs gyöke. Ez csak másod- vagy harmadfokú esetben lesz igaz, amikor a polinom esetleges felbontásának egyik tényezője tuti (x-alfa) alakú gyöktényező.

2. feladat: [8, 4, 4]₂ nyújtott Hamming-kód lehet-e ciklikus?
Ez is ment, örültem, hogy sokféle megoldás is született.

3. feladat: Ciklikus nullaösszegű kódok generátorpolinoma
Egyszerű volt, de másoláskor ezt is sikerült sokaknak elrontani.

4. feladat: Szisztematikus ciklikus kódok jellemzése
Na erre nem sikerült értékelhető megoldást beadni, és én sem igazán értem, már a kérdést sem, szóval akinek csak ez lett rossz, az ne aggódjon...

Na most egy kicsit el voltam havazva, bocs. Az 5. feladatsor hétvégéig várat magára, a 6.-t elküldtem, viszont a pontszámokat elfelejtettem beírni, most emlékezetből vannak fent, szóval ellenőrizzétek mindenképpen! Ha nem stimmel akkor meg keressetek meg, lehetőleg a kijavított házival, az órarendemet megtaláljátok a főoldalon.

A 4. feladatsort kijavítottam, de még nem osztom ki, mert néhányaknak egyben van az 5-dikkel. Amúgy egész emberséges lett, ketten is megkapták a maxpontszámot!

1. feladat: L'(alfa_i)=L_i(alfa_i)
Egyszerű volt, mégis sokak 1 pontot kaptak rá csak, mivel másoltak ÉS rosszul. Mivel ez már n+1-edszerre fordul elő, ezért a következő alkalommal aki látványosan rosszul másol, 0 pontot fog kapni.

2. feladat: GRS_{alfa, v}=GRS_{a*alfa+(b, ..., b), c*v}
A két konstansszorzózás ment mindenkinek. A konstans b vektor hozzáadása is megy sor- és oszlopműveletekkel, a legkézenfekvőbben talán a sorokra vonatkozó teljes indukcióval jött ki.

3. feladat: n<q => GRS_{alfa, v}=GRS_{alfa', v}, ahol alfa'-nek egyik eleme sem 0
Gyönyörűen adja magát az előzőből, és olyanoknak is meg lett volna szabad oldania, akik a 2.-t nem adták be. Máskor csak bátran!

4. feladat: "nyújtott" GRS is MDS.
Nagy sláger volt ez a feladat, sajnos elsősorban másolás terén ez is. Itt már 0 pontokat is osztogattam, amikor az látszott, hogy nagyon nem érti a beadó. Leírom a logikáját a lemásoltnak (többféle megoldás is jó volt), hogy legalább egyszer értsétek: a generátorelemeken ellenőrizzük a minimális távolságot. Összevetjük egyrészt a generátormátrix utolsó sorát az összes többivel - ez az első lerajzolt mátrix miatt lesz jó - aztán az összes többi sort egymással - ehhez kellett a második mátrix.

1. feladat: GF(16) konjugáltosztályai GF(4) felett
Na itt lettem nagyon ingerült a rosszul lemásolókra, hogy egy ilyen szarvashibát nem vettek észre a másolt szövegben. Már ez megérte volna a 0 pontot, ráadásul pont egy ilyen egyszerű feladatban...

2. feladat: GF(9) összes elemének a minimálpolinomja
Aki eddig megpróbálkozott ezzel, az alapvetően a definíciókat nem érti pontosan (tisztelet az 1 fő kivételnek). Először is, nem véletlenül kezdtük a félévet azzal, hogy a GF(pⁿ)-et megkonstruáltuk egy polinom gyökével való bővítéssel, emlékeztek? Na ide is valami olyasmi kell. F_pⁿ-ben azért nem jó gondolkodni, mert az ugye n>1 esetén nem test, nem ad multiplikatív csoportot. A minimálpolinom definíciójának alapos átolvasása is segít az elindulásban.

Feladat: Önduális [8, 4, 4]₂ lineáris kód súlyfüggvénye
Ez most jól sikerült, mert végre 2 pontos megoldást másolt le a többség, nem pedig 0 pontost, mint a múltkor. Onnan látszik, hogy másolt, hogy a hülyeség is le van másolva. Sok érdekes megoldás született például arra, hogy miért van 1 db 0 súlyú kód, holott linalgból tanultátok, hogy a nullvektor minden vektortérnek eleme - például azért mert tetszőleges v vektort saját magából kivonva megkaphatjuk. Tehát a csupa 0 kód is kódszó minden lineáris kódban.

Azokat az alapészrevételeket, hogy csak páros súlyú kódszavak lehetnek, 2 súlyú nem lehet, mindenki észrevette. Ezután volt aki egyből alkalmazta a MacWilliamset és kapott egy ötismeretlenes egyenletrendszert és kimathematicázta - ez most jó, de ZH-nál nehezen lesz megoldható. Általában a legjobb az volt, hogy x=0, y=0 spec. esetből kijött, hogy van csupa 1-es kódszó, és abból minden további jó. Egyvalaki próbálta meg MacWilliams nélkül, de úgy tűnik, hogy azt annyira egyszerűen nem lehet.

1. feladat: [7, 3, 4]₂ szimplex kód duálisának súlyfüggvénye
Ez nagyjából mindenkinek ment, de levontam 1 pontot, ha valahogy nem szerepelt a végeredmény, ugyanis a súlyeloszlás csak abból olvasható le.

2. feladat: [8, 4, 4]₂ nyújtott Hamming-kód súlyfüggvénye
Egész szép mennyiségű 0 pontos született ebből, mert bár a helyes végeredményt leírtátok, de nem indokoltátok meg semmilyen formában, és most ötletem sincsen, hogy miből jöhetettek rá "ránézésre", hogy hány darab 4 súlyú kódszó szerepel. Egyébként 1 pontot ért a súlyfüggvény és további 1 pontot az, hogy általában hogyan változik a súlyfüggvény nyújtáskor.

2. feladat megoldása:
Kétféleképpen is jó lett volna. Egyik, ha leírjátok az összes kódszót, és elégedetten konstatáljátok, hogy tényleg annyi van belőle, amennyi. Ez a rondábbik. A szebbik indoklás: mivel egy paritásbitet veszünk hozzá az eredeti kódhoz, melyet az 1. feladatban kiszámoltatok, ezért ez a párosok súlyán nem változtat, a páratlan 3 hosszúak súlyát pedig eggyel megnöveli - így lesznek ezek is mind 4 súlyúak.

3. feladat: Önduális [8, 4, 4]₂ lineáris kód súlyfüggvénye
Ez az, ami jövő hétfőre még mindig beadandó. Adjátok is be, mert egyelőre senkinek sem sikerült 2 pontos, azaz helyes megoldás beadnia, bár néhányan egész jó úton járnak. Sokan viszont félreértették a kérdést, a nyújtott Hamming-kódot ebbe most nem szabad belekavarni. A feladat az, hogy ennyi információból (önduális [8, 4, 4]₂) ki kéne hozni a 2. feladat végeredményét!

1. feladat: F₉ konstruálása
Általában akkor vontam le pontot, ha elszámolás és elvi tévedés egyszerre történt, vagy az egyikből nagyon sok.

2. feladat: y kódszó <=> y H^T=0
Oda irány 1 pont, vissza irány 1 pont.

3. feladat: y helyett y+z hibavektort kapunk
Megállapítható-e a hiba, mikor és miért? 1 pont.
Hogyan? 1 pont.
Tehát ha valaki csak simán behelyettesítette (y+z)H^T-t és kiszámolta, azért nem kapott semmit. Azoknak, akik így jártak: szorozzatok be egy 1 súlyú bináris hibavektort valami H^T-vel! Ugye milyen könnyű leolvasni, hogy melyik bit hibás? Most 2 súlyút: így meg ugye hogy nem lehet leolvasni. Ennyi lett volna a válasz.