VIK Wiki - Felhasználó közreműködései [hu]

Elosztott rendszerek

2013-06-06T09:59:41Z

Vbalu987:

{{Tantárgy
| név = Elosztott Rendszerek
| tárgykód = VIAUM124
| szak = InfoMsc - AlkInfo
| kredit = 4
| félév = tavasz
| kereszt = nincs, és nem is kell
| tanszék = AUT
| jelenlét = nincs
| minmunka = ZH+Vizsga
| labor = ősszel
| kiszh = 0
| nagyzh = 1
| hf = 0
| vizsga = Van
| levlista = https://lists.sch.bme.hu/wws/info/alkinfo-msc
| tad = https://www.vik.bme.hu/kepzes/targyak/VIAUM124/
| tárgyhonlap = https://www.aut.bme.hu/Course/VIAUM124
}}

=== Tipikus ZH/Vizsga kérdések ===
* elosztott rendszerek előnyei a központosított rendszer előnyeivel
* GIOP protokoll (General Inter ORB Protocol) üzenet típusai, üzenet tartalma
* COM objektum típusok

=== ZH / Vizsga kidolgozások ===
* [[ElosztottRendszerekVizsga20050526]]

==2013.05.30 Vizsga==
# elosztott rendszerek vs centralizált különbségei
# COM interfészek felsorolása (5db), részletezd
# GIOP
# integrációs megoldásokból 4 db
# EJB tranzakciós attributumok, mire jók, sorold fel, részletezd
# .NET remoting fogalmai, működése általánosságban, hogyan lehet objektumokat létrehozni
# WCF: mi és mire jó a binding, objektumok szálkezelése

==2006.04.24. minta zh==

# Kifejteni miért fontos az elosztott rendszer (centralizált/elosztott rendszer összehasonlítása).
** centralizált rendszer előnyei
*** könnyen adminisztrálható
*** nagy megbízhatóság redundáns hardverrel biztosítható
*** szakértőket biztosít a szállító
** elosztott rendszer előnyei
*** rugalmas
*** horizontálisan is skálázható
*** nagy teljesítményű
*** dinamikus feladatelosztással megbízhatóvá tehető
*** jó ár/teljesítmény
*** a rendszer bizonságkritikus részei jól szeparálhatók
# Komponens alapú fejlesztés előnyei és hátrányai.
** komponensek külön fejleszthetők
** interfész és implementáció külön van választva
** interfész is bővíthető (örökléssel vagy aggregációval)
** elég csak a bináris kódot kiadni a megrendelőnek
** konténer biztosítja a middleware-t szabványos felületen keresztül
** deklaratív leíró file, adminsztrációs felület biztosított hozzá
** komponens technológiák egymás között nem átjárhatók
# Milyen típusú servereket ismer a COM-ban?
** in-process: komponens a kliens processzében fut. Gyors, de csak szinkron hívás van és egy hibás komponens magával ránthatja a klienst is. Pl. VB
** in-process handler: felüldefiniálható a standard marshalling. Pl. .NET Application Domains
** local server (out-process): a szerver (tipikusan .dll) külön processzben fut, ha elszáll, a kliens csak timeoutot kap. Stabil, de lassabb, mint az in-process
** remote server: a szerver távoli gépen is futhat, a hozzáférés transzparens. Ez jelenti a legnagyobb overheadet. Pl. DCOM
# Middleware szolgáltatások (10 db), ezek közül néhányat kifejteni.
** névfeloldás, security, tranzakciókezelés, object pooling, perzisztencia, load balancing, életciklus management, szálkezelés, event/notify, messaging
# GIOP protokoll.
** GIOP Fejléc: magic string, verzió, byte sorrend, üzenet típus (1-7), üzenet méret
## RequestMessage (K->S) — kérés: GIOP header, Message header (objektum azonosító, metódus, szolgáltatások, aszinkron kérés azonosító), Body (metódus paraméterek)
## ReplyMessage (S->K) — válasz a kérésre: GIOP header, Reply header (válasz azonosító (mire válasz?), státusz kód), Body (visszatérési érték, hibainfó)
## CancelRequest (K->S) — aszinkron kérés megszakítása: GIOP header, kérés ID
## LocateRequest (K->S) — objektum megpingelése: GIOP header, objektum ID
## LocateReply (S->K) — ping válasz
## CloseConnection (S->K) — kapcsolat befejezése
## MessageError (K<->S) — hiba
# .NET framework fő részei (esetleg volt szó .NET remotingról, de erre pontosan nem emlékszem). <ul><table border="1" cellspacing="1" cellpadding="2"><tr><td> Subsystems: <table style="width:100%; text-align:center;" border="1"><tr><td> Web services </td><td> WinForms </td><td> ADO.NET </td><td> XML </td><td> ... </td></tr></table> </td></tr><tr><td> Base Class Library: ~5000 osztály </td></tr><tr><td> CLR: <table border="1" cellpadding="2" style="width:90%; text-align:center;"><tr><td> '''Garbage collector''' </td><td> Type checker </td><td> Debugging </td><td> Threading </td><td>Code checker</td></tr><tr><td> InterOp </td><td> COM </td><td> Remoting </td><td> '''JIT compiler''' </td><td> </td></tr></table> </td></tr><tr><td> ClassLoader </td></tr></table>Bővebb infó angolul [http://www.c-sharpcorner.com/UploadFile/chandrakantpp/UnderstandingFrameworkatglance11292005013851AM/UnderstandingFrameworkatglance.aspx?ArticleID=78f8b8b0-c67e-4061-81af-e30779f915ab itt]</ul>
# Web service, milyen célra használható?
** integráció különböző platformok között
** külső cég által fejlesztett komponensek felhasználása
** üzleti folyamatok tervezése
** fejlesztési paradigma
# J2EE architektúra ábrával [http://kepfeltoltes.hu/130322/j2ee_appserver_www.kepfeltoltes.hu_.png] Forrás: http://uml2006.infojarda.hu/EJB_1.pdf

