Notes

Tutta sta parte si fa in modo formale in Sistemi Lineari e determinanti, quindi potresti saltarla totalmente Equazioni lineari L’obiettivo dell’algebra lineare è risolvere n equazioni con n sconosciuti di primo grado. Cosa che ci riesce con grandissimo successo! Andiamo ora a definire meglio cosa è una equazione lineare Definizione Una equazione lineare è una equazione a coefficienti appartenenti a un certo campo (che può essere R) e incognite il cui grado è 1 e che siano indipendenti: ...

Algebra modulare Assunzioni Andiamo ora ad assumere l’esistenza e correttezza di alcune cose di base. (in teoria si possono dimostrare da cose più di base, ma non ho tempo). Teorema fondamentale dell’algebra Ogni numero intero si fattorizza in modo unico. Algoritmo di Euclide La conseguenza più importante di questo teorema, dovuto ad Euclide è che se ho $a, b \in \mathbb{Z}$ allora esistono resto e dividendo fra i due. Ossia $\exists q, p : a\mid b = qk + p$ per qualche $k$ intero ...

Ultima modifica: September 18, 2022 9:43 AM Primo Abbozzo: September 16, 2022 9:52 AM Studi Personali: Yes Elementi di ripasso Measure Theory Introduzione Requirements of the measure function Vorremmo cercare di estendere il concetto di misurabilità a gruppi molto più ampi di un singolo intervallo, vorrei creare una funzione che sia in grado di misurare degli insiemi. *su vedrà che sono impossibili). Impossibilità di questi requirements (assurdo) Costruzione dell’insieme di interesse ...

Definizione gruppo Qualunque insieme più operazione tale per cui: Esistenza dell’inverso per ogni elemento $\forall g \in G, \exists g^{-1} \in G : gg^{-1} = e$ Esistenza di un elemento neutro $\exists e \in G: \forall g \in G, eg = g$ Associatività: $(gh)f = g(hf)$ Closure: $\forall g, h \in G \implies gh \in G$ Unicità dell’elemento neutro Supponiamo di avere un gruppo $G$ e due elementi neutri $e, f$ Allora abbiamo che $ae = a = af$ però se moltiplichiamo per l’inversa abbiamo che $a^{-1}ae = a^{-1}af \implies e = f$ ...

Gruppi ciclici e permutazioni Il gruppo ciclico Definizione gruppo ciclico Abbiamo definito in Gruppi per la prima volta il significato di gruppo ciclico generato da un elemento del gruppo, questo insieme si è poi dimostrato essere un sottogruppo del gruppo $$ G = \left\{ a^{n} \mid n \in \mathbb{Z} \right\} $$ Dove a è chiamato elemento generatore. $$ ord(G) = \lvert \langle a \rangle \rvert $$Criterio $a^{i} = a^{j}$ Probabilmente ha qualche relazione con Teorema di Lagrange. note sull’enunciato entrambe le frecce $\impliedby$ sono abbastanza ovvie. ...

Cook Levin theorem is important because says that in 1971 if $SAT \in P$ then $NP = P$. We will start with this idea to define the concept of NP-completeness. Let’s start with the basics. Poly-reduction Def: poly-reduction $$ x \in L' \iff f(x) \in L $$ This is very similar to the Halting Theorem and Reducibility#Mapping reducibility. The difference is that it needs to be polynomially-bounded, so to say, it is efficient function. ...

Introduzione Note filosofiche (non impo) Bisogna in primo momento cercare di definire cosa è la computazione e cosa è un computer. Aristotele faceva la distinzione fra proprietà essenziali e accidentali. Quelle essenziali sono proprie dell’oggetto. Una sedia può essere fatta di legno o di metallo, ma questa proprietà è accidentale, ovvero, essa rimane una sedia indipendentemente dal materiale di cui è fatta. Solitamente in matematica si prova ad astrarre (vedi Astrazione sul controllo per nota generale sull’astrazione). Però in questo campo si sono trovati molte concezioni equivalenti. Fino ad arrivare a concepire la tesi di Church-Turing. Il prof. nota che questo è strano, perché in altre discipline si converge in unico modello, mentre qui molte cose sono indifferenti. Questo è importante per capire come la concezione di Computer Science si è evoluta (Denning 2010). ...

Halting theorem Questo è un problema fondamentale, che abbiamo trattato anche in Fondamenti teorica#Halting problem, ma qui lo ritrattiamo, perché così lo rifacciamo per bene. In parte è stato trattato anche al corso di Logica. Enunciato Halting theorem $$ HALT = \left\{ \langle x, y \rangle \in \Sigma^{*} \times \Sigma^{*}: x = code(M),M \text{ si ferma su } x\right\} $$Dimostrazione Halting theorem La parte del sì è facile perché basta eseguirlo e vedere che si ferma (quindi abbiamo una La macchina di Turing#La macchina di Turing universale. Se si ferma appartiene al linguaggio, altrimenti è la parte in cui diverge. ...

This note is useful to gather in a single place the description of some common problems in CS and their theoretical implications explained in other notes. The Clique problem Description of the problem This problem is in NP, find all sub-graphs where all nodes are connected (this set of nodes forms a complete graph). We can prove that the problem is in NP because there is an easy non-deterministic algorithm that computes it. See Time and Space Complexity#Clique problem for details of this proof. ...

Introduction to the Rice Theorem Ci sono molti teoremi che non possono essere decisi, vedere Halting Theorem and Reducibility. Qui andiamo a chiederci quale sia l’insieme dei problemi decidibili. Proprietà dei linguaggi TM $$ L_{\mathcal{M}} = \left\{ x \in \Sigma^{*}: \mathcal{M} \text{ accetta } x \right\} $$$$ L_{\mathcal{M}} = L_{\mathcal{M}'} \implies P(\mathcal{M}) = P(\mathcal{M}') $$ Definiamo questa non triviale se esiste una macchina per cui è 0, e una per cui è 1 (ossia non è costante). Practically this definition is useful when we need to have a difference between the language and the Turing machine that decides that language. ...