Česky
Kamil Dudka

Study

File detail

Name:Downloadbin.txt [Download]
Location: study > min
Size:60.4 KB
Last modification:2009-06-26 20:53

File content

Copyright (c)  2009  Kamil Dudka.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.2
or any later version published by the Free Software Foundation;
with no Invariant Sections, no Front-Cover Texts, and no Back-Cover
Texts.  A copy of the license is included in the section entitled "GNU
Free Documentation License".

--
- kurz je volitelný a proto nás bude bavit
- od příštího roku bude povinný pro nějaký nový obor

- věda ... získávání nových poznatků, které nemusí být okamžitě využitelné
- inženýrství ... vydělávání peněz (plnění společenských požadavků)
--

- budou se vyrábět inteligentní systémy
    - které jsou schopny se adaptovat
    - které jsou schopny se samy obnovit

- teoretické a *fyzické* limity počítání
- rekonfigurovatelné zařízení
- vhodná literatura ještě není k dispozici, vyjde v říjnu '09

Biologií inspirované počítače
-----------------------------
- inspiraci hledáme obvykle v biologii, výjimečně někde jinde
- pod pojmem počítač máme na mysli HW/SW
- design:
    1. tradiční - běžně používané postupy /konvenční/
    2. netradiční - postupy pro klasickou informatiku podivné
                  - přesto v některých případech velmi funkční
                  - nekonvenční

- živé systémy jsou odolné proti chybám
- jsou schopny řešit jiné problémy, než pro které byly vyvinuty
- různé vědy se na pojem "život" dívají různě
- život z pohledu biologie:
    - samoorganizovaná vnitřní struktura
    - schopnost samoregulace
    - metabolismus, růst
    - reaktivní chování
    - schopnost reprodukce

- z našeho pohledu je život důsledkem *emergence*:
    Vznik složitého globálního chování na základě lokální interakce komponent
    systému (bez centrálního řízení).

    - př.: hejno ptáků (není organizované globálně)

- různé přístupy:
    1. redukcionismus ... všechno je možné rozložit na jednotlivé komponenty
        - typický příklad inženýrství (počítač vidíme jako hierarchii)
        - v praxi ne vždy funguje

    2. holismus ... celek je vždy něco víc než souhrn jeho částí

    3. epistemologie - část filozofie zabývající se poznáním
                     - př.: evolučním alg. získáme řešení, u kterého nedokážeme
                            vysvětlit, proč funguje

- samoorganizace
    - 2. termodynamický zákon říká, že v izolovaném systému všechno spěje
      k chaosu (s časem se zvyšuje entropie, neurčitost)

    - ukázalo se, že živé systémy nejsou izolované
    - disipativní struktura - otevřený dynamický systém, který vykazuje
                              dynamickou samoorganizaci
    - v buňce jsou organizované struktury, které snižují míru uspořádání svého
      okolí

- Rayleigh-Bénardův jev
    - samoorganizace jako fyzikální jev
    - kapalina zahřívaná zdola a ochlazovaná shora
    - při výměně teplé a studené kapaliny se molekuly začnou nějakým způsobem
      koordinovat

Atraktor
--------
    Atraktor dynamického systému je množina stavů, do kterých systém směřuje.

- př.: fázorový diagram kyvadla
- může být (kvazi)periodický, ale taky *chaotický*

Chaos
-----
- chaos je deterministický systém popsatelný matematicky
- velmi citlivý na vstupní parametry, počáteční podmínky
  (malá změna na vstupu způsobí velkou změnu na výstupu)
- př.: jakýkoliv relevantní model počasí

Bifurkace (rozdvojení)
----------------------
- velké změny v dynamickém systému na základě nepatrné změny parametru
- zachycuje se v tzv. bifurkačním diagramu
- bifurkační bod ... rozdvojení
- chaos ... posloupnost bifurkačních bodů

Logistická rovnice
------------------
- máme populaci lidí, chceme zjistit velikost populace v určitém čase
- pokud by populace rostla rychle ... nebylo by dost zdrojů
  (potřeba penalizovat nadměrnou produkci)
- pro logistickou rovnici neexistuje analytické řešení

Celulární automat
-----------------
- příklad samoorganizace
- my se budeme zabývat pouze lineárním automatem
- př.: úloha "majorita", N=149
- lze pozorovat emergentní chování, samoorganizaci

Umělý život
-----------
    Umělý život je metoda, jejíž podstatou je generovat z jednoduchých
    spolupracujících mikroskopických prvků takové chování na úrovni
    makroskopické, které je možno interpretovat jako projev života.

- opakem evoluce je revoluce, což je cesta, která obvykle nefunguje
- v živých systémech je vysoká míra paralelismu
- známý příklad umělého života: Tierra
    - virtuální počítač simulován na normálním počítači
    - kód počítače je schopen se množit
    - tento kód může být mutován/rekombinován
    - programy běžící v OS bojují o čas a paměť
    - dokonce vznikají komunity mezi programy
    - "evoluční závody ve zbrojení" ... predátor/oběť

- př.: swarm robots
    - skupinka malých robotů
    - nejsou organizovány centrálně
    - komunikace je pouze lokální na základě strategie
    - ve složitém terénu se dokázaly spojit do řetězu
    - inspirace v chování hmyzu (mravenci, roje, ...)

- různé postoje k umělému životu
    silný umělý život - považován za skutečný (stejně jako psa, dítěte)
                      - zatím se nikomu dost dobře nepodařilo

    slabý umělý život - život je simulován na počítači
                      - poznatky získané simulací mohou být užitečné

    - podobné v umělé inteligenci (Turingův test)

Biologický přístup
------------------
- řízená metoda pokus/omyl

Tradiční umělá inteligence
--------------------------
- metoda shora dolů
- funguje dobře pro snadno definovatelné problémy (e.g. šachy)

Výpočetní inteligence (softcomputing)
-------------------------------------
- alternativa k tradiční umělé inteligenci
- funkčním modelem je lidská mysl
- inspirace v procesech (DŮLEŽITÉ):
    fylogeneze - evoluce
    ontogeneze - vývin mnohobuněčného organizmu
    epigeneze - vývoj nervového systému, imunitního systému, ...

- v tomto kurzu budeme inteligentní techniky strkat do HW (e.g. FPGA)
    natural computing ... počítání podle přírody


Limity abstraktního a fyzického počítání
========================================

Algoritmus
----------
    Algoritmus je přesně definovaná konečná posloupnost příkazů (kroků) (které
    jsou vybírány z předem definované konečné množiny elementárních příkazů),
    jejichž prováděním pro každé přípustné vstupní hodnoty získáme po konečném
    počtu kroků odpovídající hodnoty výstupní.

    Intuitivně algoritmem rozumíme postup, který nás dovede k řešení úlohy.

- implementace algoritmu může být různá (univerzální počítač, FPGA, LEGO)
- "počítačem" může být i kbelík hmoty (návrh pomocí evolučních technik)

Problém nekonvenčních počítačů
------------------------------
- nejasná definice *výpočtu*
    - musí být výpočet vázán na manipulaci se symboly? (u NN není)
    - může mozek provádět výpočet?
    - ... zasahuje částečně do filozofie

- limity počítačů ... teoretická informatika
    - teorie automatů ... modely výpočtů
    - teorie vyčíslitelnosti ... které problémy jsou/nejsou řešitelné
    - teorie složitosti ... cena výpočtu

    - neříká, jestli provádí příroda "výpočet"
    - neříká, jak souvisí fyzické a abstraktní počítání

Turingův stroj
--------------
- klasický Turingův stroj neumožňuje zasahovat do výpočtu
- univerzální Turingův stroj ... program stroje je na pásce
- existence nerozhodnutelných problémů ukazuje na meze algoritmizace

