06. Elemi algoritmusok - halmazműveletek

Default book

A matematikai logikában tanuljuk és használjuk, de az informatikában kifejezetten gyakran használunk halmazokat - adathalmazokat. A programozás egyik alapvető feladata, hogy a különböző műveletek során legyünk képesek halmazokat felismerni és halmazműveleteket végezni,

Halmaz

Azonos tulajdonságokkal rendelkező "dolgok" csoportja.

A hamaz elemei

A halmazba tartozó dolgokat a halmaz elemeinek hívjuk

Magyarázat

Bármilyen tárgyból, fogalomból, élőlényből tudunk halmazokat létrehozni. Egy "dolog" egy időben lehet többféle halmaznak is tagja. az, hogy a világ egy "dolga" a halmaz része, vagy kívül van-e egy halmazon az határozza meg, hogy létezik-e az a tulajdonsága, ami a halmazt meghatározza.

A programozás során a "dolgok" lehetnek numerikus adatok, szöveges adatok stb...

Halmazok számossága

A halmazba tartozó elemek száma. Ha a "dolgok" száma véges, akkor a belőlük alkotott elemek száma is véges, de ha a dolgok száma végtelen, akkor bevezethetünk egy új fogalmat:

Megszámlálható számosságú végtelen = Ha a pozitív egész számokhoz hozzá tudom rendelni a halmaz elemeit egyesével és nem megszámlálható számosságú végtelen, ha ezt nem tudom megtenni.

Egy kis matematikai példa, de ne ijedjetek meg:

Az egész számok halmaza végtelen, de megszámlálható számosságú, mert:

1 =>  0
2 =>  1
3 => -1
4 =>  2
5 => -2
6 =>  3
7 => -3
stb...

A következő sorszámhoz hozzárendelem először a következő pozitív, majd a következő negatív számot...

Nem megszámlálható számosságú a valós számok halmaza, mert nem tudom az egész számokhoz hozzárendelni a valós számokat. Ezt be lehet bizonyítani, de ezt most nem teszem meg, mert nem matematikát tanítok most.

A halmazok elemei közötti reláció (viszony, kisebb-nagyobb, stb...)

Vannak olyan halmazok, amelyek elemei között egyértelmű sorrendet tudunk mondani. Meg tudjuk állapítani, hogy melyik kisebb, mint a másik. Ilyen például az egész számok halmaza, vagy az ABC betűi, vagy például a szövegek. Az elemek között vannak relációk.

Vannak olyan halmazok, amelyeknél ilyen relációt nem tudunk megmondani. Ilyen például a sík egész koordinátájú pontjai (x,y). A (0,0) pont esetén van legalább három másik olyan pont, amely az origótól ugyanolyan távolságra van, mint az adott pont. Pl. (1,0), (0,1), (-1,0), (0-1) Melyik legyen a kisebb és a nagyobb? Nincsen értelme meghatározni.

A halmazok a programozásban

A programozás során leginkább véges számosságú és relációs halmazokkal találkozunk, vagyis a fentiek alapján véges számú elemekből álló halmazok és a halmaz elemei között tudunk sorrendet felállítani.

Halmazok uniója (=egyesítése)

Ha van két halmazunk, akkor a két halmaz unióját azok az elemek alkotják, amelyek vagy egyik, vagy másik vagy mind a két halmazban benne vannak.

Jele: U vagyis

A halmaz és B halmaz uniója A U B

Halmazok metszete (=közös része )

Ha van két halmazunk, akkor a két halmaz metszetét azok az elemek alkotják, amelyek mind a két halmazban egyszerre benne vannak!

Jele: Å (Mivel a weben nincsen a metszetnek megfelelő karakter, ezért ide egy olyan jelet kell képzelni, amelynek csak a két lába van meg, vagy inkább egy fejre állított U betűt!)

A és B halmaz metszete => A Å B

Matematikai logika, logikai műveletek

A programozásban a amikor vannak különböző dolgaink olyan módon képezünk halmazokat, hogy a dolgok valamilyen tulajdonságát megnevezzük.

Példa 1.

Legyenek a dolgok például egész számok 1-től 1000-ig.

  • Lehet A halmaz azoknak a számoknak a halmaza, amelyek 500-nál kisebbek!
  • Legyen B halmaz azoknak a számoknak a halmaza, amelyek oszthatók 3-mal!

Mi lesz a két halmaz uniója?

Azok a számok, amelyek vagy az egyik szabálynak, vagy a másiknak vagy mind a kettőnek megfelelnek. Nyilvánvalóan 1-től 500-ig minden egész szám, majd 501-től 999-ig minden hárommal osztható szám

Ha például ki akarom íratni a két számhalmaz elemeit, akkor azt valahogyan így kell megtennem:

​Algoritmus leíró nyelven

