Algoritmi Polinomiali de Generare a Submulțimilor Discrete Finite

-Introducere-

Motivul alegerii acestei lucrări este de a înţelege mai bine cum un algoritm matematic de generare poate fi implementat în cadrul unui limbaj de programare.

Algoritmul propriu-zis este înglobat în cadrul unui program întreg ce este format din anumite biblioteci pentru diferite tipuri de proceduri sau funcţii prestabilite, constante sau variabile de date şi numeroase modalităti de prelucrare a datelor de intrare. Acestea pot fi primite de la tastatura sau direct dintr-un anumit fişier.

La final se poate observa soluţia generată în urma rulării respectivului algoritm în compilator, în cazul de faţă acesta fiind Borland C++ 3.1.

Această lucrare este intitulată “Algoritmi polinomiali de generare a submulţimilor discrete finite” şi face parte din “GENERAREA DE SUBMULŢIMI”. Este structurată în zece subcapitole, iar fiecare dintre acestea se axează pe o anumită modalitate de generare a elementelor unei mulţimi. Pentru reprezentarea unei mulţimi se foloseşte de obicei un vector cu n componente în care se introduc elementele acesteia.

Submulţimile generate vor fi de următoarele două tipuri:

- submulţimi în care este importantă ordinea în care apar elementele;

- submulţimi în care nu contează ordinea în care apar elementele.

Toate generările ce sunt prezentate în această lucrare au un caracter iterativ, fiecare element fiind dedus din anteriorul său

La generarea elementelor produsului cartezian din cadrul aplicaţiei elementele vor fi generate succesiv într-un vector V cu m componente.

În următorul subcapitol sunt prezentate 4 metode de generare a tuturor submulţimilor unei mulţimi cu n elemente.

În cadrul generării combinărilor se va studia problema generării tuturor celor submulţimi ale lui A, cu proprietatea că oricare două submulţimi diferă prin natura elementelor.

Subcapitolul 5 prezintă mai multe metode de a genera cele n! permutări de grad n. Orice permutare de grad n se reprezintă printr-un vector p cu n componente.

La generarea aranjamentelor se vor descrie două metode de generare a tuturor grupărilor de m elemente distincte din mulţimea [n], două grupări diferind fie prin natura, fie prin ordinea elementelor.

Generarea combinărilor cu repetiţie conţine trei metode de generare a m-combinărilor cu repetiţie.

În subcapitolul următor se prezintă determinarea tuturor modalităţilor de scriere a unui numar n sub forma :

n = + + +

unde numerele naturale nenule , , se numesc părţi ale lui n.

La final se generează toate partiţiile unei mulţimi, unde o partiţie reprezintă o descompunere a mulţimii de forma :

A = ∪ ∪ ∪

unde cele k submulţimi , , (numite clase) sunt nevide şi două câte două disjuncte.

Aplicaţia propriu-zisă este compusă din două programe rulate în Borland C++.

Prima problemă generează elementele unui produs cartezian. Elementele produsului cartezian vor fi generate succesiv într-un vector V cu m componente.

În cadrul celui de-al doilea program se implementează un algoritm de generare a tuturor grupărilor de m elemente distincte din mulţimea [n], două grupări diferind fie prin natura lor, fie prin ordinea elementelor. Astfel se generează aranjamente de n elemente luate câte m, cu repetiţie.

ALGORITMI POLINOMIALI DE GENERARE A SUBMULŢIMILOR DISCRETE FINITE

I.1. Reprezentarea mulţimilor şi generarea iterativă a elementelor

Fie A = { , , } o mulţime oarecare cu n elemente. Pentru reprezentarea ei se foloseşte de obicei un vector cu n componente în care se introduc elementele mulţimii. Este important de notat că o astfel de asociere mulţime → vector stabileşte implicit o ordine a elementelor mulţimii, corespunzătoare ordinii în care apar elementele în vector.

Fie B o submulţime a lui A. Există mai multe modalitaţi de reprezentare a submulţimilor, cele mai folosite fiind următoarele:

(i) - printr-un vector cu n componente, unde elementele submulţimii sunt plasate la începutul vectorului, precizându-se în plus numărul lor sau introducând pe restul poziţiilor din vector o valoare care nu aparţine mulţimii A = [n] = {1,2, ,n}.

(i’) - printr-un vector cu n componente, construit analog cu cel din reprezentarea (i) cu deosebirea că elementele submulţimii sunt plasate la sfarşitul vectorului.

(ii) - prin vectorul caracteristic al submulţimii, adică acel vector c {0,1 definit de:

c(i) = (1)

În această lucrare vom presupune totdeauna că A = [n] = {1, ,n} deoarece între o orice mulţime A={ , , } şi [n] există o bijecţie, de exemplu cea dată de corespondenţa

Submulţimile care vor fi generate în această lucrare vor fi de urmatoarele două tipuri:

- submulţimi în care este importantă ordinea în care apar elementele.

- submulţimi în care nu conteaza ordinea în care apar elementele.

Pentru submulţimile de al doilea tip, dacă folosim pentru ele una dintre reprezentările (i) sau (i’), vom conveni că ordinea în care apar elementele să fie cea crescătoare; în acest mod vom evita generarea de mai multe ori a aceleaşi submulţimi.

Toate generările ce vor fi prezentate vor avea un caracter iterativ, fiecare element fiind dedus din anteriorul său. Algoritmul general de construire a unui nou element apare în procedura GEN. El foloseşte pe langă un vector V de dimensiune n ( în care vor fi generate succesiv submulţimile ) şi un indicator de generare IG. La apelarea procedurii, IG are fie valoarea 0 ( dacă este vorba de prima apelare, deci trebuie făcuta o iniţializare ), fie valoarea 1 ( dacă trebuie construit succesorul vectorului V ). La terminarea fiecărei execuţii a procedurii, IG are fie valoarea 1 ( dacă a fost generat un nou vector V ), fie valoarea 0 ( dacă au fost generaţi toţi vectorii V ceruţi de problema concretă ).