KöMaL - Középiskolai Matematikai és Fizikai Lapok
English Információ A lap Pontverseny Cikkekről Távoktatás Hírek Fórum Internetes Tesztverseny
Játékszabályok
Technikai információk
TeX tanfolyam
Regisztráció
Témák

 

apehman

Rendelje meg a KöMaL-t!

Támogatóink:

tehetseg.hu

Ericsson

Google

Emberi Erőforrások Minisztériuma

Emberi Erőforrás Támogatáskezelő

Oktatáskutató és Fejlesztő Intézet

ELTE

Reklám:

ELTE

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

Fórum - Valaki mondja meg!

  Regisztráció    Játékszabályok    Technikai információ    Témák    Közlemények  

Ön még nem jelentkezett be.
Név:
Jelszó:

  [1. oldal]    [2. oldal]    [3. oldal]    [4. oldal]    [5. oldal]    [6. oldal]    [7. oldal]    [8. oldal]    [9. oldal]    [10. oldal]    [11. oldal]    [12. oldal]    [13. oldal]    [14. oldal]    [15. oldal]    [16. oldal]    [17. oldal]    [18. oldal]    [19. oldal]    [20. oldal]    [21. oldal]    [22. oldal]    [23. oldal]    [24. oldal]    [25. oldal]    [26. oldal]    [27. oldal]    [28. oldal]    [29. oldal]    [30. oldal]    [31. oldal]    [32. oldal]    [33. oldal]    [34. oldal]    [35. oldal]    [36. oldal]    [37. oldal]    [38. oldal]    [39. oldal]    [40. oldal]    [41. oldal]    [42. oldal]    [43. oldal]    [44. oldal]    [45. oldal]    [46. oldal]    [47. oldal]    [48. oldal]    [49. oldal]    [50. oldal]    [51. oldal]    [52. oldal]    [53. oldal]    [54. oldal]    [55. oldal]    [56. oldal]    [57. oldal]    [58. oldal]    [59. oldal]    [60. oldal]    [61. oldal]    [62. oldal]    [63. oldal]    [64. oldal]    [65. oldal]    [66. oldal]    [67. oldal]    [68. oldal]    [69. oldal]    [70. oldal]    [71. oldal]    [72. oldal]    [73. oldal]    [74. oldal]    [75. oldal]    [76. oldal]    [77. oldal]    [78. oldal]    [79. oldal]    [80. oldal]    [81. oldal]  

Ha a témához hozzá kíván szólni, először regisztrálnia kell magát.
[2030] jonas2015-04-09 09:13:25

A válasz az, hogy nem igaz, én néztem be valamit. Egy ellenpélda a &tex;\displaystyle \left(\matrix{1&1&0\cr 0&0&1\cr 0&1&0}\right)&xet; mátrix.

Előzmény: [2029] jonas, 2015-04-09 08:48:28
[2029] jonas2015-04-09 08:48:28

Egy négyzetes mátrixot Hankel mátrixnak hívunk, ha bármely antidiagonálisában csak azonos elemek vannak. Például

&tex;\displaystyle T = \left(\matrix{ 0&6&2&1&9\cr 6&2&1&9&8\cr 2&1&9&8&1\cr 1&9&8&1&2\cr 9&8&1&2&1\cr }\right) &xet;

egy Hankel-mátrix.

Minket most olyan Hankel-mátrixok érdekelnek, amiknek minden eleme 0 vagy 1. Igaz-e, hogy ha egy négyzetes nulla-egy mátrix a sorainak és oszlopainak valamely permutációjával Hankel-mátrixszá alakítható, akkor csak a sorainak a permutációjával is Hankel-mátrixszá alakítható?

A kérdés onnan jön, hogy felix azt kérdezi a MathOverflow-n, hogy hány ilyen permutált mátrix van.

[2028] marcius82015-04-05 10:45:25

Kiegészítés az előző kérdésemhez: Feltehető, hogy annak a valószínősége, hogy annak a valószínűsége, hogy a 4-es metró hibamentesen "t" működik, "lambda" paraméterű exponenciális eloszlást követ. Tisztelettel: Bertalan Zoltán.

