Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Algoritmusok

  [1]    [2]    [3]    [4]  

Szeretnél hozzászólni? Jelentkezz be.
[100] Zilberbach2010-08-15 07:08:56

Igazad van Alma, úgy gondolom a kései időpontban én néztem el.

Az ötletem csak akkor lenne életképes a gyakorlatban, ha létezne egy olyan algoritmus, ami nagy számokról képes lenne gyorsan megállapítani, hogy egy tetszőleges (prím)szám alapú számrendszerbe átírva 0-ra végződne-e, vagy sem.

Előzmény: [99] Alma, 2010-08-15 01:03:50
[99] Alma2010-08-15 01:03:50

100 000 nem osztható 4951-gyel, mint ahogy 100 sem osztható 3-mal. Szerintem gondold végig még egyszer, bár lehet, hogy eme kései órában én nézek el valamit csúnyán.

Pl: 2003 osztható 3mal?

Előzmény: [98] Zilberbach, 2010-08-14 23:43:27
[98] Zilberbach2010-08-14 23:43:27

Úgy gondolom, sikerült egy lépést tennem abban az irányban, hogyan lehetne nagy számokat gyorsan, hatékonyan faktorizálni, viszonylag olcsó számítógépeken.

(Tudom, lehet hogy sikamlós terep ez, de a bankok és a titkosszolgálatok majd-csak találnak más módszereket, ha netalán annyira nagy törzsszám-szorzatokra is hatékony lenne az ötlet, amilyeneket ők használnak.)

1. Abból indulok ki, hogy a törzstényezős fölbontás egy olyan oszthatósági probléma, ahol a prímszámokkal való oszthatóságot vizsgáljuk.

2. De hogyan lehet rájönni gyorsan, hogy egy nagy szám osztható-e maradék nélkül például: 4951-el?

Például úgy, hogy a tízes számrendszerben fölírt szám utolsó 5 számjegyét átírjuk 4951-es számrendszerbe, és ha így 0-ra végződik akkor nyilván oszható 4951-el, ha nem, akkor nem osztható, és akkor nem is kell a nagy számot elosztani 4951-el, és ezzel rengeteg időt lehet megtakarítani.

3. Algoritmus terv-vázlat, és a számítógép fölépítésének vázlata: Ha a faktorizálandó szám páros, akkor a gép elkezdi osztani 2-vel, és ezt addig folytatja, amíg páratlan számot nem kap eredményül (ha a faktorizálandó szám páratlan ez a lépés értelemszerűen kimarad).

A(z egyik) processzor elkezdi kiszámítani a páratlan szám négyzetgyökét.

A gépben van egy gyors ROM szilárdttest memória, rajta szép sorban a prímszámok, 3-tól amennyi csak ráfér.

A (másik) processzor átszámítja a szám utolsó két számjegyét 3-as számrendszerbe, és ha 0-ra végződő számot kap akkor el is végzi az osztást 3-mal.

Ha nem 0-ra végződő számot kap, akkor meghívja a ROM-ból a következő törzsszámot az 5-öt és azzal osztja el a faktorizálandó szám 5-ös számrendszerbe átszámolt utolsó két 10-es számrendszerbeli számjegyét. (Ez egyébként az a kivétel, ahol lehetne azt is vizsgálni, hogy 10-es számrendszerben írva 0-ra, vagy 5-re végződik-e, de valószínűleg összességében nem lenne gyorsabb a program ha beleírnánk ezt a kivételt, sőt..)

Azt hiszem, a folytatást mindenki könnyen el tudja képzelni, aki ért a számítástechnikához, az ötlet lényege egyébként sem a számítástechnikai megoldásban van, ezt a leírást csak gondolat-ébresztőnek szántam, gyakorlott programírók valószínűleg csak mosolyognak rajta.

Talán még csak annyit, hogy ha a ROM kifogyna a prímszámokból akkor kicsit lassulunk, néhány processzort be kell fogni, hogy szépen sorban szoftveresen szolgáltassák a továbi prímszámokat.

[97] Zilberbach2010-06-14 21:36:33

Köszönöm a választ Róbert Gida.

Előzmény: [96] Róbert Gida, 2010-06-13 22:24:36
[96] Róbert Gida2010-06-13 22:24:36

85 jegyű számokat lehet 1 óra alatt faktorizálni egy mai átlagos 2 GHz-es gépen, 1 magon.

Előzmény: [95] Zilberbach, 2010-06-12 13:43:12
[95] Zilberbach2010-06-12 13:43:12

