2016-01-25

Chomského normální forma bezkontextových gramatik - referát

Do předmětu Teoretická informatika oboru Informační a komunikační technologie na VŠB jsem měl za úkol zpracovat krátký referát na téma Chomského normální forma bezkontextových gramatik. Nejde o žádnou vědeckou práci, ale i tak je mi líto nechat tento text ležet v šuplíku bez užitku někomu dalšímu. Celý text ke stažení.

Chomského normální forma je tvar či specifický způsob zápisu formální gramatiky. Při převodu bezkontextové gramatiky do Chomského normální formy se po odstranění pravidel typu A → ε provádí krok, který odstraňuje pravidla typu X → Y (neterminál se přepisuje na neterminál). (Pak dostaneme jen pravidla typu A → α, kde α je terminál nebo |α| ≥ 2, přičemž generovaný jazyk se nezměnil.)
Noan Chomsky - filosof a matematik

Zadání

Na vhodném příkladu ilustrujte algoritmus odstraňující ona pravidla X → Y a ukažte jeho korektnost.

Definice

Je přímo uvedena výše, jinými slovy: Bezkontextová gramatika je v Chomského normální formě, jestliže každé její pravidlo je tvaru X → Y Z nebo X → a, kde „X, Y, Z“ označují neterminální symboly a „a“ terminální symbol. Tedy na levé straně je jeden neterminál, na pravé terminál nebo maximálně 2 další neterminály. Kde A, B a C jsou neterminály, α je terminál, S je startovní neterminál a ε je prázdný řetězec, přičemž B ani C nemohou být startovacím neterminálem.

Tvar CHNF

  • A → BC nebo
  • A → α nebo
  • S → ε (je povoleno, pokud gramatika generuje prázdný řetězec a zároveň se S nevyskytuje na pravé straně žádného pravidla)

Algoritmus

  1. odstranění ε pravidel;
    • nahrazení těmi terminály a neterminály, které by se tam mohly objevit a přidat je za stávající pravidla. Je třeba to provést důkladně a zahrnou všechny možné vzniknuvší kombinace!
  2. odstranění jednoduchých pravidel;
    • samostatné neterminály v jednom znaku nahradit jejich přepisem
  3. odstranění terminálů mimo A → α;
    • zavést substituci novým neterminálem za všechny terminály, které jsou součástí neterminálů, kromě osamocených terminálů nebo skupiny terminálů.
  4. pohlcování neterminálních symbolů.
    • Všechny neterminály, které jsou delší než 2 znaky se musí zkrátit zavedením dalších substitucí. Ponechá se první znak a zbývající se substituují dalším neterminálem.
  5. Výsledkem je sada pravidel ve tvaru X → Y Z, přičemž pro zjednodušení mohou být zapsána i za sebou se znakem „nebo |“.

Příklady


Použití

Bezkontextové gramatiky
G = ({VÝROK, PŘÍVLASTEK, PODMĚT, PŘÍSUDEK}, {malý, velký, pes, kocour, běží, leží, spí}, VÝROK, Pdále)

Význam

Pro pochopení formy je třeba mít představu o tom, čeho forma to je. S bezkontextovými jazyky a gramatikami se hojně setkáváme při syntaktické analýze textu, třeba zdrojových kódů programovacích jazyků. Slovo „bezkontextová“ v názvu gramatiky znamená, že na levé straně každého pravidla stojí jeden neterminál bez sousedních symbolů (tedy není v „kontextu“).

Všechny bezkontextové jazyky lze generovat bezkontextovými gramatikami v jistém speciálním tvaru. Derivační stromy, příslušné k těmto gramatikám, pak mají jednotný tvar. Tato skutečnost usnadňuje cestu k závěrům v některých úvahách o bezkontextových jazycích. Příkladem je Chomského nebo Greibachova normalní forma.

Převedení zápisu gramatiky do CHNF vede k vytvoření jednoznačného derivačního stromu. Gramatika G je jednoznačná, jestliže každé slovo z L(G) má právě jedno levé odvození (právě jeden derivační strom), jinak je víceznačná a jako takovou ji není možné vždy transformovat na ekvivalentní jednoznačnou gramatiku.