[2027] marcius82015-04-05 10:32:41

Ma reggel néztem a TV-t, és ott mondták, hogy a 4-es metró vezető nélküli próbaüzemét tervezik. Tegyük fel, hogy a 4-es metró átlagosan 60 napig tud egyfolytában hiba nélkül metróvezető nélkül működni. Ezt ellenőrizendő, a következő tesztet találták ki: A 4-es metrót egyfolytában 360 napig járatják, és mérik, hogy mennyi ideig működik vezető nélkül hibamentesen. Ha a 360 nap próbaidő alatt van meghibásodás, az időmérést 0-ról kezdve újra kezdik. Ha ezután is van meghibásodás, akkor az időmérést megint 0-ról kezdve újra kezdik. Természetesen a 360 nap alatt akárhány meghibásodás történhet akármikor, de minden egyes meghibásodás után az időmérést 0-ról kezdve újra kezdik. A teszt akkor eredményes, ha van legalább 120 nap eltelt idő, amikor a 4-es metró hibamentesen működik vezető nélkül. Mennyi annak a valószínűsége, hogy a teszt eredményes? Tisztelettel: Bertalan Zoltán.

[2026] csábos2015-03-31 21:46:16

Beütöttem a google-ba.

http://oeis.org/A001250

Itt nézz utána.

Előzmény: [2025] marcius8, 2015-03-31 07:58:12
[2025] marcius82015-03-31 07:58:12

Mennyi annak a valószínűsége, hogy "n" elemet véletlenszerűen sorbarendezve, a kapott elemek vagy úgy követik egymást, hogy nagyobb-kisebb-nagyobb-kisebb-.... vagy pedig úgy, hogy kisebb-nagyobb-kisebb-nagyobb-....? Bertalan Zoltán.

[2024] Hajba Károly2015-03-07 20:39:24

Erre a problémára már kigondoltam egy eljárást.

Mindkét fajta pontot (telekhatárpont és felirathely pont) külön-külön X és Y koordináták alapján sorba rendezem. A vizsgált terület legkisebb és legnagyobb X ill. Y koordinátája közé kell esnie a keresendő feliratpont mindkét koordinátájának. Egy nem túl bonyolult, de hosszabb telekforma ill. 'átlós' tájolás esetén max 10 vizsgálandó pont adódna, de a 20 feletti szám már nagyon extrém helyzet lenne.

Előzmény: [2021] Róbert Gida, 2015-03-07 19:42:21
[2023] Hajba Károly2015-03-07 20:11:40

Településenként van bontva, Budapesten kerületenként. Továbbá belterület-külterület-zártkert. Ezek az egybetartozó egységek, melyekre igaz, hogy minden csomópontba (nem telekhatár-töréspont) legalább három él fut be, de ez a gyakorlatban általában nem több négynél.

Tesztelés céljából kivágható egy bármely méretű téglalap formájú terület is, de ekkor lesznek kettévágott területek. (Tervezési alaptérképként ilyeneket kapunk dwg-ben, de ez az építési engedélyes terv helyszínrajzához kell.)

Előzmény: [2021] Róbert Gida, 2015-03-07 19:42:21
[2022] Hajba Károly2015-03-07 19:56:13

Nem T_OBJ_ szerepel, hanem T_FELIRAT

Előzmény: [2019] Hajba Károly, 2015-03-07 18:31:21
[2021] Róbert Gida2015-03-07 19:42:21

Heurisztika is müködik itt: legyen S a sokszög súlypontja, míg d az S és a csúcsok közötti maximális távolság. Így, ha egy p pont d-nél távolabb van S-től, akkor nem lehet a sokszögben. (és ez konkáv sokszögre is igaz természetesen).

Általában egy megyében van egy terület, így csak azokat a sokszögeket kell végignézni amik az adott megyében vannak. Egy szebb algoritmus lehetne quadtree-k alkalmazása: http://en.wikipedia.org/wiki/Quadtree .

[2020] Erben Péter2015-03-07 19:41:52

Szép feladat.

