Algoritmusok

Van sok Office Open XML dokumentumunk. Ezeket megnyitjuk MS Office 2010-zel és LibreOffice-szal, mindkettőből mentünk egy PDF-et vagy PS-t. A PDF vagy PS bitképpé alakítható, lesz egy screenshot-pár, az egyik a dokumentum képe MS Office-ban, a másik a dokumentum képe LibreOffice-ban.

Ezeket a képeket kellene összehasonlítani. Sajnos pixelre akkor sem egyeznek meg, ha amúgy a LibreOffice-ba való importálás hibátlan, azaz kb. ugyanazt látjuk mindkét képen. Kicsit máshogy renderelődnek a fontok, kicsit mások a térközök, de a layout mégis ugyanaz. Valahogy el kellene különíteni a hibás importálást a jótól egy program segítségével.

Zseniális videók a különböző rendezési algoritmusok szemléltetésére:

bubblesort:
http://www.youtube.com/watch?v=lyZQPjUT5B4&feature=related

selectsort:
http://www.youtube.com/watch?v=Ns4TPTC8whw&feature=related

shellsort:
http://www.youtube.com/watch?v=CmPA7zE8mx0&feature=related

insert sort:
http://www.youtube.com/watch?v=ROalU379l3U&feature=related

Azt mondjuk megnézném, hogy a quicksortot, hogyan táncolnák el... :)

Sziasztok!

PHP vagy MySQL alatt tud valaki olyan függvényről, ami képes olyanra, hogy egy szövegben nem csak egy konkrét szót, hanem az ahhoz hasonlókat is keresi?

Pl:
Eredeti szöveg:
"BBCode jelölők használata engedélyezett, az URL-ek automatikusan linkké alakulnak"

és szeretném, ha mondjuk a "használatára", vagy az "engedélyezni", vagy a "linkek" szavakat a szövegben megtalálja.

Valakinek valami ötlet? Van erre valami szakirodalom, ahol érdemes tovább keresni?

Szép napot !

Alaphelyzet: egy darab Solaris processz, van egy jó nagy platformunk, (C++-ban) ami
tartalmaz egy (konkrétan topológia) adatstruktúrát, ami néha változhat (újra kell olvasni, mert módositják, törölnek/hozzáadnak, stb.)
Ilyenkor (1) write lockoljuk a globális platform lockot (konkrétan omni thread mutex), hogy ne akadjuk össze az alábbival:

A processzünk sok threadben, több CPU magon bejövő eseményeket dolgoz fel, amikből jó sok tud jönni per sec. Mikor bejön egy esemény, turkálni (olvasni) kell az adatstruktúrában, ehhez (2) read lockoljuk a globális platform lockot.
(a sok (2)-es egymást nem zavarja, mert mind csak olvas, mehetnek egyszerre)

Probléma: a mutex megszerzésnek/eleresztésnek van költsége, ami nagy esemény intenzitás esetén jelentős lehet, még akkor is, ha szabad a lock. (nyilvántartjuk az olvasásra várók számát, if-elgetünk, külön mutex van az olvasásra várók számának változtatásához és vizsgálatához, conditional variable a várakozók felébresztéséhez, stb.)

Amin agyalok:
Mivel az (1) viszonylag ritkán történik, ezért az idő túlnyomó részében de facto fölösleges a lockot megszerezni a (2) esetben. Az ötlet az, hogy limitálnám, hogy az (1) pl. csak minden 10. másodpercben történhetne (pl. kivárnánk), ezáltal a többi 9 másodpercben (azaz az idő 90%-ában) ki lehetne hagyni a lockolást a (2) esetekben.
(alternativa, hogy nem idő szerint, hanem iráskor tennénk éles módba a lockot)

A gondom, hogy ehhez is kell egy flag, ami jelzi, hogy 'éles' módban vagyunk-e (azaz egy 10. másodpercben) vagy nem. Ennek a flagnak az állitásához ill. vizsgálatához ugyancsak kéne egy lock, különben a 10. másodperc elején/végén nem lesz biztonságos a működés. Akkor meg ott vagyok, ahol a part szakad, egy mutexet kiváltottam egy másikkal, amit vizsgálni kell rengetegszer, minden eseménynél a (2)-ben.
És ha egy nem éles módban (2)-ben elkezdett olvasás közben üt az óra, és hirtelen éles módba megyünk, akkor az (1) thread simán megkapja a write lockot, és összekuszálja az adatstruktúrát, amin a (2) dobhat egy hátast.