Hlavní výhodou v Chomského normální formě je že, každé odvození řetězce s n písmeny má přesně 2n - 1 kroků, je tedy možné určit, zda je řetězec v jazyku všech derivací ve známém počtu operací.


Derivační strom

Derivační strom je v reprezentant syntaktické struktury slovního řetězce podle formální gramatiky. V derivačním stromě jsou vnitřní uzly označeny jako neterminály gramatiky, zatímco koncové uzly jsou označeny jako terminály. Derivační stromy mohou být využity pro generování nebo analýzu vět v přirozeném jazyce, stejně tak jako během zpracování počítačových jazyků.

Vytváření derivačních stromů ze specificky formátované gramatiky vede na jednoznačné derivační stromy, což je velký výhoda pro porovnávání bezkontextových gramatik mezi sebou.

Důkaz

Nejprve věta 12.2.2 o odstranitelnosti ε přechodů: Ke každé bezkontextové gramatice G lze sestrojit ekvivalentní nevypouštějící gramatiku G‘ tž. L(G‘) = L(G) − {ε}. Důkaz ve skriptech str. 62.


Co se tím říká? Nedochází k porušení správnosti gramatiky, neboť důkaz odstranění ε přechodů se provádí výše, to je první zásah do konstrukce gramatiky: ve stručnosti se pouze přepisují symboly na nová umístění, ale jde jen komplikaci zápisu. Dalším porušením integrity by mohlo být přepisování pravidel neterminály, ale lze jistě souhlasit, že zavedením substituce nedochází ke změně významu původního výrazu a právě tato úprava se v průběhu převodu do CHNF odehrává. Intuitivně lze vyčíst, že v rámci algoritmu nedochází k modifikaci samotné gramatiky.

Jednoduše si lze představit důkaz jako problém grafu o 2 uzlech nad sebou. Pokud horní a spodní uzel rozdělím a vložím mězi ně uzel další, pak se zcela logicky nemění význam grafu, pouze je v něm více uzlů. Přesně stejný případ vytváří gramatika v Chomského normální formě, protože nemění význam a pouze dochází k přidání pravidel se specifickými vlastnostmi.

Zdroje


Autor Žádné komentáře :
Štítky:

2016-01-16

Protínají se rovnoběžky v nekonečnu? Aplikace na trojúhelník

V hospodě jsme se dostali k zajímavému problému. Tím byla definice trojúhelníku za pomocí dvou rovnoběžek tak, jak je to znázorněno na náčrtku.

Autor věty říká, že jde o trojúhelník, protože se rovnoběžky protínají v nekonečnu.


Všichni intuitivně cítíme, že tato úvaha není správná, nicméně není úplně mylná, pojďme ale matematicky ukázat v čem je problém. Sázka byla o půl litr točené Kofoly a to už stojí za pár hodin pročítání matematických skript. 


Moje prvotní myšlenka byla, že to ztroskotá na vágním zadání, přičemž jsem byl ihned spolusedícími upozorněn, že nemám používat divná slova, kterým nerozumí. (což je samo o sobě docela složitý problém).

Vycházejme z toho, že se celý příklad odehrává "za normálních podmínek". Elementární definice rovnoběžek vychází z jejich podstaty v Eukleidově prostoru (to je ten "náš normální", pak je i spousta dalších).

Axiom rovnoběžnosti z pátého Eukleidova postulátu: Každým bodem B, který neleží na přímce p, lze vést právě jednu přímku p′, která neprotíná p. 

 Intuitivně z toho vyplývá, že rovnoběžky se nikde neprotínají. Jak vidíte Eukleides neznal pojem nekonečno, jeho geometrické axiomy jsou staré cca 2000 let, protože nekonečno jako pojem se podařilo zkrotit teprve odhadem 300 let zpátky. Přesto se občas vyskytuje tvrzení, že se rovnoběžky protínají v nekonečnu. (respektive se mi nepodařilo najít žádný věděcký zdroj informací, který by tuto myšlenku podpořil)


Nicméně připusťme pro zbytek článku, že se rovnoběžky skutečně protínají v nekonečnu, na řešení to nebude mít vliv. Tím by došlo k naplnění představy o tom, že vznikne trojúhelník.