Chomského hierarchie
--------------------
- existují jazyky bez formálního základu
- jazyků typu 0 je spočetně mnoho
- ale všech jazyků je více :-)
- ... je otázka jestli činnost mozku leží mimo třídu 0
- existují také další výpočetní modely, které jsou ekvivalentní TS

Church-Turingova teze
---------------------
    Turingovy stroje (a jim ekvivalentní systémy) definují svou výpočetní
    silou to, co intuitivně považujeme za efektivně vyčíslitelné.

- nelze dokázat matematicky (příliš vágní)

Fyzická Church-Turingova teze
-----------------------------
    Libovolná funkce, kterou je možné fyzicky vypočítat, může být vypočtena
    pomocí Turingova stroje.

Gödelovy věty a meze formalizace
--------------------------------
- pan Gödel byl podivín (kniha Neúplnost)
- narodil se v Brně (je po něm pojmenovaná posluchárna E112)
- objevil meze formálních systémů
- algoritmus je taky formalizmus
    - má omezení
    - není schopný dělat to, co mozek

    "věta o úplnosti" - všechny platné formule lze ve formálním systému odvodit

- věty o neúplnosti:
    I. věta o neúplnosti
        - každá netriviální bezesporná teorie je neúplná
        - existují tvrzení, která nelze dokázat ani vyvrátit
        - netriviální ... obsahuje Peanovu aritmetiku

    II. věta o neúplnosti
       - v dostatečně silné rekurzivní bezesporné teorii nelze dokázat její
         vlastní bezespornost

Super-turingovské výpočetní modely
----------------------------------
- např. stroj, který udělá každý další krok za poloviční dobu
    - pokud sečteme délku všech kroků, dostaneme 2 časové jednotky
    - jsme schopni vyřešit HP v konečném čase
    - pěkně se řeší na papíře, ale hůře se implementuje

- O-stroj (Turingův stroj s orákulem)
    - orákul umožňuje "věštit"
    - zeptáme se dopředu, kudy jít

- ideální neuronová síť je také silnější než Turingův stroj

Van Leeuwen & Wiedermann
------------------------
- interaktivní Turingův stroj
- jsme schopni řešit nerozhodnutelné problémy, ale ne ty, které nás zajímají

Abstraktní vs. fyzické stroje
-----------------------------
- pozn.: analogové počítače

Heisenbergův princip neurčitosti
--------------------------------
- přesnost měření je v mikrosvětě omezena
- není možné přesně určit hybnost a polohu zároveň
- součin (ne)přesností je vždy větší než Planckova konstanta:
    \Delta_r \Delta_p >= h

--
- na písemce umět spočítat max. frekvenci kila hmoty:
    E = m c^2
    f = 2E/(\pi \cdot h)

- v kilu hmoty je možné uložit max. cca 10^31 bitů dat

Meze zvyšování hustoty integrace na čipu
----------------------------------------
- Mooreův zákon není možné udržet do nekonečna
- určeno minimální energií, která je nutná pro překlopení log. 0/1
- limitní hustota integrace je 10^13 switchů na cm^2 (velikost 1.5 nm)
- limitní frekvence 25 THz
- tohle jsou pouze teoretické hranice (ne praktické)
- problém zejména s odváděním tepla (a taky přiváděním energie)
- zpřesnění modelu: přidání bariéry mezi 0/1 (nutné pro zabránění kmitání)
- čím menší je element ... tím více potřebujeme energie k udržení informace

Reverzibilní výpočty
--------------------
- pro výstup jsme schopni spočítat odpovídající vstup
- výhodnější z pohledu energie, entropie
- reverzibilní hradlo musí realizovat bijektivní zobrazení
- na písemce budeme určovat, jestli je hradlo reverzibilní podle tabulky

--
feature size ... 45nm u Intel Core 2


Rekonfigurovatelný HW
=====================
- začalo v oblasti digitálních obvodů před asi 30 lety (PAL)
- v polovině 80. let přišlo FPGA
- dostalo se dokonce do analogové oblasti:
    FPTA = Field Programmable Transistor Array
    FPAA = Field Programmable Analog Array

    - ale také rekonfigurovatelné antény

- implementuje se obvykle pomocí multiplexů (digitální vs. analogové)
- funkci můžu implementovat pomocí lookup tabulky (v FPGA)
- také lze vytvořit např. rekonfigurovatelné zrcadlo
  (deformace membrány pomocí napětí převedeného na elektrody)
  --> celá řada rekonfigurovatelných optických systémů

- konfigurovatelné molekuly :-) ... podívat se na VA charakteristiku
- zajímavý experiment s kapalnými krystaly (také umožňují výpočet)

Digitální rekonfigurovatelná zařízení
-------------------------------------
- funkce obvodu je určena konfiguračním řetězcem (bitstream)
    - ten může ovlivnit řídící signály multiplexu
    - může ovlivnit obsah lookup tabulky
    - řetězec je uložený v konfigurační paměti

- konfigurační paměť může umožňovat různou četnost přístupů
- někdy jsou k dispozici dvě konfigurační paměti (umožňuje přepnutí kontextu)
- dnes mohou být konfigurační řetězce dosti objemné
- konfigurační řetězec obvykle vytvoříme nástrojem od Xilinxu na základě VHDL
- pokud potřebujeme konfigurační řetězec měnit za běhu, nachystáme si dopředu
  několik řetězců, které můžeme za běhu nahrávat

- způsoby rekonfigurace (bude na zkoušce):
    1. statická rekonfigurace - rekonfigurace obvodu pouze během odstávky
    2. dynamická rekonfigurace - alespoň část obvodu vykonává užitečné operace
    3. úplná rekonfigurace - starší FPGA, pouze celý čip najednou
                             (i když ve skutečnosti měníme jen část)
    4. částečná (parciální) rekonfigurace - není potřeba měnit celý
                                            konfigurační řetězec najednou
    5. interní rekonfigurace - mohu pomocí jedné části čipu rekonfigurovat
                               jinou část čipu
    6. externí rekonfigurace - konfigurační data se sypou "z venku"

- přepnutí kontextu - změna konfigurace obvodu na žádost
                    - např. nahraji obvod pro dělení
                    - je potřeba rychlá rekonfigurace

- granularita rekonfigurace:
    A. jemnozrnná (fine-grain) - jsme schopni rekonfigurovat základní elementy
                                 dané architektury
    B. hrubozrnná (coarse-grain) - pouze na úrovni staveních bloků
                                   (dělička, ...)

Využití rekonfigurace
---------------------
    (bude na zkoušce)

    a) upgrade firmware
    b) zvyšování funkční hustoty
    c) zvyšování spolehlivosti
    d) zajištění adaptace

Princip obvodů PLD
------------------
- PAL, PLA, GAL, ...
- známe z INC
- programovatelná propojovací matice
- existují různé varianty
- typicky se programují pouze jednou
- typické využití:
    - adresové dekodéry, konečné automaty
    - glue logic = spojovací logika

- zpětná vazba umožňuje realizovat sekvenční obvody

CPLD = Complex PLD
------------------
- lze si představit jako hierarchickou strukturu PLD obvodů
- vhodně propojené
- lze realizovat složitější logické obvody
- někdy výhodnější než FPGA (zejména kvůli ceně)
- konfiguraci nelze měnit tak často jako v FPGA

FPGA (Field Programmable Gate Array)
------------------------------------
- umožňuje zvýšit výkon až 10000x proti architektuře s univerzálním procesorem
- původní využití bylo 1x naprogramovat (vícekrát jenom při vývoji obvodu)
- v poslední době vznikají aplikace s dynamickou konfigurací
  (na čipu se dynamicky vytváří různý HW :-) )

- je potřeba znát základní pojmy (slice, clb, ...)

- FPGA je matice logických bloků
- blok se dá naprogramovat
- programovatelné vstup-výstupní buňky
- a propojky, které jsou také programovatelné

- konfigurační paměť je distribuovaná po čipu
- navíc hotové komponenty, které zvýší efektivitu návrhu (e.g. řadič PCI
  sběrnice)

