OptMod-2017/Gyakorlat11

A MathWikiből
A lap korábbi változatát látod, amilyen Kkovacs (vitalap | szerkesztései) 2017. november 21., 11:57-kor történt szerkesztése után volt.

Múzeum

Egy múzeumnak megfogyatkozott támogatás miatt változtatásokat kell tennie. Az elsõ változtatás, hogy kevesebb biztonsági õrt alkalmaz. Míg eddig minden teremben volt egy biztonsági õr, mostantól az ajtókban fognak állni, hogy két termet tudjanak felügyelni. Határozzuk meg a szobák lefedéséhez szükséges létszámot és az õrök elhelyezkedését, ha a következõ a múzeum alaprajza (minden termet figyelni kell):

Muzeum.png


DNS

Hasonló sorozatok helytakarékos tárolása

A DNS-ek feltérképezésének egyik praktikus problémája a hosszú egymástól nem sokban különböző azonos hosszúságú DNS-ek praktikus tárolása. Most egy egyszerűsítsük a problémát bináris sorozatok esetére. Két sorozat között definiált a Hamming-távolság: Sum(i) |a_i - b_i| , azaz azon bitek száma amelyeket át kell billenteni hogy megkapjuk a másik sorozatot. Amíg a Hamming-távolságok nem túl nagyok, érdemes egyetlen sorozatot eltárolni illetve a különbségeket amivel a többi sorozat felírható. Magyarázd el, hogyan lehet ezt minimális feszítőfa keresésével megoldani, illetve add meg a megoldást Excel vagy AMPL segítségével (AMPL előnyben)!

A sorozatok:

  1. 011100011101
  2. 101101011001
  3. 110100111001
  4. 101001111101
  5. 100100111101
  6. 010101011100
Személyes eszközök