==(2013.06.06) Elosztott Rendszerek vizsgakérdések==

# GIOP ismertetése (15 pont)
# 10 db Middleware szolgáltatás, ebből 5-öt részletesen kifejteni (15 pont)
# COM és CORBA technológiák különbségei (10 db különbség) (20 pont)
# Objektum relációs leképezés fogalmai, hogyan oldható ez meg JPA-val. (15 pont)
# EJB-ben időzítés megoldása+szekvencia diagram (15 pont)
# Milyen problémát old meg az XML web szolgáltatások?, mi a megoldás kulcsa?. Mik a hozzá kapcsoló szabványok? Mik a WS-* szabványok?, sorolj fel hármat. (20 pont)

Feladatok: -- Ekler Péter - 2006.04.25. 
Megoldások: -- [[PallosPeter|Peti]] - 2006.04.25.

[[Category:InfoMsc]]
[[Category:AlkInfo]]
[[Category:InfoMsc Tavasz]]

Elosztott rendszerek

2013-06-06T09:58:50Z

Vbalu987:

{{Tantárgy
| név = Elosztott Rendszerek
| tárgykód = VIAUM124
| szak = InfoMsc - AlkInfo
| kredit = 4
| félév = tavasz
| kereszt = nincs, és nem is kell
| tanszék = AUT
| jelenlét = nincs
| minmunka = ZH+Vizsga
| labor = ősszel
| kiszh = 0
| nagyzh = 1
| hf = 0
| vizsga = Van
| levlista = https://lists.sch.bme.hu/wws/info/alkinfo-msc
| tad = https://www.vik.bme.hu/kepzes/targyak/VIAUM124/
| tárgyhonlap = https://www.aut.bme.hu/Course/VIAUM124
}}

