2015. május 11., hétfő

A brief history of modern Hungary

Hungary traces its history back to the hungarians, an alliance of semi-nomadic tribes from southern Russia and the Black Sea coast that arrived in the region in the ninth century. After centuries as a powerful medieval kingdom, Hungary was part of the Ottoman and then Habsburg empires from the 16th century onwards, emerging as an independent country again after World War I. The Hungarian language belongs to the Finno-Ugric family and is one of the handful of languages spoken within the European Union that are not of Indo-European origin. A landlocked country, Hungary is home to Lake Balaton, the largest in central Europe, and to a large number of spa towns and hot springs. At a glance International: Hungary joined NATO in 1999 and the EU in 2004. The EU has expressed concerns over what it sees as Hungary's failure to respect European democratic standards since 2010 It has especially rich traditions in folk and classical music and was the birthplace of numerous outstanding performers and composers, including Franz Liszt, Bela Bartok and Zoltan Kodaly.  Hungary became co-equal partner with Austria in a dual monarchy in the mid-19th century after an unsuccessful revolt against the Habsburgs in 1848. After a period of turmoil following World War I, an independent kingdom of Hungary was established under the authoritarian regency of Admiral Miklos Horthy.  The redrawing of European borders that took place after World War I left about five million ethnic Hungarians living in neighbouring countries. Their status remains a sensitive issue and has complicated Hungary's relations with its neighbours. Following World War II, in which Admiral Horthy had allied himself with Germany, Hungary fell under communist rule. An uprising in 1956 was crushed by Red Army forces, but Hungary did later become the first Eastern European country to gain some economic freedom. Hungary played an important part in accelerating the collapse of communism across Eastern Europe when it opened its border with Austria in 1989, allowing thousands of East Germans to escape to the West. Just a few months later the Berlin Wall was history. Hungary's post-communist economic transition was achieved relatively smoothly. Within four years of the collapse of communism nearly half of the country's economic enterprises had been transferred to the private sector, and by 1998 Hungary was attracting nearly half of all foreign direct investment in Central Europe. Ten years later, the picture looked rather less rosy. A high level of both private and state borrowing left the country particularly vulnerable to the credit crunch of 2008, and in October of that year the government was forced to appeal to the International Monetary Fund and the European Central Bank for massive loans in a bid to stave off economic collapse.




2015. május 9., szombat

Algoritmus leírása


Folyamatábra

Struktogram
Programozási feladattípusok (programozási tételek), a feladatmegoldás speciális kérdései. 
 A vizsgálni kívánt sorozatot megadhatjuk elemei felsorolásával vagy elemei kiszámítási módjával.
 
Feladattípusok

összegzés (a sorozat  elemeinek  összege,   szorzata, uniója stb.),
maximum-kiválasztás (a sorozat maximális, vagy   minimális értékű elemének kiválasztása),
megszámolás (adott tulajdonságú elemek száma a  sorozatban),
kiválogatás (sorozat  adott  tulajdonságú   elemeinek megadása),
Feladattípusok
kiválasztás (a vizsgált sorozat egy adott   tulajdonságú elemének megadása, ilyen elem  biztosan   szerepel a sorozatban),
eldöntés (van-e a vizsgált sorozatban  adott   tulajdonságú elem),
keresés (a vizsgált sorozat  egy adott   tulajdonságú elemének megadása, ilyen elem lehet, hogy nincs a sorozatban),
Feladattípusok
unió (két sorozatként ábrázolt halmaz egyesítése),
metszet (két sorozatként  ábrázolt halmaz közös  elemei),
összefuttatás (két rendezett sorozat egyesítése),
szétválogatás (egy sorozat kétféle tulajdonságú  elemeinek különválasztása),
Feladattípusok
rendezés (rendezetlen sorozat  elemeinek  átrendezése növekvő vagy csökkenő sorrendbe),
visszalépéses keresés (sorozatokból egy-egy elem meghatározása).


Összegzés: Ez a feladattípus egy sorozathoz egy értéket rendel.
A sorozat elemeinek összegét, szorzatát, unióját stb. kell előállítani.
A feladatok egy részénél az így kiszámított  értékkel esetleg még egyszerű műveletet kell végezni (pl.  osztani  az átlagszámításnál).
Az összegzés általános algoritmusa
Eljárás:
      S:=kezdőérték
      Ciklus I=1-től N-ig
         S:=S művelet A(I)
      Ciklus vége
   Eljárás vége.