A valódi projektekben az adatok pontatlansága, illogikus tárolása sokszor több gondot okoz, mit az, hogy van-e jó algoritmus az elméleti problémára. A hibák javítása és az adatok "tisztítása" nehezebb, mit az eredeti kérdés megoldása.

Előzmény: [2017] Hajba Károly, 2015-03-07 17:22:54
[2019] Hajba Károly2015-03-07 18:31:21

Itt egy minta. 14. és 16. oldal

14. oldal: A határvonal a szakasz (s ezért írtam először vonalat), a határ a lánc, s a felület a terület.

16. oldal: A tényleges állományokban csak a T_PONT, T_HATARVONAL és ezektől független T_OBJ_ATTRDB van meghatározva, azaz a [* sárga szám *] helyett [**] szerepel, így nincs a T_FELULET-hez kötve. A * az adatok közötti szakaszoló jel.

Előzmény: [2015] Erben Péter, 2015-03-07 15:10:03
[2018] Hajba Károly2015-03-07 17:46:47

Tesztadat a szabványos DAT formátumban ill. a jelzett digitális szinten a földhivataloknál rendelkezésre állnak. Annyi észrevétellel, hogy egyes egyébként illeszkedő szakaszok elvileg közös pontja néha, ha csak kis mértékben is, de csak közel egymás mellett van. Gyanítom, hogy ez a régi rajzos térképek kézi digitalizálásának következménye. A CAD programom dwg-t fogad, s ha egy zárt görbébe kattintok, akkor azt kitölti. Sokszor ez nem sikerül és 'nem zárt görbe' hibajelzést ad, pedig ránézésre a rajzon a görbe zárt.

Majd megkérdezem, hogy (a DAT és DWG-n kívül) még milyen formátumban igényelhető adat.

Előzmény: [2015] Erben Péter, 2015-03-07 15:10:03
[2017] Hajba Károly2015-03-07 17:22:54

Köszönöm a részletes leírást.

Tegnap este rábukkantam az (A) példádra a wikin.

A feladat teljesen az életből való, sajnos minden téren. A szakaszok a földhivatali nyilvántartásban a telekhatárokat képező ömlesztve digitalizált szakaszok, az önálló pontok ezen telkek helyrajzi szám feliratának a helye. A '90-es évek végén nagyon jól kidolgozott szabvány lett megalkotva erre, de a megvalósítás során csak a lehető legkisebb átalakítást hajtották végre. A szabványban le van írva a telek fogalma is, de a nyilvántartásban nincsenek hozzárendelve a szakaszok ill. a láncok. Pedig amennyiben ez meg lenne oldva, akkor az erre alapuló területi tervezésnél nem egy CAD-es fedvényrajzot kellene készíteni kézzel és egérrel, ami vagy illeszkedik a töréspontokhoz vagy csak megközelíti, hanem a helyrajzi számmal. A hrsz-hez csak hozzárendelem a területfelhasználási adatokat, és a többit egy program elintézi ill. precízen felrajzolja, valóságos területi kimutatást készít. De jelenleg ez csak közelítő és emiatt nem lehet hiteles.

Most indult egy pilot program a "digitális Magyarországért", s ez épp abban a városban van, ahol dolgozom és épp ismerem az egyik kulcsembert. Így teszek egy kísérletet arra, hogy ez az átalakítás is bekerülhessen idővel a programba. Ehhez látnom kell a feladat folyamatát, méretét, buktatóit, s minden közbe jöhető dolgot mivel idő és pénzügyi igényt kell adni ahhoz, hogy esetleg bekerülhessen.

Előzmény: [2015] Erben Péter, 2015-03-07 15:10:03
[2016] Erben Péter2015-03-07 15:12:00

Azt elfelejtettem mondani, hogy ezek az egyszerű de lassú (&tex;\displaystyle O(l\cdot n)&xet;) algoritmusok voltak.

Előzmény: [2015] Erben Péter, 2015-03-07 15:10:03
[2015] Erben Péter2015-03-07 15:10:03

A legtöbb helyen két módszert említenek. (A) "metszések száma" /crossing number/; (B) "kanyargási szám" /winding number/. Inclusion of a point in a polygon