=== Tipikus ZH/Vizsga kérdések ===
* elosztott rendszerek előnyei a központosított rendszer előnyeivel
* GIOP protokoll (General Inter ORB Protocol) üzenet típusai, üzenet tartalma
* COM objektum típusok

=== ZH / Vizsga kidolgozások ===
* [[ElosztottRendszerekVizsga20050526]]

==2013.05.30 Vizsga==
# elosztott rendszerek vs centralizált különbségei
# COM interfészek felsorolása (5db), részletezd
# GIOP
# integrációs megoldásokból 4 db
# EJB tranzakciós attributumok, mire jók, sorold fel, részletezd
# .NET remoting fogalmai, működése általánosságban, hogyan lehet objektumokat létrehozni
# WCF: mi és mire jó a binding, objektumok szálkezelése

==2006.04.24. minta zh==

# Kifejteni miért fontos az elosztott rendszer (centralizált/elosztott rendszer összehasonlítása).
** centralizált rendszer előnyei
*** könnyen adminisztrálható
*** nagy megbízhatóság redundáns hardverrel biztosítható
*** szakértőket biztosít a szállító
** elosztott rendszer előnyei
*** rugalmas
*** horizontálisan is skálázható
*** nagy teljesítményű
*** dinamikus feladatelosztással megbízhatóvá tehető
*** jó ár/teljesítmény
*** a rendszer bizonságkritikus részei jól szeparálhatók
# Komponens alapú fejlesztés előnyei és hátrányai.
** komponensek külön fejleszthetők
** interfész és implementáció külön van választva
** interfész is bővíthető (örökléssel vagy aggregációval)
** elég csak a bináris kódot kiadni a megrendelőnek
** konténer biztosítja a middleware-t szabványos felületen keresztül
** deklaratív leíró file, adminsztrációs felület biztosított hozzá
** komponens technológiák egymás között nem átjárhatók
# Milyen típusú servereket ismer a COM-ban?
** in-process: komponens a kliens processzében fut. Gyors, de csak szinkron hívás van és egy hibás komponens magával ránthatja a klienst is. Pl. VB
** in-process handler: felüldefiniálható a standard marshalling. Pl. .NET Application Domains
** local server (out-process): a szerver (tipikusan .dll) külön processzben fut, ha elszáll, a kliens csak timeoutot kap. Stabil, de lassabb, mint az in-process
** remote server: a szerver távoli gépen is futhat, a hozzáférés transzparens. Ez jelenti a legnagyobb overheadet. Pl. DCOM
# Middleware szolgáltatások (10 db), ezek közül néhányat kifejteni.
** névfeloldás, security, tranzakciókezelés, object pooling, perzisztencia, load balancing, életciklus management, szálkezelés, event/notify, messaging
# GIOP protokoll.
** GIOP Fejléc: magic string, verzió, byte sorrend, üzenet típus (1-7), üzenet méret
## RequestMessage (K->S) — kérés: GIOP header, Message header (objektum azonosító, metódus, szolgáltatások, aszinkron kérés azonosító), Body (metódus paraméterek)
## ReplyMessage (S->K) — válasz a kérésre: GIOP header, Reply header (válasz azonosító (mire válasz?), státusz kód), Body (visszatérési érték, hibainfó)
## CancelRequest (K->S) — aszinkron kérés megszakítása: GIOP header, kérés ID
## LocateRequest (K->S) — objektum megpingelése: GIOP header, objektum ID
## LocateReply (S->K) — ping válasz
## CloseConnection (S->K) — kapcsolat befejezése
## MessageError (K<->S) — hiba
# .NET framework fő részei (esetleg volt szó .NET remotingról, de erre pontosan nem emlékszem). <ul><table border="1" cellspacing="1" cellpadding="2"><tr><td> Subsystems: <table style="width:100%; text-align:center;" border="1"><tr><td> Web services </td><td> WinForms </td><td> ADO.NET </td><td> XML </td><td> ... </td></tr></table> </td></tr><tr><td> Base Class Library: ~5000 osztály </td></tr><tr><td> CLR: <table border="1" cellpadding="2" style="width:90%; text-align:center;"><tr><td> '''Garbage collector''' </td><td> Type checker </td><td> Debugging </td><td> Threading </td><td>Code checker</td></tr><tr><td> InterOp </td><td> COM </td><td> Remoting </td><td> '''JIT compiler''' </td><td> </td></tr></table> </td></tr><tr><td> ClassLoader </td></tr></table>Bővebb infó angolul [http://www.c-sharpcorner.com/UploadFile/chandrakantpp/UnderstandingFrameworkatglance11292005013851AM/UnderstandingFrameworkatglance.aspx?ArticleID=78f8b8b0-c67e-4061-81af-e30779f915ab itt]</ul>
# Web service, milyen célra használható?
** integráció különböző platformok között
** külső cég által fejlesztett komponensek felhasználása
** üzleti folyamatok tervezése
** fejlesztési paradigma
# J2EE architektúra ábrával [http://kepfeltoltes.hu/130322/j2ee_appserver_www.kepfeltoltes.hu_.png] Forrás: http://uml2006.infojarda.hu/EJB_1.pdf

