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: Számtech. OKTV

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]  

Szeretnél hozzászólni? Jelentkezz be.
[228] Róbert Gida2010-06-09 23:58:35

http://programozobajnoksag.com/

[227] RRichi2010-01-28 22:24:27

Megértettem, fairnek tűnik, végiggondolom. Köszönöm a segítséget.

Előzmény: [226] Engedy Balázs, 2010-01-28 19:50:08
[226] Engedy Balázs2010-01-28 19:50:08

Pedig Ágoston már elmondta a jó megoldást, csupán két irányt felcserélt: az első csoportba kerülnek tehát azok, amelyekre ai\leqbi, a másodikba pedig az ai>bi feltételnek megfelelők. Az első csoportot ai szerint növekvően, a második csoportot bi-k szerint csökkenően rendezzük, majd a gépeknek sorban beadjuk az első, majd a második csoportba került elemeket, amilyen hamar csak tudjuk. (Vegyük észre a forgási szimmetriát!)

Hogy ne csak kötözködjek, egy kis hint a bizonyításhoz: induljunk ki egy optimális ütemezésből (tehát ahol nem csak a sorrendet, hanem a végrehajtások pontos idejét is tudjuk minden munkadarabra mindkét gépnél), és mutassuk meg, hogy amikor cserékkel az ütemezés elejére rendezzük ai-k szerint növekvő sorrendbe az első csoport elemeit, illetve a végére bi-k szerint csökkenő sorrendbe a második csoportba tartozó munkadarabokat, akkor az áthelyezések során az optimalitási tulajdonság nem sérül, illetve az ütemezés továbbra is legális marad. (És végül eljutunk a fenti algoritmus által előállított ütemezéshez.)

Előzmény: [225] RRichi, 2010-01-26 16:36:57
[225] RRichi2010-01-26 16:36:57

Ha az egyetemen tananyag, te biztosan tudod a választ, szóval hálás lennék, ha elmondanád...

Előzmény: [221] Róbert Gida, 2010-01-26 14:54:46
[224] RRichi2010-01-26 15:54:50

És A gép mi szerint dolgozik?

Előzmény: [219] HoA, 2010-01-26 11:40:17
[223] RRichi2010-01-26 15:54:09

Ez a 10-20 1-6 1-6 1-6 elemnégyest a 10-20 elemmel kezdené, holott valamelyik 1-6 elemmel kellene.

Előzmény: [220] Ágoston, 2010-01-26 14:17:29
[222] Ágoston2010-01-26 15:03:27

Elnézést, pont fordítva: a szerint növekvőbe, b szerint csökkenőbe...

[221] Róbert Gida2010-01-26 14:54:46

Ütemezéselméletnek hívják ezeket a feladatokat, egyetemen tanítják is. Több, mint valószínű ezt a feladatot is. Szerintem polinom alg. van rá.

Előzmény: [220] Ágoston, 2010-01-26 14:17:29
[220] Ágoston2010-01-26 14:17:29

Egy ötlet: legyen a[i] az A műveletek elvégzési ideje, b[i] a B műveleteké. Válasszuk két csoportba az elemeket: ha a[i]-b[i] nemnegatív, akkor az elsőbe, ha negatív akkor a másodikba. Az első csoportot rendezzük 'a' szerint csökkenőbe, a másikat 'b' szerint növekvőbe. Ekkor a sorrend úgy lesz, hogy először az első csoport rendezetten, majd a második. Ez a sorrend megfelelő lesz (legalábbis szerintem). Tehát az első így kepott elemet beadjuk A gépnek, ha kész akkor a 2. rakjuk A-ba és a készet B-be.

[219] HoA2010-01-26 11:40:17

Arra tudsz példát, amikor nem optimális ha B az A által már megmunkált darabok közül a neki ( B-nek ) legtöbb időt igénylőnek kezd neki?

Előzmény: [217] RRichi, 2010-01-25 21:38:31
[218] RRichi2010-01-25 21:41:57

Um, nem látszik a példaábra amit csináltam,szóval leírom ide is:

1. tárgy: A művelet 8, B művelet 1 időegység 2. tárgy: A művelet 1, B művelet 6 időegység 3. tárgy: A művelet 6, B művelet 3 időegység

Megoldás, A és B gépben is a tárgyak sorrendje:

2. tárgy-> 3. tárgy-> 1. tárgy

Előzmény: [217] RRichi, 2010-01-25 21:38:31
[217] RRichi2010-01-25 21:38:31

Hello mindenki!

Bármely ciki legyen is, elakadtam az egyik 2. fordulós problémával. Úgy sejtem, nincs polinomiális megoldása, de bizonyítani nem tudom, és mindeddig nem találtam tökéletes megoldást, sem én, sem azok, akikkel már beszéltem a problémáról.

A 4. feladatról lenne szó. Adott N tárgy, melyeken A és B gépnek el kell végeznie egy-egy műveletet. Minden tárgyon először A majd utána B műveletet kell elvégezni, egy gép egyszerre csak egy tárgyon dolgozhat. Minden tárgyra adott, hogy mennyi idő alatt tudjuk elvégezni rajta A és B műveletet. A feladat egy olyan program megírása, ami megadja a tárgyak sorrendjét A illetve B gépben (szinte biztos, hogy a két sorrend bizonyíthatóan azonos minden esetben) úgy, hogy minél hamarabb végezzünk az összes tárggyal. Tehát ha adott 3 tárgy,

t: 1. | 2. | 3. A: 8 | 1 | 6 B: 1 | 6 | 3

akkor azokra megadja, hogy az optimális sorrend a 2.->3.->1.