Szóval itt tartok, nem találok fogást a problémán. Pedig *valahogy* meg lehetne úszni a nagyrészt fölösleges lockolásokat, azt sejtem.
Köszi minden konstruktiv tippet.

Keresek valami olyan programot, amivel bármilyen magyar szónak leveszi a toldalékát, ragokat, többesszámot stb. egyszóval mindent.

Pl.
- paprikás -- paprika
- almásan -- alma

Linux alá kellene, akár valami library vagy cli. Megköszönném, ha valamilyen példával együtt írnátok, ne csak annyit, hogy hunspell. :)

Köszi!

Sziasztok!

Egy algoritmust kellene találnom a következő problémára:

Adva van egy lap (szélesség, magasság) és n db kép ( kép azonosító, max. szélesség, max. magasság).
Az algoritmusnak a képeket kellene a lapra helyeznie úgy, hogy a lapot optimálisan töltsék ki a képek.
A képeknél a maximum szélesség és magasság van megadva ( ez az a méret ami felett már pixelesedik megjelenítés ), aminél lehetnek kisebbek de a képek szélesség/magasság aránya nem változhat.
Meg van meg adva a képek minimum szélessége ami egy konstans( álló képnél a magasság ).
Az mar csak hab a tortán, hogy van egy konstans távolság megadva a képek között (margo1) és a képek és a lap széle között (margo2).

Az algoritmus kimenetének az n db kép x, y koordinátájának és szélesség, magasságnak kellene lenni.

Még annál a fázisnál tartok, hogy milyen fajta algoritmus jöhetne szóba a problémára.
Tudom, hogy vannak matematikai algoritmusok egy téglalap felosztására például.
Mivel a képek mérete nem előre meghatározott, azon gondolkodtam, hogy ez már nem-e a mesterséges intelligenciával jobban megoldható kategória inkább.
Nem szeretném újra feltalálni a kereket, ezért kérdezlek benneteket, hogy ismer-e valaki erre a problémára illő vagy hasonló létező algoritmust.

Előre is köszi a segítséget!

sziasztok!

olvasgattam neten mindenfele kriptografiai cuccokrol, es a veges testeken (galois field) alapulo eljarasokat mindig megemlitik, mint igen, ennek (mmint a gf-eknek) is van eroteljes kriptografiai alkalmazasa. es valoban, par algoritmusban (blowfish, pl) fel is lehet ismerni ezeket a reszleteket amik kozvetve ide kapcsolodnak.
kerdes, hogy konkret, tisztan gf-eken alapulo kripto eljarasokrol hol lehetne valami irodalmat vadaszni? pl hogy egy sima veges test feletti affin trafo mint block cipher mennyire megbizhato? (pl gf(2^32) felett egy x -> a*x+b ahol [a,b] egy 64bites kulcs). ugye ez
- rengeteg tulajdonsagot ma'r alapbol hordoz amit ugy "illik" tudnia egy jo block ciphernek (pl. siman lehet ezzel prng-t csinalni, akar meg crypto-safe-t is)
- trivialis felepiteni belole egy cbc, cfb, ofb, barmilyen lancolast, gyk annyi kell hogy a != 0 legyen;
- minimalis memory footprint (gyk ordo(1)),
- egyszeru implementalas
deviszont:
- baromi lassu, (gondolom) emiatt nem terjedt el. haxolhato ez persze, a footprint a'ra'ra (lasd pont blowfish).

viszont hogy milyen tipusu tamadasokra erzekeny egy ilyen, arrol semmi info; mindenfele oldalak vegtelen ciklusban hivatkozzak egymast (pl wikipedia-rol kiindulva), de idaig nem jut el. vagy ennyire rosszak lennenek ezek a tulajdonsagai? de akkor mint ezen matematikai struktura lehetseges felhasznalasa, miert szerepel ennyire elokelo helyen a kriptografia?

van egy mikrokontroller (atmega), amire keszul program. egy elmeleti(bb) jellegu problema, a kovetkezo" peldan keresztul: csinalunk egy egyszeru" timer-irq alapu, posix-szeru" gettimeofday()-jellegu realtime ora implementaciot, imigyen:

struct  timeval
 {      uint32_t        tv_sec;
        uint16_t        tv_msec;      /* usec helyett msec, eleg jo lesz ez is */
 };

struct  timeval  timeofday={0,0};

ISR(TIMER0_OVF_vect)
{
 static uint16_t cnt=0,inc;
 
 cnt+=20;               /* 20:9 == 32768*1000 : 14745600                     */
                        /*      == (cycle/irq) * finest_resolution : F_CPU   */
 inc=cnt/9;
 cnt=cnt%9;

 timeofday.tv_msec += inc;
 if ( timeofday.tv_msec >= 1000 )
  {     timeofday.tv_sec  += (uint32_t)(timeofday.tv_msec/1000);
        timeofday.tv_msec %= 1000;
  }
}

