SEMIGRUPPI LIBERI E TEORIA DEI CODICI

Matematica SEMIGRUPPI LIBERI E TEORIA DEI CODICI

0512300027
DIPARTIMENTO DI MATEMATICA
CORSO DI LAUREA
MATEMATICA
2022/2023

ANNO CORSO 3
ANNO ORDINAMENTO 2018
PRIMO SEMESTRE
CFUOREATTIVITÀ
648LEZIONE
Obiettivi
1.CONOSCENZA E CAPACITA' DI COMPRENSIONE: L'INSEGNAMENTO INTENDE FORNIRE UN'INTRODUZIONE ALLA TEORIA DEI SEMIGRUPPI E MONOIDI LIBERI E ALLA TEORIA DEI CODICI, CON PARTICOLARE RIFERIMENTO ALLE PROPRIETÀ DELLE PAROLE SU UN ALFABETO.
2.CAPACITA' DI APPLICARE CONOSCENZA E COMPRENSIONE: OBIETTIVO DELL'INSEGNAMENTO È ANCHE QUELLO DI RENDERE LO STUDENTE CAPACE DI RISOLVERE PROBLEMI DI VARIA NATURA APPLICANDO LE CONOSCENZE TEORICHE ACQUISITE.
Prerequisiti
GLI ARGOMENTI TRATTATI NEI CORSI DI ALGEBRA E ANALISI MATEMATICA DEL PRIMO ANNO.
Contenuti
SEMIGRUPPI E MONOIDI (24 ORE). IL TEOREMA DI ASSOCIATIVITÀ GENERALE. IL GRUPPO DEGLI ELEMENTI INVERTIBILI DI UN MONOIDE. ZERO DI UN SEMIGRUPPO. ELEMENTI IDEMPOTENTI. FATTORI DI UN ELEMENTO DI UN SEMIGRUPPO. SEMIGRUPPI CANCELLATIVI. SEMIGRUPPI COMMUTATIVI. CONDIZIONI NECESSARIE E SUFFICIENTI AFFINCHÉ UN SEMIGRUPPO SIA UN GRUPPO. IL SEMIGRUPPO DELLE PARTI DI UN SEMIGRUPPO. PRODOTTO DIRETTO DI SEMIGRUPPI E DI MONOIDI. IL SEMIGRUPPO E IL MONOIDE DELLE PAROLE SU UN ALFABETO. IL MONOIDE DELLE RELAZIONI BINARIE SU UN INSIEME. IL MONOIDE DELLE TRASFORMAZIONI DI UN INSIEME. IL MONOIDE DELLE FUNZIONI PARZIALI IN UN INSIEME. SOTTOSEMIGRUPPI E SOTTOMONOIDI. SOTTOSEMIGRUPPI E SOTTOMONOIDI GENERATI DA UNA PARTE DI UN SEMIGRUPPO. SEMIGRUPPI FINITAMENTE GENERATI. SEMIGRUPPI MONOGENICI. ORDINE DI UN ELEMENTO DI UN SEMIGRUPPO. INDICE E PERIODO DI UN ELEMENTO DI ORDINE FINITO. SEMIGRUPPI PERIODICI. OMOMORFISMI DI SEMIGRUPPI E DI MONOIDI. IMMERSIONE DI UN SEMIGRUPPO NUMERABILMENTE GENERATO IN UN SEMIGRUPPO 2-GENERATO. CONGRUENZE IN UN SEMIGRUPPO. SEMIGRUPPI E MONOIDI QUOZIENTE. TEOREMI DI OMOMORFISMO NEI SEMIGRUPPI E NEI MONOIDI. IDEALI DI UN SEMIGRUPPO. IDEALI GENERATI DA UNA PARTE DI UN SEMIGRUPPO. CONGRUENZE E QUOZIENTI DI REES. IL SEMIGRUPPO DEI FATTORI DI UNA PARTE PROPRIA DI UN SEMIGRUPPO. CONGRUENZE SINTATTICHE. SEMIGRUPPI SINTATTICI. SEMIANELLI. IL RETICOLO DELLE CONGRUENZE DI UN SEMIGRUPPO. CONGRUENZA GENERATA DA UNA RELAZIONE IN UN SEMIGRUPPO. SEMIGRUPPI E MONOIDI LIBERI. INSIEMI LINEARMENTE INDIPENDENTI E BASI. UNICITÀ DELLA BASE E SUE CARATTERIZZAZIONI. PROPRIETÀ UNIVERSALE DEI SEMIGRUPPI E DEI MONOIDI LIBERI. ESISTENZA ED UNICITÀ A MENO DI ISOMORFISMI DEL SEMIGRUPPO LIBERO E DEL MONOIDE LIBERO DI BASE AVENTE ASSEGNATA CARDINALITÀ. LUNGHEZZA DI UN ELEMENTO IN UN MONOIDE LIBERO. LEMMA DI LEVI. LEMMA DI LYNDON E SCHUTZENBEGER. SOTTOMONOIDI DI MONOIDI LIBERI. ELEMENTI IRRIDUCIBILI. CARATTERIZZAZIONI DEI SOTTOMONOIDI LIBERI DI UN MONOIDE LIBERO. TEOREMA DI SCHUTZENBEGER. PARTI LIBERABILI DI UN MONOIDE. SOTTOMONOIDI UNITARI A SINISTRA (UNITARI A DESTRA, BIUNITARI) DEL MONOIDE DELLE PAROLE SU UN ALFABETO. PRESENTAZIONI DI SEMIGRUPPI E DI MONOIDI. IL MONOIDE COMMUTATIVO LIBERO. IL MONOIDE BICICLICO.