Felmerül ötletként, hogy B szerint csökkenő sorrendben rendezünk, hogy A szerint növekvőbe, hogy B szerint csökkenőbe majd A szerint növekvőbe, hogy A szerint növekvőbe majd B szerint csökkenőbe, A/B szerint növekvőbe, A-B szerint növekvőbe, valamint az is, hogy ha adott egy optimális sorrend n tárgyra, akkor n+1 tárgynál az eredeti n tárgy egymáshoz viszonyított sorrendje nem fog változni, azonban ezekhez mindhez találtunk olyan kombinációkat, amikor hibás adatot produkálnak. Nagyon érdekelne, hogy létezik-e polinomiális algoritmus, vagy ha nem, akkor annak a bizonyítása, hogy a probléma nem oldható meg polinomiális időben.

Válaszaitokat előre is köszönöm.

[216] NemBen2010-01-08 13:59:05

Sziasztok!

Más is tud valamit arról hogy holnap nem 10kor hanem 9kor kezdődik a prog. 2. forduló?

Ez most elég fontos lenne tudnom, mert már így is átrakták Paksról Pécsre(és Szekszárdi vagyok), szóval kilométerből nem lesz hiány...

Kössz,

NemBen

[215] RRichi2008-10-30 00:31:09

Már értelek, így teljesen jó.

Előzmény: [214] Róbert Gida, 2008-10-30 00:24:48
[214] Róbert Gida2008-10-30 00:24:48

Ezért írtam, hogy 2*M*N állapot van összesen, egy kapcsoló minden nyitott ajtót bezár, illetve kinyitja a csukottakat ha rálépünk, így csak az a lényeges, hogy páros vagy páratlan sokszor léptünk kapcsolóra. (i,j,paritás)-sal le lehet írni a helyzetet, (i,j) a labirintusbeli helyed, míg paritás a kapcsolókra történt lépesszámnak a paritása.

Előzmény: [212] RRichi, 2008-10-30 00:10:10
[213] RRichi2008-10-30 00:10:35

És igen... nagyon komplex.

Előzmény: [211] [clayman], 2008-10-04 16:07:49
[212] RRichi2008-10-30 00:10:10

RG-nek üzenem, hogy a labirintus aközben is megváltozhat, miközben kóborlunk benne. Lehet, hogy csak én nem értem jól mit akarsz mondani, de mintha a tiedből ez kimaradt volna...

Előzmény: [204] Róbert Gida, 2008-03-03 02:27:15
[211] [clayman]2008-10-04 16:07:49

Milyen komplexitású megoldásra gondoltál?

Előzmény: [210] RRichi, 2008-10-04 10:21:53
[210] RRichi2008-10-04 10:21:53

Itt egy kis nehezítés a labirintushoz, lehet rajta gondolkodni (én tudom a megoldást, csak a hecc kedvéért adom föl...):

Adott egy M*N-es labirintus. Minden mezőjén vagy ajtó van, vagy kapcsoló, vagy semmi. Minden kapcsolóhoz megadjuk, hogy mely ajtó(ka)t kapcsolja, valamint minden ajtóhoz a kiindulási helyzetét. A zárt ajtó falként, a nyitott semmiként viselkedik.

Adjuk meg, hogy hogyan lehet a legrövidebb úton eljutni az (1;1) pontból az (M;N) pontba!

[209] kdano2008-03-04 19:09:18

ja, ennyire nem vagyok benne a programozásban :P

Előzmény: [208] Róbert Gida, 2008-03-03 23:08:27
[208] Róbert Gida2008-03-03 23:08:27

Én is ezt írtam: bfs=breadth first search, magyarul szélességi keresésnek hívják.

Előzmény: [207] kdano, 2008-03-03 22:42:30
[207] kdano2008-03-03 22:42:30

Hát ha nem Dijkstra, akkor Dijkstra light, ismertebb nevén szélességi bejárás :P

Előzmény: [204] Róbert Gida, 2008-03-03 02:27:15
[206] kdano2008-03-03 22:25:56

http://home.fazekas.hu/~kdano/misc/DNS.PAS

Ez a megoldásom 5 pontot ért a 15-ből, mivel benne felejtettem egy hülye debuggoló sort.. 5 pont az öt helyes első sor, tehát valószínűleg ettől függetlenül a program jó. Nem igazán volt kedvem ismét felfogni, hogy mit csinál a program, úgyhogy ez a debuggoló sor még mindig benne van. Egyébként fogyaszd egészséggel.

Előzmény: [203] nadorp, 2008-03-02 21:20:06
[205] nadorp2008-03-03 12:27:47

Kösz, ennyi segítség már elegendő lesz.

Előzmény: [204] Róbert Gida, 2008-03-03 02:27:15
[204] Róbert Gida2008-03-03 02:27:15

A labirintus marha egyszerű: összesen ugye M*N mező van, de azt is kell tudnod, hogy páros sokszor léptél kapcsolóra vagy sem, azaz 2*M*N állapot van (ha páros sokszor akkor minden ajtó úgy van, ahogy eredetileg volt, különben pont fordítva). Legrövidebb utat keresünk egy start állapot között és egy vége állapot között (vigyázz, mert ez kétféle, aszerint, hogy a végén páros vagy páratlan sokszor léptünk a kapcsolóra), hát mi a túró, ha nem Dijkstra algoritmusa! Bár ezt bfs-el is meg lehet oldani O(M*N) időben és tárban.

A DNS-t nem tudom hogy kell, bár az utóbbi hónapokban kb. 5 ilyen feladatot csináltam meg, ha ez is ebbe a kategóriába tartozik, akkor O(L1*L2) időben megoldható, ahol L1,L2 a két string hossza. A feladat őse Levenshtein távolság problémája, wikipedia-n fent van, ez persze nem az OKTV feladat, de szerintem valami hasonló lesz itt is a megoldás.

Előzmény: [203] nadorp, 2008-03-02 21:20:06

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]