Inizio della pagina -
Logo DISCO
|
Visita la Versione ad elevata leggibilità
|
Vai al Contenuto della pagina
|
Vai alla Fine dei contenuti
|
Vai al Menu Principale
|
Vai alla Barra di navigazione (sei in)
|
Vai al Menu di navigazione (albero)
|
Vai alla Lista dei comandi
|
Vai alla Lista degli approfondimenti
|
Vai al Menu inferiore
|
Logo Ateneo
   
Didattica
Metodi algebrici per l'informatica

Codice ins.

Insegnamento

CFU ins.

Tipo ins.

Anno

Sem.

SSD ins.

Responsabile insegnamento

E3101Q129

Metodi algebrici per l'Informatica

8

OBS

2

1

MAT/02

DALLA VOLTA Francesca

 

Algebraic topics for computer science

 

 

 

 

 

 

Contenuti:
Introduzione alle strutture algebriche. Classi di resto; campi finiti; gruppi di permutazioni. Qualche applicazione  alla  crittografia asimmetrica (come si decide se un numero e' primo?) e alla crittografia simmetrica. Codici; codici lineari.

Obiettivi formativi:
Alla fine del corso lo studente sarà in grado di apprezzare l'utilità di strumenti astratti propri dell'algebra,  per affrontare alcuni argomenti legati al mondo dell'informatica, quali  la complessità di un linguaggio formale o le basi algebriche che assicurano la sicurezza di alcuni sistemi  crittografici attuali.

Prerequisiti:
Prerequisiti per affrontare questo corso sono le conoscenze matematiche della scuola media superiore e i contenuti matematici del corso di Fondamenti dell'Informatica

Metodi didattici:
Lezioni , esercitazioni, attività di studio individuale supportate da materiali didattici in e-learning.

Altre informazioni:
Programma esteso:

  • Richiami di base di aritmetica. Teorema fondamentale dell'aritmetica (scomposizione in fattori primi).
  • Algoritmo delle divisioni successive per il calcolo del massimo comun divisore tra due interi. Tempo di calcolo.
  • Richiami sulle relazioni di equivalenza. Congruenza modulo n. Insieme quoziente Zn..
  • Richiami sul concetto di operazioni su un insieme. Strutture algebriche. Monoidi, monoide  libero, gruppi.
  • Reticoli, anelli e algebre di Boole.
  •  Gruppi di permutazioni. Calcolo del numero di permutazioni su un insieme finito
  • Struttura di Zn.. Spazio vettoriale Z2n
  • Uso di  Zn e  Z2n nei moderni sistemi crittografici.
  • Congruenze lineari. Teorema cinese del resto.
  • Funzione φ di Eulero e suo uso in problemi di fattorizzazione.
  • Riconoscere se un numero e' primo.
  • Teorema di Fermat generalizzato. Descrizione del sistema crittografico RSA.
  • Campi; campi finiti .  Zn con n primo o potenza di un primo. 
  • Anello dei polinomi su un campo.
  • Costruzione di campi finiti a partire dall'anello dei polinomi.
  • Richiami su spazi vettoriali.
  • Sottospazi vettoriali e cenni sui codici lineari.
  • Gruppi di permutazioni. Azione su un insieme
  • Uso dei gruppi di permutazioni nello studio dei grafi, dei codici e dei sistemi crittografici
  • Gruppi di permutazioni e complessità.

Testi di riferimento:
Dalla Volta Francesca, Rigoli Marco, Elementi di matematica discreta e algebra lineare (Pearson);
Lindsay Childs, Algebra. Un'introduzione concreta (ETS);
Ronald L. Graham, Donald Knuth and Oren Patashnik Concrete Mathematics: A Foundation for Computer Science (Addison-Wesley Publishing Company.)

Modalità di verifica dell'apprendimento
Tipo esame:
scritto e orale
Tipo valutazione:
voto finale

Contents:
An introduction to algebraic structures.  Zn. . Fields and finite fields. Permutation groups. Some application to cryptography. Codes, linear codes.

Aims:
The students should understand the utility of algebraic topics  in the study of Computer Science problems (cryptography, complexity)

Prerequisiti:
To attend this course, the student should have a good knowledge of the Mathematics studied in higher school and the knowledge of mathematics topics of the Course  Fondamenti dell'Informatica

Teaching methods:
Lectures, class exercises,  some personal  activity supported by  e-learning.

 Program details:

  • basis  arithmetic Foundamental Theorem of arithmetic.
  • Extended Euclide's algorithm. Algorithm complexity.
  • Equivalenc relation.  The set  Zn..
  • Sets and operations. Algebaic structures.  Monoid,  free monoid; groups.
  • Lattices, Boole rings and Boole  algebrsa.
  • Permutation groupas. Counting the permutations on finite sets.
  • Structure of  Zn..  Vector space  Z2n
  •  Zn and   Z2n   in modern cryptography.
  • Linear congruences.  Chines Theorem.
  •  φ of Eulero in factorization problems.
  • How to understand if an integer number is a prime number.
  • Generalized  Fermat Theorem .  RSA.
  • Fields, finite field;   Zn when n is prime  or  a power of a prime number. 
  • Polynomial Ring..
  • How to construct finite fields from the polynomial ring.
  • Vector spaces.
  • Vector subspaces and linear codes.
  • Permutation groups: actions.
  • Permutation groups in graph theory, code theory and criptography.
  • Permutation groups and complexity.

Books:
Dalla Volta Francesca, Rigoli Marco, Elementi di matematica discreta e algebra lineare (Pearson);
Lindsay Childs, Algebra. Un'introduzione concreta (ETS);
Ronald L. Graham, Donald Knuth and Oren Patashnik Concrete Mathematics: A Foundation for Computer Science (Addison-Wesley Publishing Company.)

Course’ s exam procedures:
Written and oral examination

Tipo valutazione:
Mark

Approfondimenti

Google Translate
Translate to English Translate to French Translate to German Translate to Spanish Translate to Chinese Translate to Portuguese Translate to Arabic
Translate to Albanian Translate to Bulgarian Translate to Croatian Translate to Czech Translate to Danish Translate to Dutch Translate to Finnish Translate to Greek Translate to Hindi
Translate to Hungarian Translate to Irish Translate to Japanese Translate to Korean Translate to Norwegian Translate to Polish Translate to Romanian Translate to Russian Translate to Serbian
Translate to Slovenian Translate to Swedish Translate to Thai Translate to Turkish

(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - ultimo aggiornamento di questa pagina 11/11/2013