Elnézést kérek ha nem a megfelelő fórumhba írok, sajnos tapasztalatlan vagyok számítástechnikában.

A kérdésem:

Tételezzük föl, hogy bemegyek egy átlagos magyar számítástechnikai üzletbe, és veszek egy átlagos képességű PC-t.

Installálok rá egy olyan programot ami (nagy) számok törzstényezős fölbontását végzi el.

Maximium hány jegyű számok törzstényezős fölbontására számíthatok üzembiztosan, ha egy számra kb 1-2 óra üzemidőt szánhatok?

[94] Róbert Gida2010-01-01 17:04:44

Nem az Eternity II.-re gondoltál? Az 16x16-os és 2 millió dollárt ér egy helyes kirakása, szerintem reménytelen. Hasonló, mint a gubanc, itt is parkettázni kell.

Előzmény: [93] Higgs, 2010-01-01 15:55:59
[93] Higgs2010-01-01 15:55:59

Üdv!

Egy fórumon olvastam, hogy egy algoritmus, ami a 15*15-ös Rubik gubanc-ot belátható időn belül kirakja, 1 millió dollárt ér. Ez igaz?

[92] lgdt2009-05-16 20:45:00

Olvasd el ezt. Nem hiszem, hogy beférne a tartalma egy hozzászólásba. :)

Előzmény: [91] Orsós Ferenc, 2009-05-04 12:51:55
[91] Orsós Ferenc2009-05-04 12:51:55

hellosztok sajnos az a helyzet van, hogy mindenhez értek egy kicsit a matekon belül (naggyából) de az algoritmusokhoz kuka vagyok. ha lenne valaki olyan kedves, hogy egy kicsit részletesen elmagyarázná örök hálám adnám neki. előre is nagyon-nagyon-nagyon köszönöm.

[90] diakmatekos2007-11-18 10:44:19

nem, hanem már elkészítettem. Csak akkor vmi kezdőötlet kellett, de már megvan.

[89] Róbert Gida2007-11-11 20:46:48

Hopp, ez a prog.hu-ról van. 2000x2000-es a maximális mátrix mérete, k\leq2*n. Nem jutottál be a második fordulóba? Vagy mi történt?

Előzmény: [88] diakmatekos, 2007-11-11 19:11:29
[88] diakmatekos2007-11-11 19:11:29

A feladat már tárgytalan...

[87] diakmatekos2007-09-30 12:15:33

Sziasztok! Lenne egy elég nehéz feladatom,amit nem tudok jelenleg elkezdeni sem:( Megköszönném ha segítenétek. Csak annyit szeretnék kérni hogy segítsetek az elindulásban. Íme a feladat:

Adott egy N×N-es négyzet (mátrix). A kis négyzetek egy számot tartalmaznak, az értéküket. Lépni a szomszédos négyzetekre léphetünk (jobbra,balra,fel,le). A feladat a következő: Keressünk maximális értékű k hosszúságú körutat, mégpedig úgy hogy minden tag (kis négyzet) csak egyszer szerepel (kivéve persze a kezdőpontot, ami egyben a végpont is)! A feladat nehézsége nem N és k értékétől nehéz. (A négyzetünk kb 100*100-as, az út pedig mondjuk 30 hosszú.)

Köszönök előre is minden segítséget, ha nem értetek valamit írjatok. köszi.

[86] Hajba Károly2006-06-21 00:43:53

Sajnos jelenleg nem tudok neked [feltételt]-t konstruálni. Amit leírtam az a leghosszabb vektorösszegre vonatkozik, de nem tudom garantálni, nem látom, hogy bármely részvektortól kezdve ezzel a módszerrel el lehet-e jutni a leghosszabbhoz. Gyanítom, hogy ha az eredő nem nullvektor és nagysága egy nagyságrendel marad csak el a leghosszabbétól, akkor szerkeszthető jó induló feltétel.

Csakhogy a jó eljárásnak le kell tudni kezelnie a nullvektoros eredőjű kiosztást is.

Előzmény: [85] 2501, 2006-06-20 19:02:31
[85] 25012006-06-20 19:02:31

Igazad van, megint rossz irányban implementáltam! :)

A [79]-ben vázolt kilépési feltétel formális kontextusa a következő:

ha [feltétel], akkor keresés vége, egyébként A legyen A+K