- logický blok:
    - lookup tabulka pro 4 vstupy
    - $2^16$ kombinací ... 16 bitů v konfigurační paměti FPGA
    - často implementované obvody jsou implementované na úrovni HW
      (obvody pro práci s přenosem sčítačky)

- existují dva typy propojení (jakýsi přepínač, multiplex)
    A. krátká - rychlá (propojují sousední bloky)
    B. dlouhá - propojení objektů, které jsou daleko od sebe na čipu
    C. globální hodinový signál, reset, ...

    - multiplexy zaberou asi 90% plochy čipu
    - ASIC, který dělá stejnou věc, musí být rychlejší/menší

- externí rekonfigurace FPGA lze provádět ve dvou módech
    1. master - FPGA samo generuje řídící signály
    2. slave - rekonfigurace řízena externím zařízením (microkontrolérem)

- firma Xilinx (ale i ostatní) tají formát konfiguračního řetězce
    --> problém s evolucí
    - náhodně vygenerovaný řetězec může FPGA obvod rozbít

- postup návrhu:
    1. systémový návrh
    2. kódování návrhu      --> RTL
    3. syntéza              --> netlist
    4. konfigurace FPGA

- důležité pojmy (bude na zkoušce):
    CLB - skládá se ze dvou slice(s)
    slice - dvě lookup tabulky, dva klopné obvody, spec. logika (carry, ...)

    frame - z konfiguračního pohledu je obvod rozdělen do rámců (frames)
          - nejmenší jednotka (parciální) rekonfigurace

- CLB, slice na zkoušce 100% budou
- dále na zkoušce bude otázka:
    Kolik je potřeba lookup tabulek pro implementaci 7vstupé lookup tabulky?

- není problém za běhu rekonfigurovat obsah lookup tabulek, problém je
  s propojením
- jedna disertační práce se zabývala reverzním inženýrstvím pro zjištění
  konfiguračního řetězce

- výrobci FPGA vždy používají nejmodernější technologii ASIC na trhu

- interní rekonfigurace je k dispozici od Xilinx Virtex II
  (frame, viz. ^)

- řada Virtex II Pro: navíc dva procesory PowerPC
    - navíc RocketIO porty
    - lze připojit např. na gigabitový ethernet

- řada Virtex 4: tři typy FPGA obvodu
    LX - velké množství logiky, paměť
    FX - podobné Virtex II Pro
    SX - vytvořen pro DSP aplikace

- řada Virtex 5:
    - LUT (LookUp Table) mají 6 vstupů
    - hard IP bloky (řadič PCI Express, RocketIO, ...)
    - AD převodník

- také Atmel vyrábí FPGA
    - na čipu je procesor, který také umí rekonfigurovat
    - řešení pro malé systémy
    - interní formát konfigurace je k dispozici proti podpisu

- obvod v FPGA zabere asi 100x víc plochy na čipu než ASIC

IP jádra
--------
- IP = Intelectual Property
- designéři nepracují od nuly, nakoupí hotové komponenty (IP cores)
- existují různé varianty
    soft makra - na úrovni (V)HDL
    firm makra (net list) - konkrétní HW implementace (RTL)
    hard makra - rozmístění pro konkrétní FPGA

    - různé úrovně podle toho, jak moc do toho potřebujeme vrtat
    - víme předem, kolik zaberou plochy na čipu

Dynamická rekonfigurace
-----------------------
- plochu FPGA rozdělíme na několik částí...
- ve vhodných okamžicích pošleme rekonfigurační data

- dnes se používají FPGA jako součásti Blade serverů

Rekonfigurovatelné analogové obvody
-----------------------------------
- důvod: reálný svět je analogový
- zpracování v analogové oblasti je mnohdy přirozenější
- analogové obvody jsou mnohem pomalejší (pracují s nižšími frekvencemi)
- typické aplikace:
    laditelný frekvenční filtr
    různé regulátory
    ...

- typy obvodů:
    FPAA - založené na spínaných kapacitorech
         - 4 programovatelné bločky

    FPMA - smíšené digitální/analogové obvody

    FPTA - tranzistory (univerzitní platforma)
         - lze stáhnout kompletní informace o vnitřní struktuře

    FPTA2 - větší bloky tvořené z tranzistorů

- výrazně méně programovatelných bloků než u FPGA
- několik principů:
    1. spínané kapacitory
       - rezistor zabere strašně moc místa na čipu
       - proto se nahrazují pomocí tzv. spínaného kapacitoru
       - spínače se realizují pomocí tranzistoru
       - řízeno digitálním obvodem
       - simuluje odpor
       - podívat se na schéma (jednoduché/zajímavé)
       - je potřeba splnit vzorkovací teorém

    2. Transkonduktanční operační zesilovač (OTA)
       - výstup není napěťový, ale proudový
       - vstupy sledují napětí
       - zesílení není napěťové, ale proudové (zesílení lze nastavit)
       - transkonduktance je přenosová vodivost
       - lze použít pro vyšší frekvence než spínané kapacitory

- návrh analogových obvodů není dobře algoritmizovatelný
- analogové obvody jsou velmi citlivé na vnější vlivy (prostředí, ...)
- pomocí rekonfigurace lze analogové obvody za běhu přizpůsobit na změny v
  prostředí

Rekonfigurovatelné procesory
----------------------------
- vědět, že existují


Evoluční design
===============

Darwinova teorie evoluce
------------------------
- vznik druhů přirozeným výběrem
- základní předpoklad je, že každý organizmus má v průměru víc než jednoho
  potomka (nadměrná reprodukce)
- také pozoroval, že jedinci se liší :-)
- z genetického pohledu se ale jedinci neliší tak moc
- vědělo se, že vlastnosti organizmu se dědí

- ale dědí se pouze genetická informace, ne vlastnosti získané v průběhu
  života
- některé organismy se rozmnožují pohlavně i nepohlavně
- geny nejsou lepší/horší, vhodnost závisí vždy na prostředí
- přirozený výběr ... vznik účelných vlastností (některé organismy vidí, ...)

- dnes je teorie považována spíše za předchůdce moderních teorií
    - nelze vysvětlit altruismus
    - dědičnost vloh není měkká, ale je tvrdá
    - nevěděl nic o mutacích, Medelových experimentech

Gen
---
    Vloha pro určitou vlastnost. Z pohledu molekulární biologie je to souvislý
    úsek DNA.

Alela
-----
    Varianta genu.

Genotyp
-------
    Kombinace alel, které nese ve svých buňkách konkrétní jedinec.

Genom
-----
    Souhrn všech genů, které se vyskytují v buňkách daného jedince.

Tvrdá dědičnost
---------------
    Vlohy se předávají z generace na generaci v nezměněné podobě.
    (prokázal Mendel)

Měkká dědičnost
---------------
    Vlohy se mohou měnit pod vlivem ostatních vloh přítomných v daném jedinci
    a v důsledku prostředí.
    (předpokládal Darwin)

Selekční tlak
-------------
    Tlak, kterým působí prostředí na určitou populaci tím, že z ní odstraňuje
    nositele určitých znaků.

Makroevoluce
------------
    Evoluční děje nad úrovní druhu.

Mikroevoluce
------------
    Evoluční děje uvnitř druhů nebo populací.


Neodarwinismus
--------------
- evoluční biologie se stává normální vědou
- ve 20. letech objeveny mutace (pravděpodobnost lze uměle zvýšit)
- ve 30. letech objeveny specializace (vznikání nových druhů)
-  v 50. letech objevena struktura DNA

- neutrální evoluce ... teorie, která říká, že za všechno může náhoda
    genetický drift - náhodná fixace některých alel
    genetický draft - fixace neutrálních a někdy i škodlivých alel
                    - př.: změna barvy očí je neutrální mutace

