Matematica | FREE SEMIGROUPS AND THEORY OF CODES

Matematica FREE SEMIGROUPS AND THEORY OF CODES

 0512300027 DIPARTIMENTO DI MATEMATICA EQF6 MATHEMATICS 2022/2023

 YEAR OF COURSE 3 YEAR OF DIDACTIC SYSTEM 2018 AUTUMN SEMESTER
SSD CFU HOURS ACTIVITY TYPE OF ACTIVITY MAT/02 6 48 LESSONS COMPULSORY SUBJECTS, CHARACTERISTIC OF THE CLASS
 COSTANTINO DELIZIA T
ExamDate
SEMIGRUPPI LIBERI E TEORIA DEI CODICI08/02/2023 - 12:00
SEMIGRUPPI LIBERI E TEORIA DEI CODICI08/02/2023 - 12:00
Objectives
1.KNOWLEDGE AND UNDERSTANDING: THIS COURSE WILL PROVIDE AN INTRODUCTION TO THE THEORY OF FREE SEMIGROUPS AND MONOID AND TO THE THEORY OF CODES, WITH EMPHASYS ON PROPERTIES OF WORDS ON AN ALPHABET.
2.APPLYING KNOWLEDGE AND UNDERSTANDING: COURSE AIM IS ALSO TO ENABLE STUDENTS TO SOLVE MANY KINDS OF PROBLEMS APPLYING THE ACQUIRED THEORETICAL KNOWLEDGE.
Prerequisites
TOPICS COVERED IN THE FIRST YEAR ALGEBRA AND CALCULUS COURSES.
Contents
SEMIGROUPS AND MONOIDS (24 HOURS). THE GENERAL ASSOCIATIVITY THEOREM. THE GROUP OF UNITS OF A MONOID. ZERO ELEMENT OF A SEMIGROUP. IDEMPOTENT ELEMENTS. FACTORS OF A ELEMENT OF A SEMIGROUP. REGULAR SEMIGROUPS. COMMUTATIVE SEMIGROUPS. THE SEMIGROUP OF SUBSETS OF A SEMIGROUP. DIRECT PRODUCTS. WORD SEMIGROUPS AND MONOID. THE MONOID OF BINARY RELATIONS ON A SET. MONOIDS OF TRANSFORMATIONS. MONOIDS OF PARTIAL FUNCTIONS. SUBSEMIGROUPS AND SUBMONOIDS. SUBSEMIGROUPS AND SUBMONOIDS GENERATED BY A SUBSET. FNITELY GENERATED SEMIGROUPS. MONOGENIC SEMIGROUPS. THE ORDER OF A ELEMENT. THE INDEX AND THE PERIOD OF A ELEMENT OF FINITE ORDER. PERIODIC SEMIGROUPS. OMOMORPHISMS OF SEMIGROUPS AND MONOIDS. EMBEDDING OF A DENUMERABLY GENERATED SEMIGROUP IN A 2-GENERATED ONE. CONGRUENCES OF A SEMIGROUP. QUOTIENTS. HOMOMORPHISM THEOREMS. IDEALS. IDEALS GENERATED BY A SUBSET. REES CONGRUENCES AND REES QUOTIENTS. SEMIGROUPS OF FACTORS. SYNTACTIC CONGRUENCES. SYNTACTIC SEMIGROUPS. SEMIRINGS. THE LATTICE OF CONGRUENCES OF A SEMIGROUP. THE CONGRUENCE GENERATED BY A RELATION IN A SEMIGROUP. FREE SEMIGROUPS AND MONOIDS. LINERALY INDEPENDENT SETS AND BASIS. UNIQUENESS OF THE BASE. UNIVERSAL PROPERTY OF SEMIGROUPS AND MONOIDS. EXISTENCE AND UNIQUENESS UP TO ISOMORPHISMS OF FREE SEMIGROUP AND MONID WITH BASE OF GIVEN CARDINALITY. LENGHT OF A ELEMENT IN A FREE MONOID. LEVI LEMMA. LYNDON-SCHUTZENBEGER LEMMA. SUBMONOIDS OF FREE MONOIDS. IRRIDUCIBLE ELEMENTS. CHARACTERIZATIONS OF FREE SUBMONOIDS OF FREE MONOIDS. SCHUTZENBEGER THEROEM. UNITARY AND BIUNITARY SUBMONOIDS OF WORD MONOIDS. PRESENTATIONS OF SEMIGROUPS AND MONOIDS. THE FREE COMMUTATIVE MONOID. THE BICYCLIC MONOID.

COMBINATORICS ON WORDS (8 HOURS). LENGHT AND FACTORS OF A WORD. PREFIXES AND SUFFIXES. SUBWORDS AND THEIR MULTIPLICITY. REVERSED WORDS. PALINDROME WORDS. CONJUGATED WORDS. PERMUTABLE WORDS. PRIMITIVE WORDS. EXISTENCE AND UNIQUENESS OF THE ROOT OF A NON-EMPTY WORD. ORDERS IN FREE MONOIDS. THE FREE HALL. THE DEFECT THEOREM.

CODES (16 HOURS). CHARACTERIZATIONS OF CODES. UNIFORM CODES. ORDER 2 CODES. PREFIX, SUFFIX, BIFIX CODES AND THEIR CHARACTERIZATIONS. THE SARDINAS-PATTERSON THEOREM. BERNOULLI DISTRIBUTIONS ON AN ALPHABET AND MEASURES. THE KRAFT-MCMILLAN INEQUALITY. MAXIMAL CODES. DENSE SETS OF WORDS. COMPLETE SETS OF WORDS. COMPLETENESS OF A MAXIMAL CODE. MAXIMALITY OF A NON-DENSE COMPLETE CODE. PREFIX MAXIMAL CODES AND THEIR CHARACTERIZATIONS.
SYNCHRONIZING CODES. BINARY UNIFORM CODES: MAXIMUM LIKELIHOOD DECODING, HAMMING DISTANCE, ERROR-DETECTING CODES, ERROR-CORRECTING CODES.
Teaching Methods
THIS COURSE CONSISTS OF THEORETICAL LESSONS, DURING WHICH WILL ALSO BE SHOWN HOW THE GAINED KNOWLEDGE CAN BE USED FOR THE SOLUTION OF PROBLEMS RELATED TO THE ADDRESSED ISSUES.
Verification of learning
THE EXAMINATION IS AN ORAL INTERVIEW, BY WHICH THE KNOWLEDGE OF TOPICS COVERED DURING THE LESSIONS BUT ALSO THE CAPACITY TO USE THEM TO SOLVE PROBLEMS OF ELEMENTARY TYPE WILL BE EVALUED. THE FINAL EVALUATION IS EXPRESSED OUT OF 30. THE EXCELLENCE MAY BE REACHED BY STUDENTS WHO PROVE THEIR ABILITY TO APPLY THE ACQUIRED KNOWLEDGE AND SKILLS EVEN IN DIFFERENT CONTEXTS WITH RESPECT TO THOSE PROPOSED DURING THE LESSONS.
Texts
A.DE LUCA, F.D'ALESSANDRO, TEORIA DEGLI AUTOMI FINITI, SPRINGER, MILANO, 2013.