ahol A az aktuális összeg, K a következő "tagjelölt". [79] esetében pedig [feltétel]: E*(A+K)<0, ahol E az összeg első tagja (tehát az a vektor, amelyikhez a "jelöltet" keressük). Kérlek, írd le, hogy [80] alapján mi a konstruálható [feltétel]! Újra átgondolva szerintem [feltétel]: E^2>(A+K)^2 vagy (E-(A+K))^2>(A+K)^2, de ezzel meg az 1:(1,0), 2:(2,0), 3:(0,1), 4:(-1,-3) bemenet tol ki. :)

Előzmény: [84] Hajba Károly, 2006-06-20 16:41:04
[84] Hajba Károly2006-06-20 16:41:04

Az 5. pont nincs benne és M(1,9) a jó megoldás, szerintem.

Előzmény: [83] 2501, 2006-06-20 11:40:56
[83] 25012006-06-20 11:40:56

Ez sajnos a [79]-es kontextusaban nem alkalmazhato, neha tul hamar kilepne.

(Peldaul ha a vektorok irany szerint rendezve 1:(3,1), 2:(4,4), 3:(-3,2), 4:(-3,2), 5:(-1,0), akkor a legtavolabbi pont (1,9), az elso vektor jeloltjei kozott lenne, de a targyalt kilepesi feltetel miatt nem talalnank meg.)

Előzmény: [80] Hajba Károly, 2006-06-20 00:08:26
[82] Hajba Károly2006-06-20 09:12:29

Néhány (további) megállapítás:

Az nyilvánvaló, hogy a vektorokat bármilyen sorrendben is illesztem egymás után, az eredőt adja ki, azaz az eredő a végpont. Két csoportba osztom a vektorok összeadását. Először keresem és feltételesen ismerem a leghosszabb összegvektort, így az első csoportba ezeket adom hozzá, majd a maradékot. Így a vektorsornak elvileg át kell haladnia a feltételezett legmesszebbi ponton. E három pontot (Kezdő, legMesszebb, Vég) nevezzük sarokpontoknak.

Mindhárom szakaszra (K-M, M-V, --> K-M-V) igaz, hogy a szakasz vektorait bármilyen sorrendbe is adom össze, a lencsén belül kell maradnia. Ha kilép, hibás volt az M pont, ha a vonalat nem csak az M pontban érint, több megoldás létezik, ha létezhet.

Eddig még nem írtam le, de az ábrából nyilvánvalóan leolvasható, ha kilép, akkor ez a kinti pont vagy K-tól vagy M-től messzebb van, mint a feltételezett legmesszebbi távolság.

Előzmény: [80] Hajba Károly, 2006-06-20 00:08:26
[81] Hajba Károly2006-06-20 00:39:49

Sőt. Az eredő vektornak is a rajz szerinti 'lencsébe' kell mutatnia!

Előzmény: [80] Hajba Károly, 2006-06-20 00:08:26
[80] Hajba Károly2006-06-20 00:08:26

Nemcsak derékszögnél jobban nem térhet ki, hanem szigorúbb feltétel is szükséges. A leghosszabb összegvektor két végpontjára ráhúzott köríven sem mehetnek ki a részvektorok.

Habár nem tudom, hogy ennek kihasználása növeli-e a leghosszabb összegvektor megtalálásának sebességét.

Előzmény: [66] 2501, 2006-06-14 15:41:13
[79] 25012006-06-19 17:18:38

A [70]-ben leírtakon annyit "csiszol" a [66]-os ötlete, hogy nem akkor hagyjuk abba egy vektorhoz a "jelölt" keresését, amikor a következő tag az elsőtől 180 foknál jobban kitérne, hanem amikor a következő taggal bővített összeg az első tagtól 90 foknál jobban kitérne.

Előzmény: [78] 2501, 2006-06-19 16:56:23
[78] 25012006-06-19 16:56:23

Megnéztem újra, és mégis jó a [66]-ban felvetett kilépési feltétel, csak rosszul implementáltam. Az "OP_maxsq" nevű függvény "if(ns*varr[k]<0) break;" sorában a "k"-t "i"-re kell javítani, hogy működjön. :)

Előzmény: [75] 2501, 2006-06-15 14:01:23
[77] egykerdes2006-06-19 16:20:31

Hali szerintem a [70] es jó megoldás és is egy hasonlót gondoltam ki, és egyenlőre nem találtam még rá ellenpéldát.

[76] 25012006-06-15 14:11:43

Forráskód

Előzmény: [75] 2501, 2006-06-15 14:01:23

  [1]    [2]    [3]    [4]