- další problém: biologická zdatnost nositele určité alely závisí na četnosti
  výskytu této alely v populaci (např. samičky si vybírají samečky podle toho,
  jaký je většinový vkus populace)

Sobecký gen
-----------
- Dawkins '76 (něco jako novodobý Darwin)
- evoluce neprobíhá na úrovni druhů ani jedinců, ale na úrovni genů

Zamrzlá evoluce
---------------
- Flegr, nesouhlasí s Dawkinsem
- k evoluci dochází pouze při vytváření nového druhu (Darwinova evoluce)
- po delší době se však nahromadí nová variabilita a druh se již nemění
- druh evolučně zamrzne a neodpovídá na selekční tlak

Konvenční design
----------------
- založen na použití pravidel / lidských zkušeností
- návrhový přístup shora-dolů, dekompozice
- velmi informovaný proces

- lze také chápat jako úlohu prohledávání
- prohledání prostoru možných designů

Automatické generování designů
------------------------------
    1. zakódování designu (do podoby (konečného) řetězce)
    2. ohodnocení kvality designu
    3. vymyslet způsob jak generovat nové designy

- často si neuvědomujeme, že prostor možných designů obsahuje taková řešení,
  která se nepodobají těm konvenčním

Různé algoritmy prohledávání
----------------------------
    a. náhodné prohledávání (slepé)
    b. hill climbing
       - prohledává se *okolí* bodu
       - okolí je třeba vhodně definovat
       - např. jednobitové záměny v binárním řetězci
    ...

Evoluční algoritmy
------------------
- nepracují s jedním řešením, ale s populací
  (paralelně prohledávají prostor)
- používají se biologií inspirované operátory: křížení a mutace
- využití v návrhu obvodu:
    genotyp - konfigurační řetězec
    fenotyp - výsledné zapojení obvodu
    fitness - např. počet správně vypočtených bitů pro všechny kombinace

- pojmy: gen, chromozom, fenotyp, populace

Selekce
-------
    1. ruleta
    2. podle pořadí - nezáleží na absolutní hodnotě fitness
    3. turnaj - na půlsemce budu počítat pravděpodobnost, že se něco vybere
    4. deterministicky - vybere se K nejlepších

TODO - mrknout na příklad

--
- podívat se na vztah pro výpočet doby evoluce

Základní typy evolučních algoritmů
----------------------------------
- 4 základní typy:
    genetický algoritmus
    - klasika
    - binární/celočíselný chromozom pevné délky
    - mutace/křížení

    genetické programování
    - kandidátní řešení je spustitelná struktura
    - většinou stromově orientované
    - vysoký počet jedinců (tisíce), málo generací

    evoluční strategie
    - vymysleli inženýři z Německa
      (při optimalizaci křídla letadla)
    - parametry evoluce jsou součástí chromozomu

    evoluční programování
    - jedna z prvních evolučních technik
    - dnes už se moc nepoužívá

No Free Lunch Theorem
---------------------
- volný překlad: "nic není zadarmo"
- pokud uvážíme dostatečně velkou množinu problému, všechny algoritmy mají
  "v průměru" lepší výkonost
- náš algoritmus může být pro daný problém horší než náhodné prohledávání
- důsledek: algoritmus je potřeba ladit pro konkrétní problém/úlohu
- v umělé inteligenci je potřeba do metody vložit co nejvíce znalostí
  (domain knowledge)
- u GA znalosti vložíme v podobě fitness funkce / operátoru křížení
- dobrá reprezentace řešení: malá změna chromozomu změní fitness málo

Evoluční optimalizace
---------------------
- o výsledku musím už předem hodně vědět
- výsledek není výrazně překvapivý a principielně inovativní

Evoluční design
---------------
- nahradíme kreativního designéra strojem
- většinou funguje v podobě asistence s designérem
- evoluční algoritmus nám vždy poskytne nějaké řešení (i když je hloupé)
- soutěž Humies - výsledky musí splňovat určitá kritéria

Kartézské genetické programování
================================
= Cartesian Genetic Programming (CGP)
- nepoužívá se křížení
    - v některých publikacích je zmíněno, ale většinou nepřináší užitek
    - křížení obecně funguje jenom na problémech, které mají určité vlastnosti

- populace se používá proto, aby se dal prostor prohledávat paralelně

- kandidátní řešení se reprezentuje v podobě 2D grafu
- implementujeme v poli programovatelných elementů
- do metody opět musíme vložit nějakou znalost (např. ze kterých bloků se bude
  řešení skládat)

- podívat se na definici CGP (počet řádků/sloupců, vstupů/výstupů, L-back
  parametr, množina/počet funkcí)
    L-Back ... jak vzdálené bločky můžu propojovat
        =1 ... můžu propojovat pouze sousední sloupečky

- podívat se na zakódování struktury v chromozomu:
    - dvě čísla ... kam zapojím vstupy
    - poslední číslo udává funkci

    --> dohromady (pro všechny bloky) dostanu řetězec fixní délky
    - ne všechny hodnoty řetězce jsou platné

- převod genotypu na fenotyp bude na zkoušce (bude tam chyták - funkce NOT)
- délku genotypu lze snadno spočítat

Mutace v CGP
------------
- může se změnit funkce uzlu
  (při změně z binární na unární se mění topologie!!)
- nebo propojení vstupu
- nebo propojení výstupu

- některé mutace mohou být neutrální
    - např. 3x NOT místo 1
    - nebo mutace nepoužitého bloku
      (může se projevit skokově až po nějaké době, kdy se blok připojí)

Evoluční algoritmus v CGP
-------------------------
- používá se evoluční strategie: $ES (1 + \lambda)$
    - jako rodič se bere 1 nejlepší jedinec
    - vytvoří se $\lambda$ mutantů
    - $\lambda$ je obvykle 4 --> vytvoří se 4 další
- je potřeba zachovat diverzitu populace

- princip:
    1. náhodně se vygeneruje počáteční populace (1 + \lambda jedinců)
        - nebo se vygeneruje 1000 náhodných jedinců a vyberou se nejlepší
        - nebo se použije nějaké konvenční řešení jako základ pro evoluci

    2. ohodnocení jedinců pomocí fitness
    3. nalezení nejlépe ohodnoceného jedince
    4. vygenerujeme $\lambda$ potomků pomocí mutace
    5. nová populace
    6. kontrola ukončující podmínky

- vědět jak se paralelizuje evaluace na 32/64bit procesoru
- na zkoušce bude příklad:
    "Na kolikrát se bude počítat obvod s 9 vstupy na 32bit procesoru?"

Evoluční návrh obvodů
=====================
- problém je v tom, že evoluční návrh není příliš škálovatelný
- EHW = Evolvable HW ... kombinace evolučního algoritmu a rekonfigurovatelného
  zařízení

- ohodnocení kandidátních řešení je časově kritická operace
    --> rekonfigurace musí být rychlá (ideálně v paměti RAM)

- náhodný konfigurační řetězec by neměl zničit rekonfigurovatelný obvod
- evoluci lze provádět na různých úrovních abstrakce
- chromozomy mohou obvod popisovat přímo/nepřímo

- teď několik termínů, které je dobré vědět na zkoušku:
    extrinsic evolution - kandidátní obvody jsou ohodnocovány v simulátoru
                        - výsledné řešení se pak použije pro konfiguraci

    intrinsic evolution - kandidátní obvody jsou ohodnocovány pomocí EHW

    mixtrinsic evolution - některé obvody vyhodnocovány v simulátoru
                         - některé obvody vyhodnocovány v čipu

    unconstrained evolution - návrhář neklade žádná omezení konfiguračního
                              řetězce

    constrained evolution - návrhář např. zakáže zpětnou vazbu

- různé způsoby ohodnocení:
    digitální obvody - Hammingova vzdálenost
                     - u velkých systémů se nepracuje se všemi vstupními
                       hodnotami

    analogové obvody - vyhodnocuje se v časové oblasti
                     - např. frekvenční charakteristika