Každopádně je hledání řešení přes vyvracení axiomů příliš složitý akademicko-matematický problém. Dostanete se tím do elementárních termínů geometrie a do jiných než euklidovských prostorů.

Co mě v zápětí napadlo (při připuštění protnutí), je zaměřit se na druhý pojem a tím je trojúhelník:
Základní vlastností trojúhelníka v euklidovském prostoru je jeho určení třemi body, neležícími v jedné přímce a skutečnost, že součet velikostí jeho vnitřních úhlů je roven 180°.
Pokud tedy dvě přímky svírají svírají ůhly 90° ke své kolmici, pak jejich součtem vyjde přesně číslo 180. Protnutím polopřímek v nekonečnu by vznikl sice třetí bod neležící na jedné přímce, ale také ještě nekonečně malý úhel, jehož přičtením ke 180° by byl porušen součet vnitřních úhlů a výsledný útvar by nebyl trojúhelníkem. 


 Tím jsem našel spor v původním tvrzení a Kofola by měla připadnout mi. À propos neuvažujte o nekonečnu jako o číslu, tedy ani jako o bodu, který je možné geometricky využít. 

Jak jsem naznačil, tak pravdivost celá úlohy byla postavena na připuštění jevu o protnutí a dost nepřesném zadání. Při dalším rozboru totiž dojdeme ke zjištění, že v neeukleidovské geometrii se součet úhlů v trojúhelníku liší od 180°. 

Pro řešení by pomohlo přenesení náčrtku do eliptické  geometrie. Zde ovšem vzniká problém s tím, že v tomto prostoru neexistují rovnoběžky, protože se dvě přímky z principu vždy protnou. Příbuzným problémem je Saccheriho čtyřúhelník.

Nicméně to nebylo v zadání explicitně (pardon výslovně) uvedeno a tak to nelze předpokládat. Navíc obrázek je zakreslen značením platným v Eukleidově prostoru. Zkrátka Kofola je moje.


Jisté zjednodušení pro pochopení problematiky vede obecně k možnosti napadnutelnosti textu pro jeho nedokonalost. V matematice je totiž nutné být přesný a používat specifikované termíny definovaným způsobem (vidíte, jak to dopadá), což je také důvod, proč jsou vysoce postavení matematici a) tak nesrozumitelní b) tak příšerně nudní pro nezaujaté posluchače.


Tímto článkem jsem chtěl nějak pochopitelně objasnit uvedený hospodský problém. Respektive tvrzení, kterým jeho autor vyvedl z míry učitelku matematiky na střední škole. Předpokládám, že je v něm spousta více či méně podstatných nepřesností (resp. že původní tvrzení je příliš velká blbost). Budu rád, pokud mi o nich dáte vědět v komentářích níže. 


Pokud máte i nadále pocit, že matematika je děsně nudná záležitost, tak vám doporučuji si přečíst třeba problém Rusellova paradoxu, paradox lháře (či nějaký jiný).  I když to úplně nesouvisí s problematikou geometrických prostorů.

Pokud navíc patříte k těm, co tvrdí, že se dá všechno snadno a rychle vyřešit (ať už jde o politiku, sociální otázky nebo cokoliv jiného), pak snadno přelouskáte i nějaké dosud nevyřešené matematické problémy.

Zdroje:

Tento příspěvek jsem také vyvěsil na své sociální sítě, kde se mi k němu ozvali mí kamarádi, kteří se matematikou zabývají na profesionálnější úrovni než já. Dovolil jsem si svůj původní článek podle jejich poznatků lehce modifikovat, ale zároveň chci předat jejich myšlenky dalším čtenářům:

Kamil Keprt (OSU): Tvrzení, že když přičteš nekonečně malý úhel ke 180 dostaneš více a proto to není trojúhelník se mi zdá velmi pochybné. Spíše bych řekl že v EP prostě žádné body v nekonečnu dělat nemůžeš, takže vše s čím skončíš jsou 2 body a ne 3... Do celé té Euklidovské geometrie bych nekonečno neplantal, ta na to prostě není stavěná. Jak se tam zaplantá nekonečno, tak jsou z toho reálné projektivní prostory a různé nepředstavitelné "hnusy". Za mě: Jestli dvě rovnoběžky určují trojúhelník? V EP ne, v jiných geometriích ano... Každopádně zajímavá úvaha...


