Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Računanje Galoaove grupe

[es] :: Matematika :: Računanje Galoaove grupe

[ Pregleda: 4886 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dial.InfoSky.Net.



+2789 Profil

icon Računanje Galoaove grupe11.05.2005. u 22:15 - pre 229 meseci
Da li neko zna barem jedan algoritam za računanje Galoaove grupe proizvoljnog polinoma sa racionalnim koeficijentima?
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

KPYU
Karan Predrag

Član broj: 36769
Poruke: 143
*.nspoint.net.



Profil

icon Re: Računanje Galoaove grupe12.05.2005. u 00:16 - pre 229 meseci
Mislim da znam nekog ko zna
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dial.InfoSky.Net.



+2789 Profil

icon Re: Računanje Galoaove grupe20.05.2005. u 09:55 - pre 229 meseci
Dobro, hoće li neko da odgovori, ili moram ja?
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dial.InfoSky.Net.



+2789 Profil

icon Re: Računanje Galoaove grupe31.05.2005. u 16:02 - pre 229 meseci
Ako nekoga zanima, mogu da postujem jedan algoritam.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3996
*.dialup.neobee.net.

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253


+605 Profil

icon Re: Računanje Galoaove grupe02.06.2005. u 13:35 - pre 229 meseci
Ja se lično ne bavim Galoaovim grupama ali ako te ne mrzi napiši taj algoritam koji znaš, možda će nekome nekad zatrebati.
Ljubičice crvena, što si plava kô zelena trava.
 
Odgovor na temu

Sonec

Član broj: 284879
Poruke: 892



+332 Profil

icon Re: Računanje Galoaove grupe12.05.2013. u 16:18 - pre 132 meseci
Ja bih voleo da vidim, s tim da necu moci da ga detaljnije analiziram narednih 20-tak dana, jer trenutno radim druge stvari.
Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.3gnet.mts.telekom.rs.



+2789 Profil

icon Re: Računanje Galoaove grupe13.05.2013. u 19:32 - pre 132 meseci
Polje algebarskih brojeva je rekurzivno. To znači da postoji reprezentacija algebarskih brojeva, tako da se može algoritamski računati sa njima (množiti, deliti, sabirati, oduzimati i porediti da li su jednaki), baš kao što racionalni brojevi imaju reprezentaciju (par - brojilac, imenilac) takav da postoje pravila računanja sa time.

Pošto je algebarski broj koren polinoma stepena bar jedan sa racionalnim koeficijentima, može se kao reprezentacija izabrati par - polinom, disk čiji centar ima racionalan realan i imaginaran deo i racionalan poluprečnik takav da željeni koren polinoma pripada unutrašnjosti diska, a ostali ne pripadaju zatvorenju diska.

Pritom se lako može osloboditi najpre višestrukih korena polinoma, jer polinom ima isti skup korena kao polinom , ali je svaki jednostruk. Time prelazimo na slučaj kada nam je broj korena polinoma poznat (jednak stepenu polinoma). Dalje, postoje globalno konvergentni algoritmi za numeričko rešavanje algebarskih jednačina. To znači da možemo odrediti onoliko proizvoljno malih disjunktnih diskova koji sadrže po jedan koren, koliki je stepen polinoma. Time se svi koreni polinoma mogu izračunati sa proizvoljnom tačnošću.

Računanjem vrednosti izraza u tački koja je neki od tih korena uzimajući u obzir disk kome koren pripada i grešku odsecanja prilikom računanja može se odrediti disk kome pripada vrednost izraza, pri čemu taj dosk može biti po želji mali s tim da se odredi dovoljno mali disk kome pripada taj koren. Takođe, algoritmima za faktorizaciju, kao što je na primer Kronekerov, može se polinom faktorisati na proste činioce nad poljem . Ako se svaki od faktora izračuna u tački koja predstavlja željeni koren i dobije disk kome pripada željena vrednost, dobijanjem sve manjih diskova će se dobiti za sve faktore osim jednog da im taj koren polaznog polinoma nije koren, na osnovu čega je taj koren polaznog polinoma koren preostalog faktora. Tako se u reprezentaciji može preći na nesvodljiv polinom nad poljem .

Problem je kako na osnovu reprezentacija algebarskih brojeva i izračunati reprezentaciju od npr. i slično za oduzimanje, delenje, množenje i korenovanje proizvoljnog stepena.

Ako je , pri čemu je i , onda se svaki stepen broja može prikazati kao linearna kombinacija stepena broja sa izložiocima manjim od i sa racionalnim koeficijentima. Naime, ako je ostatak pri delenju polinoma polinomom , onda je . Slično važi i za stepene broja .

Uočimo brojeve , gde je i i numerišimo ih i označimo sa . Svaki broj oblika se može prikazati kao linearna kombinacija brojeva sa racionalnim koeficijentima. Korišćenjem te činjenice i binomne formule se može broj izraziti kao linearna kombinacija brojeva sa racionalnim koeficijentima.

Ako je uz , formirajmo matricu formata takvu da se u preseku -te vrste i -te kolone nalazi . Obzirom da je broj vrsta veći od broja kolona, vrste matrice su linearno zavisne, postoje racionalni brojevi od kojih barem jedan nije nula, takvi da je za svako . Stoga je

,

odnosno za . Slično se postupa u slučaju ostalih operacija. Nakon što smo odredili nenula polinom sa racionalnim koeficijentima čiji je jedan od korena treba odrediti bar jedan disk u čijoj unutrašnjosti leži i čijem zatvorenju ne pripada nijedan drugi koren polinoma . To se može učiniti sve tačnijim izračunavanem brojeva i u cilju sve tačnijeg izračunavanja broja i sve tačnijim računanjem svih korena polinoma sve dok disk koji sadrži ne postane disjunktan sa diskovima koji sadrže korene polinoma osim jednog.

Slično se postupa i sa oduzimanjem i množenjem. Što se inverza u odnosu na množenje tiče, ako je za i , onda je za . Takođe, ako je bilo koji -ti kompleksni koren broja i , onda je koren polinoma . Za određivanje diskova važe slične primedbe kao malopre.

Napokon, kako utvrditi da li su brojevi i dati različitim reprezentacijama jednaki? Izračunajmo reprezentaciju broja , pa ako se posle svođenja polinoma iz reprezentacije na minimalan dobije polinom , onda je , a u suprotnom nije.

[Ovu poruku je menjao Nedeljko dana 13.05.2013. u 21:51 GMT+1]
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.3gnet.mts.telekom.rs.



+2789 Profil

icon Re: Računanje Galoaove grupe13.05.2013. u 20:45 - pre 132 meseci
Proverimo koliko su ključne teoreme Galoaove teorije konstruktivne do na rekurzivnost polja algebarskih brojeva. Ispostaviće se da jesu.

Neka je dat polinom sa racionalnim koeficijentima stepena barem jedan. Polinomi i imaju isti skup korena, pa samim tim i isto korensko polje, pa samim tim i istu Galoaovu grupu, pri čemu drugi nema višestrukih korena. Stoga se možemo ograničiti na slučaj polinoma bez višestrukih korena.

Ako su svi koreni polinoma bez višestrukih korena uzeti po jedanput (njihove reprezentacije su izračunljive na osnovu polinoma ), treba naći koje je primitivni element korenskog polja polinoma . U tu svrhu koristimo algoritam iz teoreme o primitivnom elementu. Ako su i algebarski brojevi dati reprezentacijama, postoji primitivan element oblika , gde je izabrano tako da ne zadovolji nijednu od nekih konačno mnogo linearnih jednačina sa koeficijentima koji su algebarski brojevi kojima možemo naći reprezentacije. Računajući sa reprezentacijama, za jedan po jedan ceo broj proveravamo da li ispunjava uslove dok ne nađemo onaj koji ispunjava. Tako nalazimo reprezentacije brojeva takvih da je i za . U tom slučaju je traženi primitivni element.

Obzirom da imamo reprezentaciju elementa , a ona se uvek može svesti na slučaj kada je polinom u reprezentaciji nesvodljiv nad poljem racionalnih brojeva, imamo i minimalni polinom primitivnog elementa. Numeričkim nalaženjem korena tog polinoma nalazimo i reprezentacije svih konjugata od . Recimo da su svi oni i da je .

Automorfizmi korenskog polja (koje je Galoaovo raširenje osnovnog polja) slikaju algebarski broj u neki od njegovih konjugata, mogu ga preslikati u bilo koji od konjugata i jednoznačno su određeni slikom primitivnog elementa. Recimo da je automorfizam za koji je . Pitanje je šta je . Svakako mora biti u pitanju jedan od brojeva . Ako je polinom sa racionalnim koeficijentima takav da je , onda je . Obzirom da ova vrednost mora pripadati konačnom skupu , numeričkim računanjem možemo poodbacivati sve mogućnosti osim jedne i zaključiti koliko je .

Ostaje da se odredi polinom . On se može odrediti tako što se nabrajaju svi polinomi sa racionalnim koeficijentima stepena nižeg od dok se ne nađe onaj čija je vrednost u tački jednaka . Naravno, ima i efikasnijih načina, ali i ovo je dovoljno za konstrukciju algoritma, koliko god on bio neefikasan.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.3gnet.mts.telekom.rs.



+2789 Profil

icon Re: Računanje Galoaove grupe15.05.2013. u 19:49 - pre 132 meseci
Postoji još nešto - ako se ispostavi da je Galoaova grupa rešiva, postoji algoritam koji ispisuje radikalska rešenja. Pristup je opet u tome da se slede ključne teoreme Galoaove teorije, čiji su standardni dokazi konstruktivni do na rekurzivnost polja algebarskih brojeva, ali je priča kudikamo duža i zaista me mrzi da pišem. U svakom slučaju bih voleo da čujem druge šta misle o ovome.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.3gnet.mts.telekom.rs.



+2789 Profil

icon Re: Računanje Galoaove grupe17.05.2013. u 08:29 - pre 132 meseci
Ispravka:
Citat:
Nedeljko: Uočimo brojeve , gde je i i numerišimo ih i označimo sa .

Umesto treba .
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

[es] :: Matematika :: Računanje Galoaove grupe

[ Pregleda: 4886 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.