Modeling arbitraty sets of combintorial objects and their sequential and parallel generation

• Autorzy: Kapralski A.

Warianty tytułu

PL

Modelowanie arbitralnych zbiorów obiektów kombinatorycznych oraz ich sekwencyjna i równoległa generacja

• Języki publikacji: EN

Abstrakty

EN

We give the representations of different subsets of compositions, decompositions, number and set partitions by means of choice functions of indexed families. The structure of the symmetric sets of choice functions is represented by investigated tables D related to Pascal's triangle and to the Stirling's numbers. Unranking and ranking representation models concerning sets of choice functions are developed. We study transformations of the models their equivalence, congruence and isomorphism basing on the tables D. We have shown superiority of the investigated models for representing the sets of combinatorial objects in comparing with the classical methodology. Then, the basic algorithms and their variants for different classes of models concerning the generation of choice functions are developed. The algorithms concerning rank use widely the tables D. The general methodology for parallel or distributed generation of the choice functions in SIMD or MIMD systems is used and developed.

PL

Zaproponowano metodę reprezentowania arbitralnych podzbiorów kompozycji liczb, dekompozycji zbiorów, podziałów liczb i zbiorów poprzez odpowiadające zbiory funkcji wyboru rodzin indeksowych. Istotne znaczenie dla reprezentowania arbitralnych zbiorów obiektów kombinatorycznych mają rosnące funkcje wyboru, monotoniczne funkcje wyboru oraz bijekcje. Zaproponowano i rozwinięto modele zbiorów obiektów kombinatorycznych jako modele nierankingowe oraz modele rankingowe. Przedstawiono ogólną teorię struktury arbitralnych zbiorów funkcji wyboru. Struktura ta reprezentowana jest poprzez tablice D, których elementy pozostają w związku z trójkątem Pascal'a oraz liczbami Stirling'a. Tablice D są wykorzystywane ponadto w algorytmach tworzących podstawy systemu generowania obiektów kombinatorycznych. Przedstawione w dalszej części twierdzenie o rankingu precyzuje własności modeli optymalnych z punktu widzenia możliwie najbardziej zwartych zbiorów rankingów funkcji należących do modelowanych zbiorów. Uzyskanie możliwie najbardziej zwartego zbioru rankingów ma istotne znaczenie dla sekwencyjnego, rozproszonego i równoległego generowania zbiorów funkcji wyboru. Ogólna metodologia generacji zbiorów funkcji wyboru w systemach SIMD, MIMD jest przedstawiona i rozwinięta w kolejnych rozdziałach.

Słowa kluczowe

EN

partition; composition; decomposition; indexed families; monotonic choice functions; increasing choice functions; modeling by rank; structural numbers; layer; combinatorial object generation

PL

kompozycje liczb; dekompozycje liczb; podzbiory arbitralne; bijekcje; modele nierankingowe; trójkąt Pascala; liczby Stirling'a; teoria rankingu

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2000
• Tom: Vol. 21, nr 2
• Strony: 1--193
• Opis fizyczny: bibliogr. 57 poz.

Twórcy

autor

Kapralski A.

• Wydział Automatyki, Elektroniki i Informatyki, Politechniki Śląskiej ul. Akademicka 16, 44-100 Gliwice tel. [phone]