Példa (egy 100 elemű tömb elemeinek összege)
Procedure osszegzes;
begin
  osszeg:=0;
      for i:=1 to 100 do
         osszeg:=osszeg+a[i];
end;
Maximum-kiválasztás
Ebben a feladatkörben adott egy N elemű sorozat.
A feladat ezen sorozat legnagyobb elemének meghatározása  (néha  csupán az értékére van szükség).
Hasonló feladat - csupán a < relációt kell >-ra cserélni - a minimum-kiválasztás.
A maximum-kiválasztás általános algoritmusa (1.)
Eljárás:
  MAXIMUM := A(1)
  SORSZAM := 1
Ciklus I=2-től N-ig
    Ha MAXIMUM < A(I) akkor   MAXIMUM := A(I)
   SORSZAM := I 
Ciklus vége
Eljárás vége.
Példa (Egy 100 elemű tömb legnagyobb elemének kiválasztása)
Procedure maximum;
begin
  max:=a[1];
  sorsz:=1;
  for i:=2 to 100 do
  begin
      if max < a[i] then
     begin
     max := a[i];
      sorsz:=i;
     end;
   end;
end;
A maximum-kiválasztás általános algoritmusa (2)
Eljárás:
   SORSZAM := 1
   Ciklus I=2-től N-ig
      Ha A(SORSZAM) < A(I) akkor SORSZAM := I
    Ciklus vége
    MAXIMUM  := A(SORSZAM)