- vztah výpočtu doby evoluce:
    t = G (P \cdot t_{eval} + t_{np})

Dvě základní použití EHW
------------------------
1. pouze ve fázi návrhu
   - evoluce může běžet měsíc
   - potom se začne sériově prodávat

2. skutečný EHW
   - vyvíjející se HW
   - evoluční algoritmus je součástí systému
   - např. pošleme nějaké zařízení do vesmíru
   - pokud nastane nečekaná událost, evoluce se spustí sama

Evoluce s otevřeným koncem
--------------------------
- to co teď probíhá na Zemi :-)
- dopředu nevíme, co všechno nastane za dobu životnosti navrhovaného zařízení
- evoluční alg. může běžet neustále na pozadí a vylepšovat funkci systému

Klíčový experiment A. Thompsona
-------------------------------
- ukázal, proč je důležité provádět intrinsic evolution
- řešení může využít některých vlastností HW, které simulátor zanedbává
- vznikl obvod, který byl více analogový než digitální (divoké zpětné vazby)
- problém přenositelnosti takto vzniklého řešení

Škálovatelnost evolučního návrhu
--------------------------------
- dobře funguje na malých příkladech
- rozděluje se na dva problémy:

    1. škálovatelnost reprezentace
    - reprezentace řešení pomocí chromozomu
    - do řešení je dobré vložit nějakou znalost, např. nějaké bloky místo hradel
    - další řešení je inkrementální evoluce
    - development - znovu-používání hotových modulů

    2. škálovatelnost evaluace kandidátních řešení
    - volba vhodné trénovací množiny
    - není možné testovat všechny kombinace v průběhu evoluce
    - další možnost je odhad hodnoty fitness

Akcelerace evolučního návrhu v FPGA
-----------------------------------
- dokáže 50x urychlit evoluci
- používají se tzv. virtuální rekonfigurovatelné obvody (VRC)
    - rekonfigurovatelný obvod vytvořený v FPGA
    - genetická jednotka, fitness jednotka
    - zřetězený výpočet i rekonfigurace (viz. obrázek)
    - mrknout na vztah výpočtu doby pipe-line výpočtu (?)

- umět vypočítat délku konfiguračního řetězce v bitech

Metody dekompozice
------------------
    1. dekompozice z pohledu výstupů
       - obvod se rozděluje na moduly počítající výstupy
       - rekurzivně
       - tato dekompozice není příliš užitečná
       - problém s vysokým počtem vstupů

    2. Shannonova dekompozice (z pohledu vstupů)
       - multiplexor na výstupu přepíná, který vstupní blok se použije
       - úloha na písemku:
            - systém, který má 8 vstupů
            - jak udělat dekompozici tak, aby moduly měly 5 vstupů
            - jak bude řešeno přepínání

- problém rozložíme na menší problémy
- rozkládáme tak dlouho, až dostaneme složitost, kterou můžeme řešit evolučním
  algoritmem

- inkrementální evoluce se používá pro návrh klasifikátoru
    - např. klasifikace dopravních značek
    - navrhneme postupně obvody pro rozpoznávání jednotlivých značek
    - obvody potom pracují paralelně
    - ten který se vybudí nejvíc se bere jako výsledná značka

    - takto navržené řešení je potom potřeba optimalizovat, abychom snížili
      počet hradel (hledají se společné podfunkce)

- o evolučním návrhu sekvenčního obvodu není tolik publikací jako
  o kombinačních
    - základním modelem je Mooreův automat
    - navrhneme kombinační logiku pro výpočet následujícího stavu
    - navrhneme kombinační logiku pro výpočet výstupu

    - zajímavým příkladem je automat pro predikci hodnoty 0/1 na základě
      historie předchozích hodnot


Evoluční návrh analogových obvodů
=================================
- příkladem jsou systémy MEMS
    - snažíme se kombinovat mechanické věci s elektronikou
    - ale děláme to na čipu
    - např. gyroskop, různé senzory

- ale také antény, ...
- návrh struktur je hodně založen na magii
    - důležitou roli hraje zkušenost designéra (jak antény fungují)
    - evoluční návrh může najít zajímavá řešení

- když trochu změníme CGP, lze použít i pro návrh analogových obvodů
- jiný přístup představují stromové struktury (GP)
    - sem dej cívku, sem kondenzátor, ...
    - proslavil prof. Koza
    - navrhují se analogové filtry, stabilizátory, regulátory, A/D převodníky

- u analogových obvodů je potřeba věnovat pozornost kompenzaci různých
  negativních vlivů (prostředí, ...)

Návrh analogových obvodů pomocí GP
----------------------------------
- ze stromu jsme schopni získat schéma obvodu
- strom zkonvertujeme na tzv. netlist
    - složený z komponent FP..
    - zápis ve tvaru matice
    - př.: RC článek sl. 3/33
    - používá se Spice (něco jako ModelSIM pro VHDL)

    - netlist se pošle do simulátoru Spice
    - dále se pošle informace o tom, co se má s obvodem dělat
    - simulátor je šikovný / časově náročný

- některé uzly stromu nemají žádný význam (např. "otoč drát")
- strom ... předpis jak zkonstruovat filtr z embrya
- na zkoušce budeme navrhovat fitness funkci pro pásmový filtr

- pan Koza je bohatý muž, který má GP jako zálibu, a živí se něčím jiným
- nevýhodou metody je vysoká výpočetní náročnost
- důležitá je evaluace v HW (může snížit složitost o 3 řády)
- problém s vysokou citlivostí na hodnoty součástek
    --> "rohová analýza"

Evoluční optimalizace antén
---------------------------
    1. evoluční optimalizace - máme zadaný nějaký tvar, hledáme parametry
    2. evoluční návrh antén - hledáme nový typ antény

- instrukce "vytvoř drát" (nějaké velikosti, orientace, ...)
- je potřeba uvažovat nějaký materiál, parametry prostředí
- v grafu je znázorněný zisk antény (vyzařovací diagram)
    - jiný diagram pro směrovou anténu
    - jiný diagram pro všesměrovou anténu
    - lze vypočítat (nebudeme se zabývat tím, jak se to dělá)

    - vyzařovací diagram je vstupem evoluce

- podívat se na obrázek
- pomocí evoluce se navrhovala jedna část antény, která se pak zopakovala 4x
- jednalo se o drátový typ antény, ale jsou i jiné typy
  (např. anténa vyleptaná na plošném spoji)

Evoluční návrh v FPTA-2
-----------------------
- děláme něco trochu jiného
- máme rekonfigurovatelné analogové zařízení
- zařízení má nějaký bit-stream
- není potřeba vymýšlet složité mapování

- vyvinuto pro NASA
- evoluční alg. implementován v DSP

- digitální hodnoty se převedou na analogové
- zpracují se testovaným obvodem
- potom se analogové hodnoty převedou zpět na digitální

- snažíme se minimalizovat chybu obvodu
- výsledkem fitness je přímo diference

- některé propojky rekonfigurovatelného obvodu můžeme rozpojit napevno
- designér může do evoluce vložit nějakou znalost
- pro návrh robustních obvodů je potřeba výrazně zesložitit fitness funkci


Adaptivní HW
============
- přizpůsobení funkce HW za provozu
- skutečný EHW (evoluční alg. běží na pozadí)

- změna specifikace
- změna charakteru vstupních dat
- obejití poruchy obvodu

- evoluční algoritmus může být součástí aplikace, nebo může být řízen vzdáleně
- problém s tím, že negarantuje řešení v určitém čase

- tyto systémy příliš nevyhovují teoretické informatice
- používají se jiné formální modely než Turingův stroj

--
- Rad-Hard ... odolné proti radioaktivnímu záření (do určité míry)

Autonomní sebeoprava
--------------------
- pro vyhodnocení fitness se používají tzv. referenční buňky
- pokud se z referenční buňky vrátí jiná než očekávaná odezva, spustí se
  sebeoprava
