UINA368 Nature Inspired Computing

Filozoficko-přírodovědecká fakulta v Opavě
léto 2018
Rozsah
2/0/0. 4 kr. Ukončení: zk.
Vyučující
doc. Ing. Petr Sosík, Dr. (přednášející)
Garance
doc. Ing. Petr Sosík, Dr.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Cíle předmětu
The listener is provided with knowledge about the most recent trends in research and construction of computers and automata based on non-electric principles. Their common feature is the possibility of massive paralelization while keeping slight dimension of computing elements. These features promise eventually to solve computationally intractable problems. The topics of DNA computing and quantum computing are stressed. 1. Abstract computing classes, Turing Machine with oracle and advice, the problem P versus NP, possible strategies of solution of computationally intractable problems. 2. Why do we need new computing media? Problems of the recent technologies concepts of computing. 3. Quantum computing, bits and qubits, reversibility of computing. Quantum gates and networks, quantum algorithms, quantum parallelism. 4. Deutsch problem XOR, Shore factorization algorithm. The problem of decoherency. The performance of quantum algorithms. 5. DNA computing, elementary properties of DNA. The PCR reaction, denaturation and hybridization, cutting and pasting, separation of molecules with the use of gel electrophoresis. 6. Computing based on recombination and on cutting/pasting. Two- and three-dimensional DNA structures. Possible applications in medicine and nanotechnologies. 7. Further biologically and chemically inspired computing models. Abstract chemical machine, membrane computing. 8. Evolutionary computing, interactive finite automata and interactive Turing machine. Evolutionary lineages of cognitive automata and their performance.
Osnova
  • 1. Úvod: abstraktní složitostní třídy, Turingův stroj s rádcem a nápovědou, problém P versus NP, možné strategie řešení dnes výpočetně nezvládnutelných problémů.
    2. Proč potřebujeme nová média? Problémy objemu aktivních prvků a spotřeby energie dnešní technologie na bázi elektřiny, jejich mechanistické pojetí výpočtu.
    3. Kvantové výpočty, bity a qubity, reversibilita výpočtů. Kvantová hradla a sítě, kvantové algoritmy, kvantový paralelismus.
    4. Deutschův problém XOR, Shorův faktorizační algoritmus (jen idea). Problémy s dekoherencí. Složitost kvantových výpočtů.
    5. DNA výpočty, vlastnosti DNA, komplementarita. PCR reakce, denaturace a hybridizace, stříhání a slepování, separace molekul pomocí elektroforézy.
    6. Výpočty pomocí rekombinace a pomocí stříhání/slepování. Dvou- a třírozměrné DNA struktury. Možné aplikace v medicíně a nanotechnologiích.
    7. Další biologicky a chemicky inspirované modely. Abstraktní chemický stroj, membránové výpočty.
    8. Evoluční výpočty, interaktivní konečný automat a interaktivní Turingův stroj. Evoluční posloupnosti kognitivních automatů a jejich výpočetní síla.
Literatura
    doporučená literatura
  • AMOS, M. Theoretical and Experimental DNA Computation. Springer-Verlag, Berlin, 2005. info
  • Păun, G. Membrane Computing. Springer-Verlag, Berlin, 2002. info
  • GRUSKA, J. Quantum Computing. McGraw-Hill, New York, 1999. info
Výukové metody
Přednáška s aktivizací
Přednáška s analýzou videozáznamu
Metody hodnocení
Zkouška
Vyučovací jazyk
Angličtina
Informace učitele
Účast na nejméně 70% výukových hodin, vypracování závěrečného samostatného projektu a jeho schválení vyučujícím.
Další komentáře
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je zařazen také v obdobích léto 2019, léto 2020, léto 2021.