Eljárás vége.
Példa (egy 100 elemű tömb legnagyobb elemének kiválasztása
Procedure maximum2;
begin
   sorsz:=1;
   for i:=2 to 100 do
      if a[sorsz] < a[i] then sorsz:=i;
    max:=a[sorsz];
end;

Megszámolás
A következő feladatok megoldása során egy  sorozathoz  egy számot rendelünk hozzá.
Rendelkezésünkre áll egy N elemű  sorozat és egy, a sorozat elemein értelmezett T tulajdonság.
Az a feladatunk, hogy a  T  tulajdonsággal  rendelkező  elemeket számoljuk meg.
Ügyeljünk arra, hogy az összegzés céljára szolgáló változó értékét kezdetben 0-ra kell állítani!
A megszámolás általános algoritmusa
Eljárás:
   DB:=0
   Ciklus I=1-től N-ig
      Ha A(I) T tulajdonságú akkor DB:=DB+1
   Ciklus vége
Eljárás vége.
Példa (Egy 100 elemű tömb elemei közül hány pozitív van)
Procedure pozitiv;
begin
   darab:=0;
   for i:=1 to 100 do
      if a[i] > 0 then darab:=darab+1;
end;

Kiválogatás
Ennél a feladattípusnál egy N elemű A sorozat összes T tulajdonsággal rendelkező elemét kell meghatározni.
Az eredmény egy B(M) sorozat lesz, ahol 0<=M<=N. 
M=0,  ha az A(N) sorozat egy eleme sem, M=N, ha az A(N) sorozat minden eleme T tulajdonságú.
A kiválogatás általános algoritmusa
Eljárás:
   M:=0
   Ciklus I=1-től N-ig
      Ha A(I) T tulajdonságú akkor M:=M+1 : B(M):=A(I)
   Ciklus vége
Eljárás vége.
Példa (egy száz elemű tömb pozitív elemeit gyűjtsük egy másik tömbbe)
Procedure pozitivtomb;
begin
   darab:=0;
   for i:=1 to 100 do
      if a[i] > 0 then
      begin
         darab:=darab+1;
         b[darab]:=a[i];
      end;
end;

Kiegészítés
A megoldásban gyakran - ha további  feldolgozásukra  nincs szükség - nem gyűjtjük ki az elemeket, hanem azonnal kiírjuk:
Eljárás:
  Ciklus I=1-től N-ig
     Ha A(I) T tulajdonságú akkor Ki: I,A(I)
   Ciklus vége
Eljárás vége.
Példa (egy 100 elemű tömb pozitív elemeinek kiíratása)
Procedure pozitivki;
begin
  for i:=1 to 100 do
     if a[i] > 0 then writeln(i,’ ., ‘,a[i]);
end;

Kiválasztás
Adott egy N elemű sorozat és egy, a sorozat elemein értelmezett T tulajdonság. Azt is tudjuk, hogy a  sorozatban  van legalább egy T tulajdonságú elem.
A feladat az első ilyen elem sorszámának meghatározása.
A kiválasztás algoritmusa
Eljárás:
   I:=1
   Ciklus amíg A(I) nem T tulajdonságú
      I:=I+1
   Ciklus vége
   SORSZAM:= I
Eljárás vége.
Példa (egy tömbben biztosan található első pozitív elem meghatározása)
Procedure elsopoz;
begin
   i:=1;
   while a[i] <= 0 do
   begin     
      i:=i+1;
   end;
   sorsz:=i;
end;
Eldöntés
Ez a feladattípus egy sorozathoz logikai értéket rendel.
A logikai érték "igaz"-at vesz fel,  ha  a  sorozatban  létezik adott (T) tulajdonságú elem, és "hamis"-at vesz fel, ha ilyen tulajdonságú elem nincs a sorozatban.
Az eldöntés általános algoritmusa
Eljárás:
   I:=1
   Ciklus amíg I<=N és A(I) nem T tulajdonságú
      I:=I+1
   Ciklus vége
   VAN:=(I<=N)
Eljárás vége.
Példa (egy 100 elemű tömbben van-e pozitív)
Procedure vanepoz;
begin
   i:=1;
   while (i <= 100) and (a[i] <= 0) do
   begin
      i:=i+1;
   end;
   van:=(i <= 100);
end;
Keresés
A keresés feladattípus egy sorozathoz egy elemet rendel.
A feladat lényege, hogy a sorozatban egy adott tulajdonságú (T) elemet kell meghatároznunk (magát az elemet vagy a sorozatbeli sorszámát szokás kérni).
Nem biztos, hogy a sorozatban van ilyen elem.
Keresés
A keresés hatékonyságát lényegesen  befolyásolhatja,  hogy rendezett vagy rendezetlen sorozatban keresünk: logaritmikus, illletve lineáris keresést használunk.
Amelyik feladatban lehet, használjuk ki a sorozat rendezettségét!

A lineáris keresés általános algoritmusa
Eljárás: lineáris keresés
   I:=1
   Ciklus amíg I<=N és A(I) nem T tulajdonságú
      I:=I+1
   Ciklus vége
   VAN:=(I<=N)
   Ha VAN akkor SORSZÁM:=I
Eljárás vége.
Példa (egy 100 elemű tömbben hányadik az első pozitív, ha van)
Procedure linearisker;
begin
   i:=1;
   while (i <= 100) and (a[i] <= 0) do
   begin
      i:=i+1;
   end;
   van:=(i<=100);
   if van then sorsz:=i;
end;

A logaritmikus keresés általános algoritmusa
Eljárás: logaritmikus keresés
      Be: X
      AlsoH = 1   FelsoH = n
      Ciklus vége
         K = (AH+FH)/2 egész része
         Ha X<A(K) akkor FH=K-1
         Ha X>A(K) akkor AH=K+1
      Ciklus amíg A(K)=X vagy AH>FH
      VAN:=(A(K)=X)
      Ha VAN akkor SORSZÁM:=K
   Eljárás vége.
Példa (egy 100 elemű rendezett tömbben keressük meg  egy tetszőleges elem sorszámát)
Procedure logaritmker;
begin
      readln(x);
      AlsoHatar:=1;
      FelsoHatar:=100;
      repeat
         Kozep:= (AlsoHatar+FelsoHatar) div 2;
         if x<a[Kozep] then FelsoHatar:=Kozep-1;
         if x>a[Kozep] then AlsoHatar:=Kozep+1;
      until (a[Kozep]=x) or AlsoHatar>FelsoHatar;
      van:=(a[Kozep]=x);
      if van then sorszam:=Kozep;
   end;

Alkalmazás
Gyakrabban találkozhatunk azonban olyan feladatokkal  a  gyakorlatban, ahol több programozási tétel együttes használatára van szükség.
Szerepel több olyan feladatsor, amelyben az adatok  azonosak, s velük kapcsolatban különböző kérdésekre  kell  választ adni.
Ezek jól használhatók önálló feladatmegoldásra.
Alkalmazás
A következő feladat megoldásánál a már  megismert  feladattípusok (összegzés, eldöntés, kiválasztás,  keresés,  megszámolás, maximumkiválasztás és kiválogatás) közül kell kiválasztani azokat, amelyekkel a kívánt eredmény elérhető.
Példa
Adott egy N elemű sorozat, valamint egy a sorozat  elemein értelmezett T tulajdonság.
Adjuk meg a sorozat minimális  értékű T tulajdonságú elemeit!
Adott N személyi számból álló sorozat [A(N)]. Adjuk meg az 1968-ban született legfiatalabb ember sorszámát  és  személyi számát!
Adjuk meg az összes ezen a napon született ember adatait is!
Alkalmazott tételek
Kiválogatás tétele: 1968-ban született emberek.
   B(I)= A(I) 2. és 3. számjegye.
Minimum-kiválasztás tétele: legkésőbbi  hónapban  és  napon született ember.
   C(I)= B(I) 4-7. számjegye.
Kiválogatás tétele: ugyanezen a napon született emberek.
Megoldás
Procedure szemelyiszam;
begin
      min:=1231;
      minsor:=0;
      for i=1-től n do
         if b[i]=68 then
                if c[i]<=min then
                begin
                    min:=c[i];
                    minsor:=i;
                end;
      if minsor>0 then
                for i=1 to n do
                if b[i]=68 and c[i]=min then writeln(a[i],’, ‘,i);
end;
Unió
Eddig olyan feladattípusokkal foglalkoztunk, ahol egy  sorozathoz egy értéket, vagy egy  sorozatot  rendeltünk  hozzá.
Ebben a részben viszont több sorozat adott, amelyből egy  sorozatot kell valamilyen szempont szerint előállítani.
A matematikából ismerjük két halmaz egyesítésének  (uniójának)  fogalmát.
Unió
A két halmaz egyesítéséből származó halmazba azok az  elemek tartoznak, amelyek legalább az egyikben szerepelnek.
Ebben, és a következő alfejezetben a  halmazt  speciálisan ábrázoljuk: az elemeit felsoroljuk egy sorozatban.
Ezt a sorrendet felhasználjuk a halmaz elemeinek bejárására.
Unió
Például, ha
      az "A" sorozat elemei: e, b, a, f, d, c és
      a  "B" sorozat elemei: j, f, b, h, d,
      akkor a két sorozat uniójába ("C") az  e, b, a, f, d, c, j, h
      elemek tartoznak.
Az unió általános algoritmusa
Eljárás:
      Ciklus I=1-től N-ig
         C(I):=A(I)
      Ciklus vége
      K:=N
      Ciklus J=1-től M-ig
         I:=1
         Ciklus, amíg I<=N és B(J)<>A(I)
            I:=I+1
         Ciklus vége
         Ha I>N akkor K:=K+1 : C(K):=B(J)
      Ciklus vége
   Eljárás vége.
Példa (egy 100 és egy 30 elemű sorozat uniója)
procedure unio;
begin     
   for i:=1 to 100 do c[i]:=a[i];
   k:=100;
   for j:=1 to 30 do
   begin
      i:=1;
      while (i<=100) and (b[j]<>a[i]) do i:=i+1;
      if i>n then
      begin
          k:=k+1;
         c[k]:=b[j];
       end;
    end;
end;
Metszet
A metszetképzés fogalmával találkoztunk már  a  matematika órán a halmazműveletek tanulása során.
Két halmaz metszetébe azok az  elemek  tartoznak,  amelyek mindkettőben szerepelnek.
   Például, ha
      az "A" halmaz elemei: e, b, a, f, d, c és
      a  "B" halmaz elemei: a, j, f, b, h, d,
      akkor a két halmaz metszetébe ("C") a  b, f, d  elemek tartoznak.
A metszet általános algoritmusa
Eljárás:
      K:=0
      Ciklus I=1-től N-ig
         J:=1
         Ciklus amíg J<=M és A(I)<>B(J)
            J:=J+1
         Ciklus vége
         Ha J<=M akkor K:=K+1 : C(K):=A(I)
      Ciklus vége
   Eljárás vége.
Példa (egy 100 és egy 30 elemű halmaz közös elemei)
Procedure metszet;
begin    
k:=0;
      for i:=1 to 100 do
      begin
         j:=1;
         while (j<=30) and (a[i]<>b[j]) do j:=j+1;
         if j<=30 then
         begin 
            k:=k+1;  c[k]:=a[i];
         end;
      end;
   end;
Összefuttatás
Az alapelve megegyezik az unióképzéssel, de feltételezzük, hogy a két sorozat rendezett,  és  azt  szeretnénk,  hogy  az egyesítés során keletkezett sorozat is rendezett legyen.
   Például, ha
      az A sorozat elemei: A, B, C, D, E, F és
      a B sorozat elemei:  B, D, F, H, J,
      akkor a két sorozat összefuttatásával keletkezett sorozatba az A, B, C, D, E, F, H, J elemek tartoznak.
Az összefuttatás általános algoritmusa
Eljárás:
      I:=1 : J:=1 : K:=0
      Ciklus amíg I<=N és J<=M
         K:=K+1
         Elágazás
            A(I)<B(J) esetén C(K):=A(I) : I:=I+1
            A(I)=B(J) esetén C(K):=A(I) : I:=I+1 : J:=J+1
            A(I)>B(J) esetén C(K):=B(J) : J:=J+1
         Elágazás vége
      Ciklus vége
   Eljárás vége.
Példa (egy 100 és egy 30 elemű rendezett sorozat összefuttatása)
Procedure osszefuttatas;
begin
      i:=1;j:=1;k:=0;
      while (i<=100) and (j<=m) do
      begin
         k:=k+1;
         if a[i]<b[j] then begin c[k]:=a[i]; i:=i+1; end else
         if a[i]=b[j] then begin c[k]:=a[i]; i:=i+1;j:=j+1; end
         else begin c[k]:=b[j];j:=j+1 end;
      end;
end;

Szétválogatás
Ebben a részben egy sorozat elemeit választjuk külön  vagy egy sorozaton belül két részre, vagy két különböző  sorozatba aszerint, hogy egy adott T tulajdonsággal  rendelkeznek-e  az elemek, vagy nem.
Például, ha az A sorozat elemei 1, 2, 3, 4, 5, 6, 7, 8, 9, és a T tulajdonság:  a  számok  párossága,  akkor  a  sorozat elemeinek szétválogatásával a 2, 4, 6, 8, és az 1, 3, 5, 7, 9 sorozatok keletkeznek.
A szétválogatás általános algoritmusa
Eljárás:
      J:=0 : K:=0
      Ciklus I=1-től N-ig
         Ha A(I) T tulajdonságú akkor  J:=J+1 : B(J):=A(I)  különben K:=K+1 : C(K):=A(I)
      Ciklus vége
   Eljárás vége.
Példa (100 szám szétválogatása paritás alapján)
Procedure szetvalogatas;
begin
      j:=0;k:=0;
      for i:=1 to 100 do
         if a[i] mod 2=0 then begin j:=j+1;b[j]:=a[i]; end
         else begin k:=k+1; c[k]:=a[i]; end;
      end;
end;

Rendezések
Közvetlen beszúrással
Közvetlen kiválasztással
Buborék-rendezés (közvetlen csere)
Keverő rendezés
megjegyzés: Ennél sokkal több rendezési algoritmus létezik!
Közvetlen beszúrás
Minden lépésben a második elemtől egyesével kiemeljük a csökkenő sorozat szerinti első elemet, és beszúrjuk a megfelelő helyre
Ábra
Algoritmus
Procedure kozvetlenbeszuras;
begin
   for i:=2 to n do
   begin
       elem:=a[i];
       j:=i-1;
       while (j>0) and (elem<a[j]) do
       begin
          a[j+1]:=a[j];
          j:=j-1;
       end;
       a[j+1]:=elem;
    end;
end;
Közvetlen kiválasztás
A sorozat soron következő legkisebb elemének kiválasztása, majd beszúrása a megfelelő helyre.
Ábra
Algoritmus
Procedure kozvetlenkivalasztas;
begin
   for i:=1 to n-1 do
   begin
      k:=i; elem:=a[i];
      for j:=i+1 to n do
          if a[j]<elem then
          begin
             k:=j; elem:=a[j];
          end;
      a[k]:=a[i]; a[i]:=elem;
   end;
end;
Közvetlen csere (buborék)
Az alkalmas elempárok összehasonlítása és felcserélése során jutunk az összes elem rendezéséhez.
Ábra
Algoritmus
Procedure buborek;
begin
   for i:=2 to n do
   begin
      for j:=n downto i do
         if a[j-1]>a[j] then
         begin
            elem:=a[j-1];
            a[j-1]:=a[j];
            a[j]:=elem;
         end;
   end;
end;
Keverő rendezés
Az előző módszer elég rossz hatásfokú, ha kevés rossz helyen tartózkodó elem van, mert akkor is elvégzi az összes összehasonlítást.
A keverő rendezés ezen úgy javít, hogy váltogatja az összehasonlító menetek irányát.
Ábra
Algoritmus / 1
Procedure kevero;
begin
   l:=2; r:=n; k:=n;
   repeat
      for j:=r downto l do
         if a[j-1]>a[j] then
         begin
             elem:=a[j-1];
             a[j-1]:=a[j];
             a[j]:=elem;
             k:=j;
         end;
      l:=k+1;
Algoritmus / 2
for j:=1 to r do
         if a[j-1]>a[j] then
         begin
             elem:=a[j-1];
             a[j-1]:=a[j];
             a[j]:=elem;
             k:=j;
         end;
       r:=k-1;
   until l>r ;
end;

Visszalépéses keresés (backtrack)
A visszalépéses keresés ( backtrack )  a  problémamegoldás igen széles területén alkalmazható algoritmus,  amelynek  lényege a feladat megoldásának megközelítése rendszeres próbálgatással.
Néha ez a legjobb megoldás!
Visszalépéses keresés (backtrack)
Adott N sorozat, amelyek rendre M(1),  M(2),...M(N)  elemszámúak.
Ki kell választani mindegyikből egy-egy elemet  úgy, hogy az egyes  sorozatokból  való  választások másokat  befolyásolnak.
Ez egy bonyolult keresési  feladat,  amelyben  egy adott tulajdonsággal rendelkező szám N-est kell megadni  úgy, hogy ne kelljen az összes lehetőséget végignézni.
Visszalépéses keresés (backtrack)
Először megpróbálunk az első sorozatból  kiválasztani  egy elemet, ezután a következőből, s ezt  addig  csináljuk,  amíg választás lehetséges.
X(I) jelölje az I. sorozatból kiválasztott elem sorszámát!
Ha még nem  választottuk, akkor értéke 0 lesz.
Ha nincs jó választás, akkor visszalépünk az előző  sorozathoz, s megpróbálunk abból egy másik  elemet  választani.
Visszalépéses keresés (backtrack)
Visszalépésnél természetesen törölni kell a választást  abból a sorozatból, amelyikből visszalépünk.
Az  eljárás  akkor  ér véget, ha minden sorozatból sikerült választani, vagy pedig a visszalépések sokasága után már az első sorozatból sem  lehet újabb elemet választani (ekkor a feladatnak nincs megoldása).
A backtrack általános algoritmusa
Eljárás:
      I:=1 : X(I):=0
      Ciklus amíg I>=1 és I<=N
         Ha VAN JO ESET(I) akkor  I:=I+1
                         különben X(I):=0 : I:=I-1
      Ciklus vége
      VAN:=(I>N)
   Eljárás vége.

  
A backtrack általános algoritmusa
VAN JO ESET(I):
      Ciklus
         X(I):=X(I)+1
      amíg X(I)<=M(I) és ROSSZ ESET( I,X(I) )
      Ciklus vége
      VAN JÓ ESET:=(X(I)<=M(I))
   Eljárás vége.
A backtrack általános algoritmusa
ROSSZ ESET( I,X(I) ):
      J:=1
      Ciklus amíg J<I és (J,X(J)) nem zárja ki (I,X(I))-t
         J:=J+1
      Ciklus vége
      ROSSZ ESET:=(J<I)
   Eljárás vége.