Algoritmusleíró nyelven:
Ciklus i:=1-től 1000-ig
  Ha (i<500) vagy (i osztva maradékosan 3-mal = 0) akkor
    Ki: i
  Elágazás vége
Ciklus vége

​C# nyelven

for(int i=1; i<= 1000; i++){
  if(  (i < 500) || (i % 3 == 0 ) ){    // A % jel az egész számok osztásának maradékát jelenti
    Console.WriteLine(i);
  }
}

PHP nyelven

for( $i=1; $i<= 1000; $i++){
  if(  ($i < 500) || ($i % 3 == 0 ) ){  // A % jel az egész számok osztásának maradékát jelenti
    print $i ;
  }
}

Ismerjük fel, hogy a három nyelven nagyon hasonló kódot kapunk.

Mi lesz a két halmaz metszete?

Az eredmény 3, 6, 9, 12, 15, .... 498-lesz. Nyilván valóan a programok nagyon hasonlóak lesznek, csak éppen a kiíratás feltételeit kell kicsit másképpen meghatároznunk.

​Algoritmus leíró nyelven

Algoritmusleíró nyelven:
Ciklus i:=1-től 1000-ig
  Ha (i<500) és (i osztva maradékosan 3-mal = 0) akkor
    Ki: i
  Elágazás vége
Ciklus vége

​C# nyelven

for(int i=1; i<= 1000; i++){
  if(  (i < 500) && (i % 3 == 0 ) ){    // A % jel az egész számok osztásának maradékát jelenti
    Console.WriteLine(i);
  }
}

PHP nyelven

for( $i=1; $i<= 1000; $i++){
  if(  ($i < 500) && ($i % 3 == 0 ) ){  // A % jel az egész számok osztásának maradékát jelenti
    print $i ;
  }
}

Ismerjük fel, hogy a három nyelven itt is nagyon hasonló kódot kapunk.

Egy halmaz negáltja ( => azoknak az elemeknek a halmazba amelyek nem tartoznak az eredeti halmazba)

Legyen Mi lesz a két halmaz metszete?

Legyenek továbbra is a dolgok az 1-től 1000-ig terjedő egész számok. Az B halmaz legyen a 3-mal osztható számok halmaz. Mi lesz B negáltja?

Nyilván azok a számok, amelyek nem oszthatók lesznek, 3-mal. A programok hasonlóak

​Algoritmus leíró nyelven

Algoritmusleíró nyelven:
Ciklus i:=1-től 1000-ig
  Ha (i osztva maradékosan 3-mal <> 0) akkor
    Ki: i
  Elágazás vége
Ciklus vége

​C# nyelven

for(int i=1; i<= 1000; i++){
  if( (i % 3 != 0 ) ){    // A % jel az egész számok osztásának maradékát jelenti
    Console.WriteLine(i);
  }
}

PHP nyelven

for( $i=1; $i<= 1000; $i++){
  if(  $i % 3 != 0 ){  // A % jel az egész számok osztásának maradékát jelenti
    print $i ;
  }
}

Példa 2.

Van egy tömbünk (vagy listánk), tetszőleges szövegekkel (String) feltöltve.

Legyen A halmaz a 10 karakternél rövidebb szövegekkel feltöltött tömbelemek halmaza!

Legyen B halmaz a szóközöket is tartalmazó tömbelemek halmaza

Írassuk ki A U B elemeit!

Nyilván szükségünk lesz olyan függvényekre, amelyek tudnak valamit mondani a szövegek hosszáról és a bennük lévő karakterek milyenségéről, azaz a szövegekben lévő karakterekről adnak felvilágosítást,

Algoritmus leíró nyelven

szöveg T[N]                 // feltöltve különböző szövegekkel
Ciklus i:=1-től 1000-ig
  Ha (T[i] hossza < 100) vagy T[i] tartalmazza a szóközt) )  akkor
    Ki: i
  Elágazás vége
Ciklus vége

​Algoritmusleíró nyelven ezt csak így tudjuk leírni, hiszen nincsenek konkrét függvényeink, de a többi nyelven erre vannak eszközök:

C# nyelven

String[] T = new String[100];
for(int i=1; i<= T.Count(); i++){
  if( (T[i].Length < 10) || (T[i].Contains(" ") ) ){    // A string műveletek a hossz és a tartalmazás
    Console.WriteLine(i);
  }
}

PHP nyelven

T = Array("lkjlk", "klkjhkhkj", "htfhgf hgfhgfh hgf hgf hgf hgf ", "poiuzt", "fjitziuioi poipoi");
for( $i=1; $i<= count($T); $i++){
  if(  strlen($T[$i] < 10) || (strpos($T[$i], " ") !== FALSE ) ){  
    print $i ;
  }
}

Feladat:

Írassuk ki a két tömb metszetét.

Tags
#programozás