Podíval bych se na to z topologického hlediska (tomu bych mohl rozumět více než geometrii), tak Eukleidovská rovina jak ji známe ze střední má svoji metriku (můžeš určit vzdálenosti libovolných dvou bodů), metrika indukuje topologii (ta říká co je otevřená množina a co ne), která je naprosto schodná s přirozenou topologií (otevřené množiny jsou prostě řečeno ty s čárkovaným okrajem, když je kreslíš) a R^2 je triviální 2 dimenzionální varieta nad R, a teď k té myšlence po té spoustě chytře vypadajících keců: 

V každém bodě je okolí, které je "homeomorfní" (spojitě můžeš přecházet tam a zpět) s tou vaší A4 papírem řekněme - a na tom papíře můžeš určit souřadnicový systém a "blabla" a můžeš si tam nakreslit různé body a měřit mezi nimi vzdálenosti atd... ten svůj papír zároveň můžeš "změnou měřítka" zvětšovat jak je libo, ale nikdy nenakreslíš bod nebo cokoliv na přesný okraj toho papíru, ten okraj je "čárkovaný", tomu papíru nepatří, můžeš se k němu jen libovolně blízko přiblížit, ale pořád to nebude na tom okraji, na tom okraji by se nacházelo to "nekonečno", ale v této struktuře to prostě nejde...

Dominik Koutný (UPOL): V euklidovské, obecně afinní, rovině se dvě rovnoběžky z definice neprotnou. Jde o to, že se dá nadefinovat něco jako "přímka v nekonečnu", a pak se rovnoběžky protnou, ale už pracuješ s projekcemi a projektivními prostory.  Proto se asi říká, že se rovnoběžky v nekonečnu protnou.

K tomu, jak říkáš že by to už nebyl trojúhelník, tam bych viděl problém v tom, že považuješ nekonečno za pevný bod, pak by součet skutečně nebyl 180°, ale jiný. Nekonečno je ale abstraktní skruktura, takže bys přičítal nulu, jelikož platí, že pro tvůj pevně daný úhel bys vždycky dokázal najít menší, takže by ti to šlo k nule. Existují však transformace, které ti nekonečno přitáhnou do bodu a pak je s ním možné pracovat jako s bodem, ale není to součástí EP. Ve fyzice jsou takové transformace běžné, např. funkce Arkus tangens ti přitáhne nekonečno do PI/2, ale to je jenom nástin, jak to může fungovat. Všechno je taky otázka definice. Říkám jenom, co jsem pochytil sem tam na hodinách, můžu se mýlit.
motikona smile.

Zdá se, že celý problém není vůbec triviální. Jako vždy pomůže, pokud se už na začátku pokusíte problém řešit intuitivně a až poté si jej začít ověřovat pomocí pouček.

Jestli chcete v tématu pokračovat, následující článek renomovaného autora jakoby v nakousnutém tématu pokračoval mnohem dále...
Autor 8 komentářů :
Štítky:

2016-01-05

Kruskalův algoritmus - implementace a rozbor

Ve škole jsem měl v rámci zbrusu nového předmětu Matematika pro zpracování znalostí vytvořit implementaci Kruskalova algoritmu včetně dokumentace a hlavně teoretického rozboru. Protože nerad ukládám práci do šuplíku, rád se podělím s případnými dalšími řešiteli o své myšlenky.