Az (A) azt csinálja, hogy húz egy egyenest a ponton át, és megnézi ennek az egyenesnek és a tartományt határoló szakaszoknak az összes metszéspontját. Ezeket a metszéspontokat rendezi, és azt feltételezi, hogy ha nem történt valami baj, akkor a metszéspontok felváltva jelzik, hogy beléptünk a tartományba, majd kiléptünk belőle. Tehát ez a konkáv tartományokra is működik. Ha a pontunk előtt páratlan sok metszéspont van az egyenesen (valamelyik irányból), akkor bent vagyunk, ha páros, akkor kint.

A gyakorlati megvalósításkor sok-sok nehézséggel szembesülünk.

1. Ha az egyenes átmegy a tartomány egy csúcsán, akkor azt két metszéspontnak hihetjük (a két szomszédos szakaszon egy-egy.)

2. Ha az egyenesre esik valamelyik határ szakasz, akkor ott végtelen sok közös pont van, és nem léptünk se be se ki.

3. Nem mindegy, hogy valós vagy egész aritmetikát alkalmazunk, mert egy egyenes és egy szakasz, illetve a pont és valamelyik szakasz nagyon közel eshet egymáshoz. Valós aritmetikát használva baj lehet a kerekítési hibákból, egész aritmetikánál pedig hatalmasra nőhetnek a nevezők és a számlálók, azért nem elegendők a programozási nyelvek beépített típusai. Ha az egész probléma eredete grafikai, és csak a képernyőn akarjuk pontokról eldönteni, hogy egy képernyőre rajzolt pixel egy képernyőre rajzolt tartományhoz képest hol van, akkor kevésbé kell félni a numerikus dolgoktól, mert a pixel méreténél kisebb hibák úgysem fognak látszani.

A (B) azon alapul, hogy megszámolja, hányszor kerüli meg a poligon a pontot. Akkor van kívül egy pont, ha nullaszor. Valahogy úgy megy a számolás, hogy a körüljárás szerint sorra vesszük a tartományt határoló szakaszokat, és mindegyikre kiszámoljuk, mekkora szögben látszik (irányított szakasz, irányított szög) a pontból. Külső pontra az előjeles szögek összege nulla, ez szemléletesen látszik konvex tartomány esetén.

Itt meg az a gond, hogy rengeteg inverz trigonometrikus függvényhívást csinálunk, ami lassú és ott is lehetnek kerekítési problémák.

Ha vannak konkrét bemenő adataid (amik nem titkosak), az érdekelne, mert ehhez a problémához nem egyszerű jó tesztadatokat gyártani.

Előzmény: [2013] Hajba Károly, 2015-03-06 16:56:29
[2014] Hajba Károly2015-03-06 17:21:29

Az előbb valamiért beleképzeltem a háromszögekre bontást, de te erről nem beszéltél.

Így akkor ezen sokszögbe beleesés vizsgálatának mikéntjéről is kérnék egy kis fejtágítást. Gyanítom, hogy a szakaszok által meghatározott egyenes egyik oldalán pozitív, míg a másik oldalán negatív értéket eredményezne a pont és végig pozitív oldalon kell maradni. De ebbe még bele kellene mélyednem.

Előzmény: [2012] jonas, 2015-03-04 22:54:07
[2013] Hajba Károly2015-03-06 16:56:29

Az első bekezdésben leírtakra időközben én is rájöttem. A pontokhoz hozzárendelem a vonalak azonosítóját. A vonalakhoz rendelt pontazonosítók meg már eleve adottak. Ahol ez nagyobb, mint 2, az csúcspontok. Ezek ismeretében már megtalálható az eljárás a területek körbejárásához.

A kérdés a második bekezdés. (A könyv nem játszik, nem tudok angolul.) Gyakorlatilag a vizsgált sokszöget elemi háromszögekre kell bontanom és minden háromszögre vizsgálni, hogy benne van-e. S ez időrabló mulatság.

Ha elmagyarázod, én állok elé a rögös utas hatékonyabb megoldás megértése elé.

Előzmény: [2012] jonas, 2015-03-04 22:54:07
[2012] jonas2015-03-04 22:54:07