int gettimeofday(struct timeval *tv)
{
 tv->tv_sec  = timeofday.tv_sec;
 tv->tv_msec = timeofday.tv_msec;
 return(0);
}

...

void main(void)
{
 
 TCNT0 = 0x00;
 TCCR0 |= 0x05;
 TIMSK |= _BV(TOIE0);
 sei(); /* by default, TIMER0_OVF_vect is called in every 32768th cycle */
 ...
 struct timeval tv;
 ...
 gettimeofday(&tv);
 ...
}

nomarmost kerdes, hogy abszolute biztosra hogyan kell ezt feljavitani? ugye ha a program kivancsi az idore, megkerdezi a gettimeofday()-t, ami belepakolja szepen a &tv strukturaba.
a gettimeofday()-ban viszont elofordulhat hogy az irq-t pont a ket ertekadas kozott hivja meg (vagy az egyik ertekadast szakitja felbe, ugye az uint32_t miatt mar az elso" sem atomi egy 8/16 bites vezerlon), ekkor nagy baromsagok is tortenhetnek (1 masodperces vagy akar 65536 sec ~1 napos tevedes is). ha viszont a gettimeofday()-ban letiltom/ujraengedem az strukturafeltoteses ertekadasok elott/utan a megszakitasokat (TIMSK &= ~_BV(TOIE0); illetve TIMSK |= _BV(TOIE0);), akkor meg lehet hogy irq-t vesztek, ami meg azert gaz mert \mu-c alatt ugye ritkan hasznal az ember blocking tipusu hivasokat, tehat pl egy fo"ciklus porgeseben ahol ido"t kell merni vmi miatt, ott a gettimeofday() kihivasa lesz a kontroller minden 3ik utasitasa, tehat az irq mondjuk az cycle-ido" 1/3-1/5-e'ben tiltva lesz.

szoval ma'r egy sima ora is ekkora zavarokat okoz, nem is beszelve az olyanokrol mint uart-nal, vagy ilyesmi (foleg ha irq-t kerunk a tx-re). timer-nel meg csakcsak nem dol ossze a vilag egy jarulekos drift miatt, de egy uart-nal mar nagyon nagy gazok lehetnek (adatvesztes, deadlock).

ezekre van valami jo veze'rcsel?

a.

Üdv!

Egy saját projectnél merült fel a következő problémám: Hasonló a probléma mint a lottónál. Van mondjuk, a példa kedvéért 90 szám amiből ugye 5-öt kell kiválasztani, ismétlés nélkül. Tehát az 1,2,3,4,5 ugyan az mint az 1,2,4,5,3. Szóval ezen összes lehetőséget szeretném legeneráltatni egy scripttel, de nem tudok rá pontos algoritmust megfogalmazni. Ebben szeretnék segítséget kérni. Tehát egy olyan algoritmusra van szükségem, ami egy adott számtartományból(pl. 1-90) legenerálja az összes lehetséges x számból álló kombinációt, és utána ezek közül meg tudjam határozni pl az összes olyan kombinációt ami "kéttalálatos" a lottón. Tehát az összes olyan 5 hosszú kombináció kellene, amiben benne van az 1-90-ig számokból előállítható számpár. Bocsánat a kesze-kusza magyarázásért, nem tudom ettől jobban szavakba önteni. A problémára azt hiszem a lottó a legjobb hasonlat.

Köszi, karika200

Van egy f függvényünk, amely így működik:
f(x) = x/2 ha x páros
f(x) = 3x+1 ha x páratlan

Ha egy természetes számra alkalmazzuk ezt a függvényt, majd az értékére újra és újra alkalmazzuk, akkor előbb-utóbb valószínűleg eljutunk az 1-hez. (Ez a Collatz-sejtés)

Az ismételt függvényalkalmazások során egy számsor képződik (milyen meglepő). Például ha a 13-tól indulunk, akkor:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1. Legyen C az a függvény amelyik egy természetes számhoz a hozzá tartozó
Collatz-sor hosszát rendeli hozzá. Például: C(13) = 10.

A kérdések a következők:
1, Van-e C-nek nem triviális (tehát nem 1 vagy 2) fixpontja? (x fixpontja f-nek, ha f(x)=x)
2, Ha igen, melyik szám(ok)?
3, Hogyan érdemes nekikezdeni egy ilyen probléma vizsgálatához? Vannak általános módszerek, technikák?