- nalezený konfigurační řetězec se pošle do ostatních (tzv. funkčních) buněk
- používají se traskonduktanční zesilovače

- "je potřeba vědět, že existuje nějaký referenční signál, který generuje
  nějaká referenční buňka; a pokud je schopna se opravit referenční buňka, tak
  jsou schopny se opravit také ostatní (funkční) buňky"

Čip pro bezztrátovou kompresi obrazu
------------------------------------
- problematika elektrofotografických tiskáren (JBIG standard)
- doba přenosu dat do tiskárny určuje rychlost tisku
- pracuje se s velkými obrázky a vysokým rozlišením
- snaha snížením objemu přenášených dat zvýšit rychlost tisku
- princip bezztrátové komprese pomocí prediktoru
- přenáší se rozdíl mezi predikovanou a skutečnou hodnotu pixelu
- ideální kompresní poměr dostaneme z prediktoru, který přesně padne na
  přenášená data

- obrázek se rozdělí na bloky, pro každý blok se zvolí vhodný prediktor

Kalibrace IO po výrobě
----------------------
- laditelný filtr
- pracuje na principu traskonduktančních OZ
- efektivita produkce zvýšena na 97% (z původních asi 50%)
- navíc se podařilo snížit plochu/příkon
- použili velmi jednoduché obvody, ale přeladitelné
- využívá se v mobilních telefonech

Evoluční robotika
-----------------
- kontrolér pro robota lze navrhnout evolučně
- pokud kontrolér vyvíjíme pomocí simulátoru, je pravděpodobné, že v reálném
  prostředí nebude fungovat

- zajímavý článek o souběžné evoluci těla a kontroléru robota


Development
===========
- znamená: fitness nepřiřadím přímo chromozomu, ale napřed musím vygenerovat
  výsledek, který se dá teprve potom vyhodnotit (zabudování developmentu
  do evolučního designu)

- neplést s evolucí
- vývoj (development) je produktem evoluce
- lze použít přímé/nepřímé zobrazení genotypů na fenotypy
- v přírodě vývoj nikdy nekončí

- Kozova metoda představuje jednoduchý příklad developmentu
- při evoluci na úrovni hradel máme velký problém škálovatelnosti

- potřebujeme zkrátit délku chromozomu a navrhovat složitější systémy
- to jsou protichůdné požadavky, které řeší přidáním znalosti:
    1. inkrementální evoluce
    2. evoluce na úrovni funkčních bloků

- z informatického pohledu je development způsobem *komprese*
  (dekomprese se potom provádí při evaluaci jedince)

- vznik samouspořádání

- mechanismus je potřeba navrhnout chytře a s ohledem na danou aplikaci
- složitost výsledného řešení potom nezávisí na délce chromozomu
- umožňuje modulární návrh
- získáme lepší evolvabilitu
- interakce genotypu s prostředím může vézt k emergentnímu chování fenotypu

- jedna biologická buňka je "složitější" než nejmodernější počítač :-)

Nukleotid
---------
- cukerný fosfát + báze
- nukleotidy tvoří abecedu:
    A - adenin
    T - thymin
    C - cytosin
    G - guanin

DNA
---
- řetězce dvojšroubovice jsou komplementární (vodíkové můstky):
    A - T (2 vodíky)
    C - G (3 vodíky)

Člověk
------
- 23 párů chromozomů
- asi 20000 genů
- ne všechny "písmena" nesou informaci
- některá jsou potom "sestřihnuta"

Proteiny
--------
- naše tělo je postaveno převážně z proteinů
- jak protein vypadá, určují geny (syntéza proteinů)
- typická lidská buňka obsahuje asi 10000 proteinů

Enzymy
------
- speciální typ proteinu
- katalyzátory (urychlovače) chemických reakcí

Ústřední dogma molekulární genetiky
-----------------------------------
- bude na zkoušce
- podívat se na obrázek; zkusit si nakreslit (!!)

RNA
---
- existují různé teorie, které vysvětlují proč DNA/RNA
- původně byla pravděpodobně jenom RNA
- později (u vyšších org.) se pak vytvořila DNA

- je méně stabilní než DNA
- bylo objeveno, že řetězec RNA se čte po trojicích
- trojici se říká Kodon

Kodon
-----
- existuje 64 kombinací, ale jenom 20 aminokyselin
- kódování je redundantní

Buněčné dělení
--------------
- oplodněná buňka se začíná dělit
- buňka se vždy dělí na dvě
- počet buněk roste exponenciálně a tak roste organismus

- existují dva typy dělení:
    1. mitóza - nepohlavní
              - vznikají klony

    2. meióza - redukční buněčné dělení
              - základ pohlavního rozmnožování
              - pohlavní buňky se nazývají gamety

Development v biologii
----------------------
- jednobuněčnému embryu se říká zygota
- proces se nazývá development (embryogeneze)
- buňky se specializují
- embryo mění svůj tvar
- buňky se specializují (červené krvinky, ...)
- některé buňky při výstavbě odumřou - např. blány mezi prsty
  (s tím se počítá)

- genetická informace nekóduje celého jedince, ale pouze předpis
  pro vybudování jedince

- typicky je určitý znak organismu ovlivněn větším počtem genů
- typicky jeden gen ovlivňuje více znaků organismu

Genetická regulační síť (GRS)
-----------------------------
- modelují vztahy mezi geny a proteiny
- něco takového se dá naprogramovat
- a dá se tím něco řídit

- porucha v GRS může zapříčinit, že někdo nemá ruce, nebo má 4 ruce

Diference buněk
---------------
- pokud se buňka specializuje, znamená to, že generuje jinou kombinaci
  proteinů, než generují ostatní buňky

--
- existují i tzv. kmenové buňky, které se dokáží přeměnit na jiný typ

Výpočetní development
=====================
- souhrnný název pro více oblastí

L-systémy
---------
- jde o jakousi (divočejší) gramatiku
- gramatika není přesně svázána pevně definovanými pravidly
- ale je to perfektně formalizovaná věc
- model byl primárně zaveden pro popis biologických systémů

- paralelní přepisovací systémy
- pracuje nad abecedou - např. tři typy buněk
- potom máme určitý axiom (startovací řetězec)
- množina přepisovacích pravidel
- ale oproti TI dochází k paralelnímu přepisu všech buněk
- všechny pravidla se provedou v jednom kroku!!

- příklad: Kochova vločka (viz. obrázek)
- takovým strukturám se říká fraktály
- můžeme takto velmi jednoduše generovat i složité tvary

- existují různé modifikace L-systémů
    - můžou být deterministické/nedeterministické
    - může být konečný řetězec tvořen pouze terminálními systémy

    - lze zavést různé omezovací podmínky
        - zakazující/podmínkové L-systémy
        - množina F ... Forbidding set

    - parametrické L-systémy

- příklad ... evoluční návrhu stolu :-)

- L-systémy je vhodné používat tam, kde se vyskytují nějaké "opakující se
  motivy"

- na zkoušku vědět: abeceda, axiomy, množina pravidel, paralelní přepisování

Maticová gramatika
------------------
    TODO

Genetické regulační sítě
------------------------
- používají se dvojice podmínka/akce
- systém je dynamický
- pokud existuje jakýsi protein p, potom dojde k tomu, že je exprimován gen,
  který vlastně způsobí následně něco

- v okolí buňky je nějaký protein ... podmínka


Celulární automaty
==================
- 1D, 2D, ...
- 1 buňka má konečný počet možných stavů
- buňka se mění na základě lokální přechodové funkce
- stavy jsou (v základním modelu) aktualizovány synchronně, v diskrétních
  krocích

- podle pravidel se dělí na uniformní/neuniformní
- konfigurace ... počáteční stav všech buněk v čase 0

