Costantino DELIZIA | SEMIGRUPPI LIBERI E TEORIA DEI CODICI

cod. 0512300027

SEMIGRUPPI LIBERI E TEORIA DEI CODICI

	0512300027
	DIPARTIMENTO DI MATEMATICA
	CORSO DI LAUREA
	MATEMATICA
	2024/2025

PERCORSO COMUNE

	ANNO CORSO 3
	ANNO ORDINAMENTO 2018
	PRIMO SEMESTRE

MODULI

	SSD	CFU	ORE	ATTIVITÀ	TIPO DI ATTIVITÁ FORMATIVA
	MAT/02	6	48	LEZIONE	CARATTERIZZANTE

APPELLI

Appello	Data	Sessione
SEMIGRUPPI LIBERI E TEORIA DEI CODICI	13/01/2025 - 09:00	SESSIONE ORDINARIA
SEMIGRUPPI LIBERI E TEORIA DEI CODICI	13/01/2025 - 09:00	SESSIONE DI RECUPERO
SEMIGRUPPI LIBERI E TEORIA DEI CODICI	03/02/2025 - 00:09	SESSIONE ORDINARIA
SEMIGRUPPI LIBERI E TEORIA DEI CODICI	03/02/2025 - 00:09	SESSIONE DI RECUPERO
SEMIGRUPPI LIBERI E TEORIA DEI CODICI	07/03/2025 - 09:00	SESSIONE ORDINARIA

	Obiettivi
	OBIETTIVO GENERALE. L’OBIETTIVO DEL CORSO È FORNIRE LE NOZIONI DI BASE DEI SEMIGRUPPI LIBERI E DELLA TEORIA ALGEBRICA DEI CODICI. CONOSCENZA E CAPACITÀ 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À COMBINATORIE DELLE PAROLE SU UN ALFABETO. CAPACITÀ 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. IN PARTICOLARE, VERRÀ RICHIESTO DI PADRONEGGIARE CRITERI E ALGORITMI IN GRADO DI STABILIRE SE UN ASSEGNATO INSIEME DI PAROLE COSTITUISCE UN CODICE, E DI EVIDENZIARNE PROPRIETÀ DI CARATTERE SIA ALGEBRICO CHE COMBINATORIO. AUTONOMIA DI GIUDIZIO. LO STUDENTE DOVRÀ ESSERE IN GRADO DI VALUTARE, DIMOSTRARE O CONFUTARE ASSERZIONI DI VARIO LIVELLI DI COMPLESSITÀ, PRODUCENDO IN MANIERA AUTONOMA ESEMPI E CONTROESEMPI CHE BEN SI ADATTINO ALLE SITUAZIONI PROPOSTE. ABILITÀ COMUNICATIVE. LO STUDENTE SARÀ IN GRADO DI USARE UN LINGUAGGIO MATEMATICO FORMALE PER DESCRIVERE I PRINCIPALI CONCETTI ESAMINATI DURANTE IL CORSO. CAPACITÀ DI APPRENDIMENTO. LO STUDENTE SARÀ IN GRADO DI: - RISOLVERE PROBLEMI RELATIVI AGLI ARGOMENTI TRATTATI E PRODURRE ESEMPI; - CAPIRE ED ANALIZZARE LE IDEE ALGEBRICHE E COMBINATORIE CONTENUTE NELLE DIMOSTRAZIONI PROPOSTE AL CORSO; - RIUTILIZZARE LE IDEE FONDAMENTALI DI ALCUNE DIMOSTRAZIONI IN CONTESTI TALVOLTA DIVERSI DA QUELLI PROPOSTI DURANTE IL CORSO.

OBIETTIVO GENERALE. L’OBIETTIVO DEL CORSO È FORNIRE LE NOZIONI DI BASE DEI SEMIGRUPPI LIBERI E DELLA TEORIA ALGEBRICA DEI CODICI.

CONOSCENZA E CAPACITÀ 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À COMBINATORIE DELLE PAROLE SU UN ALFABETO.

CAPACITÀ 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. IN PARTICOLARE, VERRÀ RICHIESTO DI PADRONEGGIARE CRITERI E ALGORITMI IN GRADO DI STABILIRE SE UN ASSEGNATO INSIEME DI PAROLE COSTITUISCE UN CODICE, E DI EVIDENZIARNE PROPRIETÀ DI CARATTERE SIA ALGEBRICO CHE COMBINATORIO.

AUTONOMIA DI GIUDIZIO. LO STUDENTE DOVRÀ ESSERE IN GRADO DI VALUTARE, DIMOSTRARE O CONFUTARE ASSERZIONI DI VARIO LIVELLI DI COMPLESSITÀ, PRODUCENDO IN MANIERA AUTONOMA ESEMPI E CONTROESEMPI CHE BEN SI ADATTINO ALLE SITUAZIONI PROPOSTE.

ABILITÀ COMUNICATIVE. LO STUDENTE SARÀ IN GRADO DI USARE UN LINGUAGGIO MATEMATICO FORMALE PER DESCRIVERE I PRINCIPALI CONCETTI ESAMINATI DURANTE IL CORSO.

CAPACITÀ DI APPRENDIMENTO. LO STUDENTE SARÀ IN GRADO DI:
- RISOLVERE PROBLEMI RELATIVI AGLI ARGOMENTI TRATTATI E PRODURRE ESEMPI;
- CAPIRE ED ANALIZZARE LE IDEE ALGEBRICHE E COMBINATORIE CONTENUTE NELLE DIMOSTRAZIONI PROPOSTE AL CORSO;
- RIUTILIZZARE LE IDEE FONDAMENTALI DI ALCUNE DIMOSTRAZIONI IN CONTESTI TALVOLTA DIVERSI DA QUELLI PROPOSTI DURANTE IL CORSO.

	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.

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.

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

Orari Lezioni

BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2024-12-13]

Costantino DELIZIA | SEMIGRUPPI LIBERI E TEORIA DEI CODICI