==(2013.06.06) Elosztott Rendszerek vizsgakérdések==

1) GIOP ismertetése (15 pont)
2) 10 db Middleware szolgáltatás, ebből 5-öt részletesen kifejteni (15 pont)
3) COM és CORBA technológiák különbségei (10 db különbség) (20 pont)
4) Objektum relációs leképezés fogalmai, hogyan oldható ez meg JPA-val. (15 pont)
5) EJB-ben időzítés megoldása+szekvencia diagram (15 pont)
6) Milyen problémát old meg az XML web szolgáltatások?, mi a megoldás kulcsa?. Mik a hozzá kapcsoló szabványok? Mik a WS-* szabványok?, sorolj fel hármat. (20 pont)

Feladatok: -- Ekler Péter - 2006.04.25. 
Megoldások: -- [[PallosPeter|Peti]] - 2006.04.25.

[[Category:InfoMsc]]
[[Category:AlkInfo]]
[[Category:InfoMsc Tavasz]]

Rendszeroptimalizálás, 17. tétel

2013-04-24T15:16:13Z

Vbalu987: /* Közelítő algoritmus a részösszeg optimalizálási problémára */

{{GlobalTemplate|Infoszak|RopiTetel17}}

==!! Polinomiális approximációs séma a =RÉSZÖSSZEG= problémára.==

__TOC__