- vědět co znamená pravidlo 250 u 1D automatu s radiem 1
- rozdělují se do 4 tříd (podle Wolframa ... program Mathematica):
    1. skončí v homogenní konfiguraci (vyvíjí se, pak to "celý zčerná")
    2. konečná perioda
    3. generovaný vzor se zdá být téměř náhodný
    4. lokálně nepravidelné struktury

- klasifikace ... pomocí výpočtu parametru lambda (Langton)
    - musíme si určit počet sousedů
    - počet stavů buňky
    - počet pravidel, které vedou do klidového stavu
    --> podívat se na vztah pro výpočet

    - lambda je v intervalu <0,1>
    - pokud je nízká, tak se informace nepřenáší (umrzne)
    - pro vznik "života" je potřeba něco mezi náhodností a trivialitou

- 2D sousedství:
    Von Neumannovo ... 5 buněk
    Mooreovo ... 9 buněk

- sebe-replikace
    - určité struktury se mohou samy replikovat při vhodných pravidlech
    - poprvé ukázal Von Neumann (v 50. letech, na papíře, matematicky)
    - Von Neumannův univerzální konstruktor ... struktura, která naklonuje
      vstup a navíc sama sebe (!!)
    - zajímavé z pohledu HW

    Langtonova smyčka
    - 8/9 stavů (drobné modifikace)

- aplikace:
    - nejsou main-stream
    - používají se jako RNG v HW
    - simulace (šíření požáru, doprava ve městě, ...)
    - jedna z metod netriviálního mapování genotypu na fenotyp


Embryonální HW
==============
- moderní HW funguje s dostatečnou spolehlivostí
- dnešní procesor obsahuje asi $10^10$ komponent, každá z nich funguje a tím
  pádem to funguje jako celek

- pokud bychom ale měli $10^20$ komponent, tak máme problém udržet
  spolehlivost

- proto hledáme inspiraci v živých systémech --> redundance
- v lidském těle je obrovská redundance
- provádí se návrh s ohledem na spolehlivost

- elementární komponenty jsou obvykle tvořeny molekulárními strukturami
  (které se natáčí, nebo vedou/nevedou proud, ...)

- spolehlivost:
    Obecná vlastnost objektu spočívající ve schopnosti plnit požadované funkce
    při zachování hodnot stanovených provozních ukazatelů v daných mezích a
    čase podle stanovených technických podmínek.

    (podle normy: pravděpodobnost bezchybné činnosti)

- vanová křivka (čas zahoření, konst. poruchovost, stárnutí systému)
- MTBF = Mean Time Between Failures

- tří-modulová redundance (TMR)
    - bude na zkoušce
    - uděláme 3 kopie modulu
    - na výstup dám hlasovací zařízení, které dá na výstup majoritu

    - někdy se moduly navrhují nezávislými týmy podle jednotné specifikace
    - po určité době má ale TMR horší poruchovost (viz. graf)

    - tzv. statická redundance

- také existuje tzv. dynamická redundance
    - není žádný hlasovací obvod
    - máme chytrý obvod pro detekci poruch
    - moduly se přepínají až při chybě

- pokročilejší je hybridní redundance (kombinace dvou předchozích)
- tři typy redundance:
    1. obvodová (TMR, ...)
    2. informační (ECC, Hamming)
    3. časová (opakování výpočtu)

Embryonální elektronika
-----------------------
- projekt Embryonics
- inspirace redundancí v živých systémech
- vychází z CA, lokální interakce
- výsledný systém se chápe jako mnohobuněčný organismus
- dvě základní operace:
    1. buněčné dělení - pravdivostní tabulka se kopíruje k sousedům
    2. buněčná diferenciace (specializace)

- podívat se na obrázky (pěkné)

Cell Matrix
-----------
- architektura inspirovaná CA
- i buňky, které jsou někde uprostřed, se dají nějak rozumně konfigurovat
  (a přitom k nim nevedou drátky)

- masivně paralelní, parciálně rekonfigurovatelná architektura
- buňka může fungovat jako výpočetní jednotka i jako konfigurátor okolních b.
- 2D/3D struktury, různé typy sousedství

- buňka má na každé straně 4 dráty
    D_in/D_out - datové
    C_in/C_out - konfigurační

- buňka má dva módy (D-mód, C-mód) ... podívat se, jak zhruba fungují
- neuniformní CA
- distribuovaná rekonfigurace (!!)
- architektura je přirozeně škálovatelná (není problém přidávat buňky)

- superbuňky
    - buňky složené z buněk
    - dokážou detekovat chyby
    - redundance
    - autonomní sebe-oprava

- existuje ASIC 8x8 buněk, FPGA konfigurace, simulátor (bude na cvičení)

POE model
---------
- klasifikace biologií inspirovaných architektur
- podívat se na obrázek modelu
- tři osy (P, O, E)
- buď jeden směr, nebo dvoj-, trojkombinace


DNA počítače
============
- zopakujeme si něco z biologie/genetiky
- Leonard Adleman ukázal, že jde použít DNA jako médium
- využívá se podobnosti s operací nad řetězci
- opakování DNA (viz. ^), ústřední dogma molekulární genetiky

- genetický kód ... kodon (kód je redundantní)
- operace s DNA:
    replikace
    štěpení
    třídění podle velikosti
    ...

--
- na zkoušku je dobré vědět, jak vypadá DNA
    - že to je posloupnost nukleotidů
    - čtyři písmenka
    - ústřední dogma
    - kodon, amino, bílkoviny, ...
--

Replikace DNA
-------------
- úloha enzymů
- výsledkem replikace jsou dvě dvojšroubovice
- založeno na tom, že vlákna jsou komplementární
- žlutému (na obr. sl. 11/59) řetězci se říká templát (něco jako šablona)

- místu dole (sl. 12/59) se říká replikační vidlička - tam pracují enzymy
- enzym DNA-polymeráza je schopen opravovat chyby vzniklé při replikaci

Štěpení DNA
-----------
- máme dva řetězce, které potřebujeme říznout v jednom bodě
- k tomu se používají restrikční endonukleázy
- je otázka, kde vzít látky, které řežou tuto strukturu na správném místě
- střih může být kolmý, nebo takový divný, křivý

Oddělení fragmentů DNA podle velikosti
--------------------------------------
- používá se "Gelová elektroforéza"
- řetězce mají polaritu
- po voležení do elektrického pole se začnou pohybovat k opačnému náboji
- menší molekuly se začnou pohybovat rychleji, větší pomaleji
- podle toho, kam řetězce dolezly, lze poznat, jak byly dlouhé

Spojování DNA
-------------
- používají se enzymy zvané "ligázy"
- jsme schopní získat řetězce, které se v přírodě nevyskytují (?)

Denaturace DNA
--------------
- zahřátím DNA na vyšší teplotu (asi 90-100 stupňů)
- nebo zvýšení pH
- vlákna DNA se rozdělí

Renaturace DNA
--------------
- opačný proces
- vlákna se naopak spojují dohromady

Hybridizace
-----------
- k ní dochází, pokud mají řetězce komplementární báze
- používá se k detekci sekvencí (tam kde je komplementarita, se řetězec naváže)
- detekce podřetězce
- např. nějaký podřetězec má vliv na to, že člověk do 20ti let zemře
- existují různé genetické nemoci
- pokud by se tato informace dostala do nějakých institucí, tak by nás nemuseli
  pojistit apod. :-)

DNA sonda
---------
- řetězec s malou délkou (do 120 nukleotidů)
- dají se synteticky vytvořit

Množení DNA a PCR
-----------------
    PCR = Polymerase Chain Reaction
        - na zkoušce nebude
        - je to způsob, jak namnožení udělat

DNA počítání
============
- vznikl obor DNA computing
- experiment provedený v roce 1994
- publikován v prestižním časopisu Science a způsobil revoluci
- vyřešil problém Hamiltonovské cesty v grafu pomocí DNA
    - NP-úplný problém
    - jednodušší varianta zjišťuje, jestli cesta existuje
    - výstupem složitější varianty je nalezená cesta
    - viz TSP

