Wyniki wyszukiwania - BazTech

1

Aspekty algorytmiczne wyznaczania współczynników wielomianu Reeda-Mullera na podstawie trókąta Pascala

Tariova G., Tariov A.

Metody Informatyki Stosowanej

|

2009

|

nr 1 (18)

119-124

PL

W artykule opisano własności algorytmiczne organizacji sieci logicznej do wyznaczania współczynników wielomianu Reeda-Mullera na podstawie trójkąta Pascala. Pod kątem złożoności proponowane rozwiązanie lokuje się pomiędzy metodą bezpośredniego wyznaczania tych współczynników za pomocą iloczynu macierzowo-wektorowego oraz algorytmem na podstawie szybkiej transformaty koniunkcyjnej. Oznacza to, że uzyskana ostatecznie struktura jest mniej skomplikowana niż w przypadku realizacji metody bezpośredniej, oraz wymaga przy sprzętowej implementacji mniej elementów logicznych. Natomiast w porównaniu do struktury opartej na realizacji „szybkich” algorytmów wymaga ona więcej elementów logicznych, posiadając jednak bardziej regularną oraz prostszą strukturę. Cechą charakterystyczną proponowanego podejścia jest to, że w razie obecności na wejściach sieci logicznej wszystkich wartości funkcji boolowskich, odpowiednie wartości współczynników wielomianu Reeda-Mullera mogą być po kolei wyznaczone w trakcie realizacji procesu przetwarzania danych po rozpoczęciu każdej kolejnej iteracji. Natomiast w przypadku sekwencyjnego sposobu realizacji procesu obliczeniowego odpowiednie wartości współczynników tego wielomianu mogą być wyznaczone w trakcie nadchodzenia kolejnych wartości funkcji boolowskich, nie oczekując na obecność całego wektora danych na wejściach sieci. Tych walorów nie posiadają obydwie wspomniane metody, służące w tej pracy za punkt odniesienia. Wszystko to sprawia, że zaprezentowane w artykule podejście stanowi w pełni konkurencyjne rozwiązanie w stosunku do rozwiązań porównywanych.

EN

In the paper the approach to the rational organization of logical network structure for simplified calculation of Reed-Muller polynomial coefficients with the reduced number of logical operation (EXOR gates or modulo-2 adders - in hardware implementation case) is presented.

2

Partial semigroups and primality indicators in the fractal generation of binomial coefficients to a prime square modulus

Doan D., Kivunge B., Smith J., Sykes T., Teplitskiy M.

Demonstratio Mathematica

|

2009

|

Vol. 42, nr 1

23-39

EN

This paper, resulting from two summer programs of Research Experience for Undergraduates, examines the congruence classes of binomial coefficients to a prime square modulus as given by a fractal generation process for lattice path counts. The process depends on the isomorphism of partial semigroup structures associated with each iteration. We also consider integrality properties of certain critical coefficients that arise in the generation process. Generalizing the application of these coefficients to arbitrary arguments, instead of just to the prime arguments appearing in their original function, it transpires that integrality of the coefficients is indicative of the primality of the argument.

3

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

Kapralski A.

Studia Informatica

|

2000

|

Vol. 21, nr 2

1-193

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.