A lényeg a következő. Először minden olyan csúcsban, ahol a töröttvonalak (láncok) végei találkoznak, találd meg az összes töröttvonalat, és ezeket rakd ciklikus sorrendbe a kiindulási szögük szerint. Utána ez alapján meg tudod találni az összes sokszöget, és mindegyiket az ezek határát alkotó töröttvonalakkal le tudod írni úgy. Ezt úgy lehet megtenni, hogy minden töröttvonalból elindulsz mindkét irányba, és átmész a következő töröttvonalra a csúcsnál, mindig balra fordulva.

Ez után meg kell találnod, hogy melyik pont melyik sokszögbe esik bele. Ha nem túl sok kijelölt pontod van (vagyis itt nem túl sok sokszöged), akkor ezt úgy teheted meg, hogy minden ponthoz és minden sokszöghöz megvizsgálod, hogy a pont beleesik-e a sokszögbe. Ez nagyjából &tex;\displaystyle O(l*n) &xet; ideig tart, ha &tex;\displaystyle l &xet; a szakaszok száma és &tex;\displaystyle n &xet; a kijelölt pontok száma, mert minden ponthoz minden sokszög minden élén végig kell menned, vagyis minden szakszon kétszer. Ha sok kijelölt pontod van, akkor ez túl sokáig tarthat. Van hatékonyabb megoldás is, ami csak kvázi-lineáris időt vesz igénybe, de ez az, amit bonyolult megérteni és bonyolult implementálni is. A könyv, amit idéztem, elmagyarázza az erre szolgáló eljárást.

Előzmény: [2008] Hajba Károly, 2015-03-04 17:49:22
[2011] jonas2015-03-04 22:42:47

Ja, és elméleti leírást szeretnél, hogy megértsd a szükséges algoritmust, vagy pedig inkább gyakorlatibb szoftverkönyvtárt, amivel implementálni tudod?

Előzmény: [2006] Hajba Károly, 2015-03-04 13:31:51
[2010] jonas2015-03-04 22:41:38

Úgy érted, hogy a láncok egymást nem keresztezik, csak a végpontjukban találkoznak, vagy esetleg érintik egymást? Az egyes területek sokszög alakúak, és a láncok teljesen körbezárják őket? Ha jól értem a feladatodat, akkor van rá nagyon hatékony algoritmus, de ez nem egyszerű.

Van erről a témáról egy jó könyv, amit ajánlanék. Magyar nyelvűt nem tudok.

Mark de Berg; Otfried Cheong; Marc van Kreveld; Mark Overmars, Computational Geometry; Algorithms and Applicatoins. Springer, "http://www.springer.com/computer/theoretical+computer+science/book/978-3-540-77973-5". Vigyázz, legalább három különböző korú kiadás van belőle.

Előzmény: [2006] Hajba Károly, 2015-03-04 13:31:51
[2009] Hajba Károly2015-03-04 17:51:28

Igen, a vonal az szakasz. Pongyolán fogalmaztam.

Előzmény: [2007] Erben Péter, 2015-03-04 13:49:33
[2008] Hajba Károly2015-03-04 17:49:22

Hosszú magyarázó szöveget írtam, de OK-zásnál elszállt. Most sem időm, sem lelki erőm nincs újból leírni az egészet. Este otthon újból nekiesek és rajzot is készítek hozzá.

Jelenleg nem éles programozási feladat, csak az eljárást kellene kitalálni, meghatározni.

Elvileg akár milliárd pont és szakasz is lehetséges, de ezek több kisebb adott részből adódnak össze. A koordinátaérték max. százmillió.

Szakasz pontja csak már korábban leírt pont lehet.

Előzmény: [2007] Erben Péter, 2015-03-04 13:49:33
[2007] Erben Péter2015-03-04 13:49:33

Ez egy programozási feladat?

Ha igen, akkor szükség lenne még néhány adatra. Például:

- Legfeljebb hány pont lehet?

- Legfeljebb hány vonal lehet? A vonal az egy szakasz? A szakasz végpontjai a fentebb leírt pontok közül kerülnek ki, vagy ezek más pontok?

- Az előforduló koordináták abszolút értékére van felső becslésünk?