- principem řešení bylo náhodné vygenerování různých řetězců (cest), nejlépe
  všech možných
- celý proces počítání spočívá v tom, jestli mezi nimi existuje cesta, která nás
  zajímá
- problém filtrace (co zbude ve zkumavce)

- v prvním kroku se vyhodí cesty, které začínají nebo končí špatně
- potom se odstraní cesty, které mají špatnou délku
- potom se odstraní cesty, co nejsou cesty (opakují se vrcholy)

- každému uzlu grafu je přiřazen oligonukleotid (musí být různé)
- každé hraně grafu je přiřazen oligonukleotid, vzniklý spojením polovin
  oligonukleotidů zdrojového a cílového uzlu (potom lze využít navázání pomocí
  komplementarity)

- působením DNA-ligázy se náhodně generují průchody grafem
- potom se použije PCR ke znásobení cest vedoucích ze zdrojového do cílového
  uzlu, zbytek se odplaví
- potom gelová elektroforéza
- potom afinitní čištění (vytvoří se komplementární řetězec a zkouší se, jestli
  tam je) - nejnáročnější část - složitost: O(n)
- nakonec se ověří existence molekuly kódující Hamiltonovskou cestu

- celková časová složitost je O(n)
- problém je, že potřebujeme exponenciálně mnoho materiálu
- laboratorní experiment nebylo jednoduché zopakovat

Formalizace výpočtu DNA
-----------------------
- všechny operace se provádí nad strukturou Tube (zkumavka)
- pracuje se s abecedou, multimnožinou řetězců
- základní operace:
    merge    - sjednocení
    amplify  - vytvoření kopie obsahu zkumavky
    detect   - vrací TRUE, pokud zadaná zkumavka obsahuje aspoň jeden řetězec
    separate - nejsložitější operace - mají se vytvořit dvě látky (rozdělením)

- příklad za domácí úlohu: sl. 46/59
- pro usnadnění života se přidávají dvě operace:
    length-separate
    position-separate

- pomocí těchto operací lze Adlemanův experiment formalizovat

SAT problém pomocí DNA computing
--------------------------------
- tím se zabýval Lipton
- řeší se přesně naopak než Hamiltonova cesta
- máme jednotná data, ale pouštíme na ně různé funkce
- na zkoušce budeme kreslit graf pro SAT problém

- 3-SAT problém je speciální případ SAT, kdy v každé formuli jsou 3 proměnné


Nanotechnologie
===============
- většina toho byla řečena/ukázána už v tom filmu
- Mooreův zákon ... zmenšování elementárních prvků
- podle Intelu Mooreův zákon přežije CMOS, potom přijdou nanotechnologie
- myšlenka přišla už v roce 1959
- nano-objekty se prohlíží rastrovým tunelovacím mikroskopem
- tunelování ... teče proud a úměrně proudu se něco zobrazuje na monitoru
  (nesouvisí s optickým mikroskopem)
- potom ještě existuje AFN mikroskop, který umožňuje měřit bez elektřiny
  (laserový paprsek)
- na zkoušky znát tyto dva základní principy

- pomocí mikroskopu můžeme hmotu také ovlivňovat

- kvantové celulární automaty
- už dnes existuje naprosto bezpečný (integrita) přenos pomocí nano-drátů

- nás zajímá, kde se využily evoluční alg. v designu

- dnešní výroba čipu ... postup shora dolů
- u nanotechnologií se používá postup zdola nahoru
  (důsledek *samoorganizace*)

- když kreslíme nano-nápis mikroskopem, tak to je postup shora dolů
- složité systémy mají nepravidelnou strukturu (problém syntetizovat)

- hlavní problém je dnes s cenou technologie
- důležité jsou myšlenky, které jsou levné / dají se dobře prodat
- porovnává se třeba podle poměru \$ / jedno hradlo

- existuje celá řada způsobů, jak vytvořit molekulární tranzistor

Kvantové celulární automaty (QCA)
---------------------------------
- neodpovídá CA podle definice
- struktura, která se dá fyzicky realizovat pomocí kvantových teček
- oblast může držet *právě* jeden elektron (ne 2, 3, ...)
- systém se popisuje pomocí kvantové mechaniky, struktury vykazují kvantové
  vlastnosti

- princip bude na zkoušce
    - jedna buňka QCA je realizována pomocí 4 kvantových teček
    - v jedné buňce jsou právě dva elektrony
    - stav buňky je reprezentován pozicí teček (viz. obrázek)
    - elektrony se nemůžou dostat do jiné konfigurace než do těch dvou na obr.
      (energeticky velmi nepravděpodobný stav)

- obrovské množství buněk na malé ploše
- koncept předpokládá pravidelné rozložení buněk, aby to nějak rozumně fungovalo
- podívat se, jak vypadá QCA invertor

- základní princip: majorita - pomocí 5-ti buněk QCA ... počítá medián (!!)
- AND/OR hradlo se počítá pomocí majority (konfigurační vstup)
- na písemce bude otázka:
    "Co je potřeba připojit na konfigurační vstup, aby to počítalo AND"

Evoluční design vs. molekulární elektronika
-------------------------------------------
- viz. experiment A. Thompsona
- ale nekonfigurujeme FPGA, ale molekuly
- na tom pracoval tvůrce CGP se svým doktorandem

- experiment s kapalnými krystaly (běžný LCD display, který se dá koupit)
- evoluce našla v LCD displeji tónový diskriminátor

NanoCell
--------
- podobný koncept jako u kapalných krystalů
- nemá nic společného s Cell Matrix
- ze čtyř stran jsou klasické elektrické vývody
- tečky jsou nanočástice zlata
- mezi tečkami jsou molekulární přepínače
    - základem molekulárního přepínače je chemická struktura
    - provádí se hodně výzkumu, jak udělat molekulární přepínač
    - podívat se na VA charakteristiku
    - přepínačů je syntézou vyrobeno obrovské množství

- obvod se potom konfiguruje tak, aby dělal, co potřebujeme
- používají se evoluční postupy
- př: sčítačka

Rekonfigurovatelné zrcadlo
--------------------------
- používá se membrána, pod kterou jsou ve vhodných místech umístěny zdroje
  napětí, které ji deformují a tím mění tvar zrcadla

- vhodnou konfigurací zrcadla se dá z divokého signálu udělat "pěkný" obraz
- používá se v astronomii
- ví se, že dochází ke zkreslení informace, která prochází přes atmosféru
- snaha reprodukovat původní (nepoškozený) obraz pomocí optického korektoru
- optický korektor funguje na bázi deformovatelného zrcadla

- jedna z metod, jak zkoumat dynamické jevy (femto-/atosekundy)
- záleží na tom, jaký má tvar impuls z laseru
- potřebujeme, aby se objevilo co nejvíce harmonických zadaného typu
- k tomu se používá evolučně navržené deformovatelné zrcadlo
- vědci objevili děje (v oblasti atosekund), o kterých se nevědělo, že existují 

Syntetická biologie
-------------------
- funguje v opačném směru než klasická biologie
- snaží se postavit z elementárních komponent nové biologické systémy
- vezmou se bakterie/prvoci a pozmění se genetická informace
- snaha vytvořit z takových komponent výpočetní systém
- příkladem je genetický blikač
- z pohledu buňky je syntetické zařízení parazitem
- naše syntetické zařízení může mutovat

Mikrofluidový biočip
--------------------
- laboratoř na jednom čipu
- to, co dělají lidi pomocí pipet atd., by bylo mít dobré na jednom čipu
- čip, který umí přijmout kapku (nebo více kapiček látky)
- dokáže kapičkami pohybovat, mísit je, rozdělovat, ...
- pohyb kapky je řízen sadou elektrod