Komentáře k článku

DNA počítače: technologie nespí

Na stránkách Zdrojáku se věnujeme především záležitostem bezprostředně spojeným s vývojem webu a webových aplikací. Pojďme se dnes vydat za hranice webu a současných počítačů a představme si technologii, kterou nepohání čipy a tranzistory – DNA počítače. Zůstanou jen hříčkou, nebo jejich masivní paralelismus pomůže řešit velmi složité úlohy?

Zpět na článek

13 komentářů k článku DNA počítače: technologie nespí:

  1. Vodpik

    NP x co-NP

    Jestli si to jeste dobre pamatuju ze skoly, tak problem obchodniho cestujiciho by nemel byt NP-uplny problem, ale co-NP uplny problem. Uz v clanku je napsano, ze u NP-uplneho problemu je problem nalezt reseni, ale pokud to reseni dostanu, tak jednoduse overim, ze jde o reseni. Pokud ale nekomu dam reseni, ze zrovna tahle cesta je ta nejkratsi, tak jak dotycny overi, ze je opravdu nejkratsi? Tezko. Musi projet vsechny moznosti (polynomialni cas), aby overil, ze neexistuje jine KRATSI reseni. A jestli si to dobre pamatuju, tak temhle uloham se rika co-NP.

    1. ps

      Re: NP x co-NP

      np uplny to je. figl je v tom, ze ten rozhodovaci problem formulujes ne jen jako exitujici cestu, to bys sis nepomoh, jak sam spravne soudis, ale jako existujici cestu levnejsi nez x.
      tezko rict z vagni verze tveho podani, ale myslim, ze nemas jasno ani v co-np.

      1. Vodpik

        Re: NP x co-NP

        Ano, pokud ukol definuju jako „Jestli existuje cesta“, nebo „Jestli existuje cesta kratsi nez x“, pak se jedna o NP-uplny problem. Zcela jednoduse polynomialne overim pravdivost, ze jde o reseni, pokud ho dostanu. Nicmene v clanku je napsano, ze se hleda „nejkratsi cesta“, ale v tom pripade uz nejde o NP-uplny problem, ale jen o NP problem.
        Jinak jestli je co-NP-uplna uloha nebo co-NP, tak to uz presne nevim, ale mam pocit, ze co-NP-uplne ulohy jsou doplnkem k NP-uplnym uloham, takze by melo jit o co-NP-uplnou ulohu.

        1. Czenek

          Re: NP x co-NP

          Problém obchodního cestujícího, intuitivně definovaný jako, „nalézt nejkratší cestu přes všechna zadaná města“ není NP-complete, ale NP-Hard.
          Třída NP-Hard je v podstatě optimalizační verze NP-complete, tedy hledání maximálního/mi­nimálního prvku.
          Problém je NP-complete, jen když na něj lze odpovědět ANO x NE a pro odpověď ANO existuje P algoritmus na ověření.
          Tedy NP-complete verze obchodního cestujícího je, jak už bylo napsáno výše, „Existuje cesta kratší než dané X“?
          coNP-complete je třída úloh, kde se zase musí odpovídat pouze ANO x NE a pro odpověď NE existuje P algoritmus na ověření. Takže když se na otázku „Existuje cesta kratší než X“ odpoví NE, tak ji ověříme stejně snadno jako odpověď ANO.
          Takže NP-complete verze obchodního cestujícího je i v co-NP.

          1. freon

            Re: NP x co-NP

            mate v tom vsichni hokej
            NP je trida VSECH (tedy i lehcich) problemu, ktere lze „uhadnout“ (orakulum) na nedeterministickem turingove stroji v polynomialnim case.
            co-NP je trida takovych problemu, jejichz doplnek lezi v NP. Doplnek rozhodovaciho problemu znamena, ze se prohodi odpovedi ANO a NE.
            NP-hard neformalne: kazdy problem z NP je lehci neho stejne tezky nez problem z NP-hard. Formalneji: existuje NP-complete problem, ktery lze polynomialne redukovat na ten NP-hard. „polynomialne redukovat“ = redukce musi byt uskutecnitelna polynomialnim algoritmem.
            NP-complete je trida takovych problemu, ktere jsou NP-hard, a navic jsou v te tride NP, pac obecne NP-hard problemy nemusi byt ve tride NP (muzou byt tezsi, treba ve tride EXPTIME). Jinymi slovy, kdybychom meli polynomialni algoritmus na reseni nejakeho libovolneho NP-uplneho problemu, tak pak muzeme resit libovolny jiny problem z tridy NP v polynomialnim case (pac reseni i ta redukce je v polynom. case a polynom + polynom = polynom).
            K tomu TSP. TSP je NP-complete, kdyz je to postaveno jako rozhodovaci problem, tedy jako „Lze projit vsechna mesta maximalne x kilometry?“ a NP-hard kdyz je to postaveno jako optimalizacni problem.
            snad sem to nezkonil

  2. _r3450n_

    Radioaktivni DNA?

    Me by zajimalo kteremu expertovi napadlo primichavat DNA ktera bude svetelkujici nebo radioaktivni. To by melo diki mutacim katastrofalni nasledky. Vysledky by byli znacne zkreslene, protoze mutace ktere radioaktivita pusobi, neumime nijak predvidat. Je to jako by nekdo predstavoval nove widle a chlubil se, ze se da do widel doinstalovat virus ktery udela z jednicek nuly a z nul jednicky a mozna i dvojky a trojky :)

    1. Martin Malý

      Re: Radioaktivni DNA?

      Od DNA ke genovým mutacím způsobeným radioaktivitou je ještě dlouhá cesta a spousta mezičlánků, nehledě na to, že mutace se týkají replikované DNA; na popsané šmrdlání DNA řetězců ve zkumavce má značení radioaktivními izotopy naprosto minimální vliv. Nesmíte všelijakým zeleným tu jejich propagandu proti radioaktivitě a mutacím zase tak baštit… ;)

      1. Vojta

        Re: Radioaktivni DNA?

        Radioaktivně značené proby (sondy) se běžně používají při řadě analytických metod, kdy v DNA hledáme nějakou konkrétní sekvenci. Taková klasická metoda (používaná dříve hlavně ve fylogenetice a fylogeografii) je Southern blotting, kdy DNA nejdřív rozsekám, pak to promíchám s radioaktivně značenou sondou, vyberu tu DNA, kam se sonda navázala a s ní dál pracuji.

  3. Jan

    Slozitost

    S tema DNA vypoctama si stejne moc nepomuzem, i kdyby se podarilo vyresit vsechny ty technologicke mouchy. Ty NP-uplne problemy umime resit s exponencialni casovou slozitosti, coz plus minus odpovida tomu, ze prohledavame cely prostor reseni, ktery je exponencialne velky vzhledem k delce vstupu. Ten DNA vypocet musi pouzit odpovidajici mnozstvi molekul – exponencialne vzhledem k velikosti vstupu. Vlastni cas prohledavani muze byt maly, ale velikost procitace exponencialne poroste s velikosti vstupu, a brzo (nekolik stovek mest? nebo uz nekolik desitek?) by hmostnost potrebne DNA presahla hmotnost zeme. Takze ano, muzeme resit NP-uplne ulohy, ale nebude to skalovat o nic lip nez s pouzitim klasickych pocitacu.

    1. pavel houser

      Re: Slozitost

      ano, je to myslim tak, viz ona „hmotnostni bariera“ v clanku. asi casto pujde nejak obejit, jenze pak zase bude exponencialni cas (na to obchazeni, na izolaci vysledku…).
      nicmene i tak by zcela teoreticky mohlo byt reseni na DNA pocitaci o nekolik radu rychlejsi nez na klasickem superpocitaci, byt slozitost by v zavislosti na vstupu stale rostla exponencialne. od urcite doby se ale o to de facto prestali pokouset, myslim.

Napsat komentář

Tato diskuse je již příliš stará, pravděpodobně již vám nikdo neodpoví. Pokud se chcete na něco zeptat, použijte diskusní server Devel.cz

Zdroj: https://www.zdrojak.cz/?p=3241