Předně měla být kritériem hodnocení délka běhu programu. Cílem mělo být udělat program efektivní. resp. nedělat ho zbytečně neefektivní. Jenže zadávající vyučující nepředpokládal, že se do toho studenti pustí ve vyšších programovacích jazycích (C# / Java), kde třeba na prohledání slovníku stačí konstantní čas O(1), a to už je rozdíl proti seznamu s lineárním časem O(n). Stejně šlo všechno snažení mimo hlavní směr neboť nakonec se testování omezilo na minimálním vzorek dat... Nyní ale k algoritmu samotnému.


Zadání

V ohodnocených grafech určete všechny nejlevnější kostry grafu pomocí Kruskalova algoritmu. 

Motivace

Proč hledat minimální kostru v grafových úlohách? Zde uvádím pouze několik zjevných příkladů použití.

Návrh elektrické sítě

Máme k dispozici seznam odběrných míst a chceme je propojit tak, abychom využili co nejmenší množství drátů. Tímto problémem se zabýval mimo jiné český vědec Otakar Borůvka, který ve svém článku „O jistém problému minimálním“ z roku 1926 publikoval algoritmus, který se zabýval návrhem efektivní elektrické sítě na Moravě. Později jeho práci využil také americký matematik Joseph Kruskal.

Smyčky v počítačových sítích

Spanning Tree Protocol (v překladu protokol kostry grafu) je v informatice název pro síťový protokol, který v ethernetových sítích odstraňuje smyčky na druhé vrstvě ISO/OSI modelu. Výpočet provádí aktivní prvek (switch), který odpojí redundantní spoje, které v síti způsobují nezastavitelné množení zpráv určených všem příjemcům (broadcast). 

Teorie

Kruskalův algoritmus pracuje na principu spojování hran s nejmenším ohodnocením, dokud tyto hrany nespojí všechny vrcholy v grafu. Takto vzniklý podgraf nazýváme kostrou grafu. Význam “koster” spočívá v jejich minimalitě vzhledem k počtu hran, přičemž je zachována souvislost grafu.

 Matematický zápis: Je dán souvislý ohodnocený graf G s nezáporným ohodnocením hran w: E(G) → R0+. Problém minimální kostry znamená najít takovou kostru T v grafu G, která má nejmenší možnou váhu. MST (z anglického “Minimum spanning tree“) je tedy číslo, které udává váhu kostry s nejmenší možnou vahou.

Předpoklady

  • Graf je souvislý (projekt umí najít i více koster v nespojitém grafu)
  • Graf je neorientovaný (případnou orientaci zahazuje)
  • Graf je vážený (hrany mají kladné ohodnocení)

Pseudokód

Kruskal(vrcholy V, hrany H, ceny c)
{
MST := ∅; //kostra je prázdná
for každý vrchol v ∈ V
          do MAKE-SET(v); //vytvoří samostatný podstrom pro každý vrchol
for každou hranu h(x, y) ∈ H v pořadí neklesajících ceny c
          if FIND-SET(x) != FIND-SET(y) //pokud jsou podstromy různé
               then MST := MST ∪ h(x, y);  //přidej hranu do kostry
               UNION(x, y); //spoj odpovídající podstromy
return MST
}

Vizualizace hledání

Pro doplnění představy o způsobu přidávání hran do kostry.

Časová složitost Kruskalova algoritmu 

Nejprve je třeba uvážit čas nutný k setřízení hran podle velikosti ceny / váhy od největší po nejmenší. Je obecně známé, že u řazení, které je založeno na porovnávání dvojic klíčů (což je univerzální metoda použitelná pro libovolná data a která je v projektu implementována), je minimální časová složitost O(H log V).

Kruskalův algoritmus najde minimální kostru v čase:
O(H log V + H · Tfind (V) + V · Tunion(V))
kde Tfind(V) a Tunion(V) jsou časové složitosti operací Find a Union na grafech s V vrcholy a H hranami, které patří do struktury Union-Find, kterou jsem do projektu implementoval. H log V + H je již zmíněná časová náročnost řazení hran.
  • Operaci find (zjistí, zda vrcholy v1 a v2 leží v téže komponentě) implementuji ve svém projektu jako cyklus nad hranami, složitost je tedy O(H).
  • Operaci union (přidá hranu v1 a v2, čili dvě komponenty spojí do jedné) implementuji v projektu jako průchod cyklem nad vrcholy v menší komponentě před spojením dvou listů. Náročnost operace je opět O(Vmenšíkomponenty) kterou můžeme zjednodušeně vyjádřit jako O(V).
Pro shrnutí tedy:
O(H log V + H + V)
V souladu s pravidly asymptotické složitosti můžeme dále zanedbat aditivní konstanty, čímž dostaneme výslednou složitost:
O(H log V)
Tato složitost je ekvivalentní se složitosti O(H log H), protože pokud V je počet vrcholů a H počet hran, tak H = V2 v nejhorším případě. Při matematické úpravě H log V2 = 2 H log V to při  zjednodušení odpovídá O(H log V).

Třída algoritmu

Hladové algoritmy fungují na principu, že se prostřednictvím lokálního optima snažíme dospět ke globálnímu optimu neboli také, pokud se musím rozhodnout, pak vždy beru aktuálně nejlepší možnost bez ohledu na budoucnost.

Lze dokázat, že hladový algoritmus najde minimální kostru grafu. V případě Kruskalova algoritmu se hladovosti dobře využívá, neboť hrany jsou před začátkem seřazeny podle ceny od nejlevnější, po přidání hrany se zjišťuje, zda-li nevznikla minimální kostra a tak nevložením horších hran nedojde k ovlivnění výsledku.

Obecným příkladem je úloha „dobře se najíst“, což je žádoucí globální optimum. Chceme-li se dobře najíst a máme před sebou stůl plný potravin, začneme pravděpodobně tím, na co máme největší chuť (lokální optimum). Až nám tato potravina dojde, budeme pokračovat druhou nejchutnější věcí, a tak dále. Na konci algoritmu budeme dobře najedení a spokojení.

Obecně hladové algoritmy nemusí poskytovat správné výsledky: Je třeba si uvědomit je fakt, že je nutné je provést nad všemi vyhodnocovanými objekty. Mohlo by totiž dojít ke stavu v následujícím příkladu hledání maxima, kdy volbou lokálního maxima přehlédneme maximum globální.

Je zřejmé, že pro obrovská množství dat není možné provést v konečném čase výpočet nad každým vrcholem a proto se v praxi využívá “hladovosti” nad velkými daty pouze jako jednoduchého heuristického nástroje. Pro komplexní hledání globálních extrémů je možné využít například algoritmus SOMA (Self-Organizing Migrating Algorithm) či některý z dalších biologicky inspirovaných algoritmů probíraných ve stejnojmenném kurzu.

Implementace

Je provedena v objektovém prostředí jazyka C# včetně všech vhodných nativních knihoven. Projekt je pro snadné ovládání doplněn o grafické uživatelské rozhraní v češtině. Použito bylo prostředí .NET framework verze 3.5, která je výchozí verzí v operačním systému Windows 7.

 Zde se hodí poznamenat, že realizované řešení nekopíruje přesně dané zadání. Vlivem chyby paralaxu došlo k podstatnému zjednodušení, takže namísto:
V ohodnocených grafech určete všechny nejlevnější kostry grafu pomocí Kruskalova algoritmu. 
se mi podařilo najít jen
V ohodnocených grafech určete první nejlevnější kostry grafů pomocí Kruskalova algoritmu. 
Jak opravit projekt tak, aby splňoval původní zadání jsem doplnil do prezentace. Nejúčinnější bude pravděpodobně použití systémového volání fork na vytvoření "kopie" procesu se svou vlastní pamětí, která dokáže vytvářet variace na původní graf za podmínek existence grafu.

Download

Projekt se zdrojovými kódy ve Visual Studiu 2015 je možné si stáhnout z tohoto odkazu včetně testovacích dat. Prezentaci zde. CC-BY 2015 Ivo Kostecký

Struktura vstupních dat

Vrchol 1 hrany 1 (int); Vrchol 2 hrany 1 (int); nezáporná metrika hrany (decimal)
Vzhledem k vágnímu zadání potencionálních vstupů není v projektu implementována vyšší než nutná ochrana proti nevyžádánemu vstupu.


Upozornění pro výstupní data

Výstup kruskalova algoritmu, tedy kostry grafů jsou poskytovány opět ve formátu CSV kompatibilním se vstupem programu. Tato struktura neumožňuje odlišení jednotlivých koster a proto jsou kostry / komponenty řazeny za sebou BEZ viditelného oddělení. Pokud potřebujete kopomenty rozlišit, využijte prvky uživatelského rozhraní, kde jsou náležitě dokumentovány výsledky.

Výsledky

Na grafu o 7000 vrcholech a 18 373 348 hranách

Otevírám z: <<cesta>>\7000.csv
Uložím do: <<cesta>>\vysledky.csv
Nyní prosím vyčkejte na výsledky úlohy.
--------------------------------------------------------
Uloha dokoncena! Čas běhu 760,0453156s.
--------------------------------------------------------
Graf má 1 koster.
Kostra "0" má vrcholů "7000" a hran "6999".
--------------------------------------------------------
Celkový počet vrcholů: 7000.
Celkový počet hran: 6999.

Na grafu o 1500 vrcholech a 843 051 hranách

Otevírám z: <<cesta>>\1500.csv
Uložím do: <<cesta>>\vysledky.csv
Nyní prosím vyčkejte na výsledky úlohy.
--------------------------------------------------------
Uloha dokoncena! Čas běhu 8,9579028s.
--------------------------------------------------------
Graf má 1 koster.
Kostra "0" má vrcholů "1500" a hran "1499".
--------------------------------------------------------
Celkový počet vrcholů: 1500.
Celkový počet hran: 1499.

Na grafu o 6301 vrcholech a 20 777 hranách

Otevírám z: <<cesta>>\OrientOhodG2.csv
Uložím do: <<cesta>> \vysledky.csv
--------------------------------------------------------
Uloha dokoncena! Čas běhu 0,0890054s.
--------------------------------------------------------
Graf má 2 koster.
Kostra "0" má vrcholů "6299" a hran "6298".
Kostra "1" má vrcholů "2" a hran "1".
--------------------------------------------------------
Celkový počet vrcholů: 6301.
Celkový počet hran: 6299.

Zdroje informací


 Pro další doplnění nebo opravu můžete použít komentáře pod tímto textem.

Autor Žádné komentáře :
Štítky: ,

2016-01-04

Jaký je rozdíl mezi SDN, NFV a síťovou virtualizací?

Pokud se zajímáte o novinky v oblastech počítačových sítí, pak jste nutně museli narazil na "nové" pojmy, jejichž definice jsou dle mého trošku těžší v počátcích pochopit. Protože se touto oblastí zabývám v rámci svého magisterského studia, dovoluji si přijít s vysvětlením vlastními slovy.

IT je oblast, kde každá sebevětší kravinka má svou vlastní, obvykle třípísmennou, zkratku. Takže jejich rozepsání je následující:
  • SDN = Software-defined networking 
  • NFV = Network functions virtualization
  • NV = network virtualization
Cílem všech těchto pojmů je přejít ze stávajícího síťařského modelu, kdy každé dedikované zařízení má svou krabičku a v ní svou konfiguraci. Největší současná nevýhoda je totiž to, že se v provozní konfiguraci po čase reálného používání nikdo nevyzná. 

 Hledat, jestli se spojení nesestaví, protože datagramy zahodí na vstupu firewall nebo uvnitř pravidlo nepovolující tento typ služby nebo na výstupu zákaz předat packety s konkrétní adresou na toto rozhraní a to vše v obou směrech a na všech zařízením po cestě je zkrátka moc velký hlavolam. Proto chcete mít centrální konfiguraci odkud je přehled nad celou sítí.

Navíc v době, kdy počet připojených zařízení roste vysokým tempem je klasický systém neudržitelný. Měl jsem možnost slyšet zkušenosti se správou univerzitní sítě VŠB a jednou severskou společností a jsem rád, že jsem za to nebyl zodpovědný...

 Nový model "krabiček" ideálně bázi PC (i když to není nutnou podmínkou pro SDN controller) se sdílenou konfigurací, respektive s jedním místem odkud se nastavení provádí. Více o smyslu toho všeho v závěru příspěvku.


Software defined networking 

Je to takový přístup k architektuře, který se snaží využít abstrakce k správě síťové funkcionality. Logické topologie sítě se dosahuje pomocí programování virtuálních komponent. Principem je oddělení rozhodovací části (control plane) síťového prvku od té vykonávající směrovací či přepínací činnost (data plane).


Pro doplnění: Rozdíl mezi control (rovina řízení) a data plane (rovina obsluhy) je podobný problému městské hromadné dopravy. Control plane ve městě určí a dále sleduje, které linky povedou odkud kam a jaká na nich pojedou vozidla. Data plane jsou šoféři, kteří převážejí cestující.


Reálně už tento stav v každém zařízení dlouho existuje, roviny jsou odděleny. SDN ale říká, že control plane se vytvoří vně na jednom místě centrálně a nikoliv distribuovaně v každém zařízení. Data plane nahradit nelze, protože to je ta část, která vykonává skutečnou práci na základě pokynů "shora".

Trochu to může připomínat řízení firmy, máte svou manufakturu v jednom státě, vyrábíte několik užitečných věcí. Najednou celou firmu koupí větší globální firma, vyhodí vaše současné vedení a nařídí, že máte dělat jenom jeden produkt. Vy máte pocit, že "ti idioti" tomu vůbec nerozumí a přitom z vnějšího pohledu jde najednou celý business lépe.

Tato prezentace přirovnává sítě k architektuře staveb a vůbec SDN pěkně shrnuje.

Pojem SDN by ale neměl zasahovat do oblastí, které byly softwarem dlouho před objevem buzzwordu SDN v roce 2009. Objevují se totiž různé manipulace, které tvrdí, že každý software v síťovém prvku do SDN patří, že směrovací protokoly jako OSPF nebo BGP jsou SDN, že firewall a load ballancer jsou SDN atd. Některé firmy tyto myšlenky tak rozvinuly, že samotný "vynálezce" Martin Casado už sám vlastně neví...

Network functions virtualization

Podstatou virtualizovaných funkcí sítě je nebýt závislý na specifickém hardwaru, protože ten je drahý, obtížně nahraditelný a pomalu se instaluje. V současném světě cloudových řešeních chcete mít vše spustitelné na x86 procesorech tedy na normálních počítačích resp. serverech, které se dnes umí automatizovat / orchestrovat.

Proto ve své síti chcete opustit fyzická zařízení jako load balancery, firewally, IDSky, IPSky, VPN koncentrátory, atd. a všechno mít jako virtuální stroje v datacentru. S NFV přišli telekomunikační poskytovatelé služeb u kterých existovalo velké množství různých proprietárních hardwarových boxů. Z dnešního enterprise pohledu je mít vše spíše softwarové běžné.

SDN vs NFV

NFV je vhodným doplňkem SDN, ale není jeho nezbytnou součástí a naopak. Jinými slovy, jsou si vzájemně prospěšné. Zatímco SDN se zabývá chováním a logickou topologií sítě, NFV přenáší funkcionalitu z fyzických zařízení na virtualizované servery. To vše v zájmu přehlednější správy, nižších pořizovacích i operačních nákladů a hlavně pro méně komplikované změny za pochodu a vytváření nových prostředí a služeb.


Network virtualization

Jestliže SDN se zabývalo jednotnou konfigurací hardwaru síťových zařízení, pak síťová virtualizace kompletně převádí tato fyzická zařízení do softwaru. 



Podle společnosti VMware je síťová virtualizace nosič pro síťové vrstvy L2 - L7 ISO-OSI modelu. Má to tedy být věrný obraz síťových prvků a linek stejně, jako je virtuální server ve vztahu se serverem fyzickým. Osobně cítím toto pojetí jako nejintuitivnější možné uchopení stavu věcí.

Nicméně na každé z úrovní je možné do opět virtualizovat nebo spouštět transportní technologie, které mají v názvu "virtuální" čímž vniká docela dobrý zmatek v pojmech i výsledku. Příkladem budiž VLANy, VXLANy, VRF, VPN, MPLS... Virtualizace celých zařízení umožňuje opouštět tyto technologie a nahrazovat je celými virtuálními zařízeními, což je většinou jejich cíl. Záleží tedy na architektovi, jak danou problematiku zpracuje. Nevím jak vám, ale mě to silně připomíná film Počátek...

Shrnutí

Celá problematika je poněkud rozsáhlá a určitě ji neobsáhne jeden článek, globálním cílem budoucích sítí, všech zmíněných technologií a konceptů je dohnat vývoj, který se udál ve virtualizaci serverové / aplikační. Lze toho dosáhnout mimojiné také díky tomu, že stále roste výkon počítačů a není potřeba se již výhradně spoléhat na hardwarově specifická zařízení, protože jejich vyšší výkon je možné nahradit kvantitou x86 počítačů.


Výborná je tato prezentace ze které pochází i množství obrázků, které jste zde viděli.

Pokud máte dotazy či připomínky, jsou vám k dipozici komentáře pod tímto textem.

 Další materiály

Autor Žádné komentáře :
Štítky: ,