- Hány másodperc alatt kell futnia a programnak?

Előzmény: [2006] Hajba Károly, 2015-03-04 13:31:51
[2006] Hajba Károly2015-03-04 13:31:51

Üdv Mindenkinek!

Az alábbi problémába futottam bele, s ehhez kérném a segítségeteket.

-------

Van sok pontom a koordinátarendszer I. negyedének origóhoz közeli elég nagy, de nem végtelen méretű területén egész számú koordinátákkal meghatározva. Van továbbá sok, egymást nem metsző vonalam két különböző ponttal meghatározva. A pontok és vonalak egyedi, sorszám jellegű azonosítóval rendelkeznek, de a sorszámozás és elem (pont, vonal) helye között nincs összefüggés.

A vonalak valamilyen hosszú, elágazásmentes és folytonos láncot (tört vonal) képeznek. A láncok nem rendelkeznek azonosítóval és nincs meghatározva a lánc és az őt meghatározó vonalak közötti kapcsolat. Több lánc egy területet zár körbe oly módon, hogy a láncok csak végpontjuknál csatlakoznak ill. a csatlakozópontnál legalább 3 láncnak kell találkoznia. Minden körbezárt területen belül található egy önálló pont, mely a terület azonosítóját tartalmazza, de nincs meghatározva a terület és a területet meghatározó láncok kapcsolata.

Feladat:

Létre kell hozni a láncok azonosítóját és a vonalak azonosítója és csakis ennek segítségével, sorrend függő felsorolással meg kell határozni (le kell írni) a lánc és az őt meghatározó vonalak közötti kapcsolatot; továbbá a láncok azonosítója és csakis ennek segítségével, sorrend függő felsorolással meg kell határozni (le kell írni) a terület és az őt meghatározó láncok közötti kapcsolatot ill. hozzárendelni a terület azonosítójához.

-------

Még nem mélyedtem el mélyen a problémába, de minden ötlet vagy már valahol fellelhető magyar nyelvű elméleti leírás, mely közelebb vihet a megoldáshoz érdekel és előre is köszönöm.

  [1. oldal]    [2. oldal]    [3. oldal]    [4. oldal]    [5. oldal]    [6. oldal]    [7. oldal]    [8. oldal]    [9. oldal]    [10. oldal]    [11. oldal]    [12. oldal]    [13. oldal]    [14. oldal]    [15. oldal]    [16. oldal]    [17. oldal]    [18. oldal]    [19. oldal]    [20. oldal]    [21. oldal]    [22. oldal]    [23. oldal]    [24. oldal]    [25. oldal]    [26. oldal]    [27. oldal]    [28. oldal]    [29. oldal]    [30. oldal]    [31. oldal]    [32. oldal]    [33. oldal]    [34. oldal]    [35. oldal]    [36. oldal]    [37. oldal]    [38. oldal]    [39. oldal]    [40. oldal]    [41. oldal]    [42. oldal]    [43. oldal]    [44. oldal]    [45. oldal]    [46. oldal]    [47. oldal]    [48. oldal]    [49. oldal]    [50. oldal]    [51. oldal]    [52. oldal]    [53. oldal]    [54. oldal]    [55. oldal]    [56. oldal]    [57. oldal]    [58. oldal]    [59. oldal]    [60. oldal]    [61. oldal]    [62. oldal]    [63. oldal]    [64. oldal]    [65. oldal]    [66. oldal]    [67. oldal]    [68. oldal]    [69. oldal]    [70. oldal]    [71. oldal]    [72. oldal]    [73. oldal]    [74. oldal]    [75. oldal]    [76. oldal]    [77. oldal]    [78. oldal]    [79. oldal]    [80. oldal]    [81. oldal]  

  Regisztráció    Játékszabályok    Technikai információ    Témák    Közlemények  

Támogatóink:   Ericsson   Google   Szerencsejáték Zrt.   Emberi Erőforrások Minisztériuma   Emberi Erőforrás Támogatáskezelő   Oktatáskutató és Fejlesztő Intézet   ELTE   Nemzeti Tehetség Program   Nemzeti
Kulturális Alap