COMBINATORIA DELLE PAROLE (8 ORE). LUNGHEZZA E FATTORI DI UNA PAROLA. PREFISSI E SUFFISSI. SOTTOPAROLE E LORO MOLTEPLICITÀ. PAROLE ROVESCIATE. PAROLE PALINDROME. PAROLE CONIUGATE. PAROLE PERMUTABILI. PAROLE PRIMITIVE. ESISTENZA ED UNICITÀ DELLA RADICE DI UNA PAROLA NON VUOTA. ORDINAMENTI NEI MONOIDI LIBERI: ORDINE PREFISSIALE, ORDINE SUFFISSIALE, ORDINE FATTORIALE, ORDINE DI DIVISIONE, ORDINE LESSICOGRAFICO, ORDINE MILITARE. INVILUPPO LIBERO DI UN INSIEME DI PAROLE SU UN ALFABETO. IL TEOREMA DEL DIFETTO.

CODICI (16 ORE). CARATTERIZZAZIONI DEI CODICI. CODICI UNIFORMI. CODICI DI ORDINE 2. CODICI PREFISSI, SUFFISSI, BIFISSI E LORO CARATTERIZZAZIONI. TEOREMA DI SARDINAS E PATTERSON. DISTRIBUZIONI DI BERNOULLI SU UN ALFABETO. MISURA DEGLI INSIEMI DI PAROLE INDOTTA DA UNA DISTRIBUZIONE DI BERNOULLI. DISUGUAGLIANZA DI KRAFT-MCMILLAN. FUNZIONE DI STRUTTURA SU UN INSIEME DI PAROLE. CODICI MASSIMALI. INSIEMI DI PAROLE DENSI. INSIEMI DI PAROLE COMPLETI. PAROLE PRIMARIE. COMPLETEZZA DI UN CODICE MASSIMALE. MASSIMALITÀ DI UN CODICE COMPLETO E NON DENSO. CODICI PREFISSI MASSIMALI E LORO CARATTERIZZAZIONI. CODICI SINCRONIZZANTI. CODICI BINARI A BLOCCHI: DECODIFICA PER MASSIMA PROBABILITÀ, DISTANZA DI HAMMING, CODICI ERROR-DETECTING, CODICI ERROR-CORRECTING.
Metodi Didattici
L'INSEGNAMENTO PREVEDE LEZIONI DI CARATTERE TEORICO, NEL CORSO DELLE QUALI SARÀ ANCHE ILLUSTRATO IL MODO IN CUI LE CONOSCENZE ACQUISITE POSSONO ESSERE UTILIZZATE PER LA SOLUZIONE DI PROBLEMI CONNESSI ALLE TEMATICHE AFFRONTATE.
Verifica dell'apprendimento
L'ESAME CONSISTE DI UNA PROVA ORALE, DURANTE LA QUALE SARANNO VALUTATE LA CONOSCENZA DEGLI ARGOMENTI TEORICI TRATTATI A LEZIONE MA ANCHE LA CAPACITÀ DI APPLICARLI NELLA SOLUZIONE DI SEMPLICI PROBLEMI. LA VALUTAZIONE FINALE SARA' ESPRESSA IN TRENTESIMI. LA LODE POTRÀ ESSERE ATTRIBUITA AGLI STUDENTI CHE DIMOSTRINO DI ESSERE IN GRADO DI APPLICARE AUTONOMAMENTE CONOSCENZE E COMPETENZE ACQUISITE ANCHE IN CONTESTI DIVERSI DA QUELLI PROPOSTI A LEZIONE.
Testi
A.DE LUCA, F.D'ALESSANDRO, TEORIA DEGLI AUTOMI FINITI, SPRINGER, MILANO, 2013.
Altre Informazioni
ULTERIORI INFORMAZIONI SULL'INSEGNAMENTO, TRA CUI IL PROGRAMMA IN VERSIONE PIÙ DETTAGLIATA, GLI ESERCIZI PROPOSTI DURANTE IL CORSO E LE DATE DEI PROSSIMI ESAMI POSSONO ESSERE CONSULTATE ALL'INDIRIZZO
HTTPS://DOCENTI.UNISA.IT/004267/HOME
EMAIL: cdelizia@unisa.it
  BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2022-11-21]