===[http://info.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=17258 Szkennelt leírás és bizonyítás az infositeon]===

===Polinomiális approximációs séma===

*Def.*: egy probléma polinomiális approximációs sémával közelíthető, ha ∀ε>0-ra van rá (1+ε)-approximáció.
Ez nem mindig elég, mert ha a közelítő algoritmus lépésszáma 21/εn4, még mindig exponenciálisan hosszú ideig fut. 
*Def.*: egy probléma teljesen polinomiális approximációs sémával közelíthető, ha ∀ε>0-ra van rá (1+ε)-approximáció, ami 1/ε-ban is polinomiális. 
*Pl.*: a metrikus utazó ügynök problémára nincs P approximációs séma, de az euklideszi utazó ügynök problémára van teljesen P approximációs séma.

===Részösszeg probléma===

Adott _A_ = {a1, a2, ..., an} és _t_. 
Kérdés: létezik-e B&sube;A úgy, hogy Σbi = _t_? 
Speciális eset: partíció probléma, amikor _t_ = Σai/2, még ez is NP-teljes.

===Részösszeg optimalizálási probléma===

Adott _A_ = {a1, a2, ..., an} és _t_. 
Keressük B&sube;A-t úgy, hogy Σbi maximális és Σbi ≤ _t_ legyen. 
A feladat NP nehéz, mert a részösszeg probléma visszavezethető rá. Bizonyítás: ha találunk olyan a _B_ halmazt, amire Σbi = _t_, akkor igen a válasz a részösszeg problémára, különben nem. 
A feladat nem NP-beli, mert nem eldöntési probléma, tehát nem is NP-teljes.

===Közelítő algoritmus a részösszeg optimalizálási problémára===

*Tétel*: a probléma teljesen polinomiális sémával közelíthető.

A bizonyítás egy konkrét algoritmus lesz:
<ol>
<li>Pontos megoldást adó algoritmus:

Tegyük fel, hogy a1 ≤ a2 ≤ ... ≤ an.
Definiálunk két halmazsorozatot:
* L0 = {0}
* Li' = {l+ai | l<big>∈</big>Li}
* Li+1 = Li ∪ Li'
Röviden: Li+1 = Li ∪ (Li+ai+1)

Például:
* a1=3, a2=5, a3=7
* L0 = {0}
* L0' = {3}, L1 = {0,3}
* L1' = {5,8}, L2 = {0,3,5,8}
* L2' = {7,10,12,15}, L3 = {0,3,5,7,8,10,12,15}

Az optimális részletösszeg max{l|l<big>∈</big>Ln <big>&and;</big> l≤t} lesz.

<li>Polinomiális közelítő algoritmus:

Egyrészt vegyük észre, hogy az Li' halmazokból nincs szükségünk a t-nél nagyobb elemekre. Képezzük a halmazokat a következő módon: Li' = (Li+ai) ∩ [0..t].

Def.: δ-val ritkítás
<pre>L növekvő sorrendbe rendezett halmaz.
foreach (l'''∈L''') {
''m'' az ''l''-et megelőző, halmazban hagyott elem, vagy ha nincs ilyen, 0.
if (''l''lt;m(1+''δ'')) ''l''-et kidobjuk.
}</pre>

A ritkítás után bármely két szomszédos elem hányadosa legalább 1+δ. A ritkított halmaz mérete felülről becsülhető: |Lritkított ≤ log1+δt+2.

<li> *Tétel*: ha az algoritmus során a halmazok t-nél nagyobb elemeit minden lépésben levágjuk és az eredményt δ=ε/2n-vel ritkítjuk, (1+ε)-approximációt kapunk a problémára, és a lépésszám n-ben, log t-ben és 1/ε-ban is polinomiális lesz.

*Biz.*: az algoritmus (1+ε)-approximációs. %P%

*Biz.*: az algoritmus lépésszáma mindhárom mennyiség szerint polinomiális.

<math> \forall i \: |L_i| \le \log_{1+\frac{\epsilon}{2n}}t+2 = \frac{\ln t}{\ln (1+\frac{\epsilon}{2n})}+2 = O(\log t) </math>

Másrészt az x≥-1-re érvényes x/(1+x) ≤ ln(1+x) összefüggést kihasználva x=ε/2n helyettesítéssel:

<math>
\forall i \: |L_i| \le
\frac{\ln t}{\ln (1+\frac{\epsilon}{2n})}+2 \le
\frac{(1+\epsilon/2n) \ln t}{\epsilon/2n}+2 =
\frac{(2n+\epsilon) \ln t}{\epsilon}+2
</math>

Az algoritmus során n db lista összefésülést kell végezni, aminek a komplexitása O(∑|Li||) = O(n||Li||). A fenti becslések alapján látszik, hogy O(n||Li) n-ben négyzetes, log(t)-ben lineáris, tehát mindkettőben polinomiális. Az 1/ε szerinti becslést órán lenyeltük. %P%
</ol>

-- [[PallosPeter|Peti]] - 2006.12.18.

[[Category:Infoszak]]

Szerkesztő:Vbalu987

2013-04-13T15:13:09Z

Vbalu987: Új oldal, tartalma: „Helló!”

Helló!