Glossario Fondamenti di informatica

Nella teoria dei linguaggi formali, insieme finito e non vuoto di simboli, indicato di solito con Sigma, da cui si costruiscono le stringhe. Concatenando i suoi elementi si ottengono le stringhe, e l'insieme di tutte quelle possibili, inclusa quella vuota, si denota con Sigma*; un linguaggio e un sottoinsieme di esso.

Struttura matematica formalizzata da George Boole nel 1854 che opera su due valori, vero e falso (1 e 0), tramite gli operatori logici AND, OR e NOT. È il fondamento teorico della logica proposizionale e dei circuiti digitali, alla base della progettazione dei calcolatori elettronici.

Unità aritmetico-logica, il circuito combinatorio del processore che esegue le operazioni aritmetiche come addizione e sottrazione e quelle logiche come AND, OR e confronti. Riceve gli operandi dai registri e un codice che seleziona l'operazione, producendo il risultato e i flag di stato come carry e zero.

Modello di architettura dei calcolatori che tiene fisicamente separate la memoria delle istruzioni e quella dei dati, con bus distinti, così da accedervi simultaneamente. Il nome deriva dal calcolatore Harvard Mark I. Si contrappone a quella di von Neumann ed e comune nei microcontrollori e nelle cache separate.

Modello di calcolatore in cui dati e istruzioni risiedono nella stessa memoria condivisa e vengono letti dalla CPU attraverso un unico bus. Comprende unità di controllo, unità aritmetico-logica (ALU), memoria e dispositivi di I/O. La condivisione del bus tra dati e istruzioni genera il cosiddetto collo di bottiglia di von Neumann, che ne limita il throughput.

Principio fondamentale dell'informatica che gestisce la complessità nascondendo i dettagli implementativi ed esponendo solo le caratteristiche essenziali di un sistema tramite un'interfaccia. Consente di ragionare per livelli, dal linguaggio macchina all'alto livello; esempi sono funzioni, tipi di dato astratti e API.

Modello computazionale che estende l'automa a stati finiti con una memoria a pila (LIFO), da cui può leggere, inserire o rimuovere simboli a ogni transizione. Grazie a questa memoria riconosce i linguaggi liberi dal contesto, come le parentesi bilanciate, che gli automi finiti non riescono a gestire.

Modello computazionale astratto con un numero finito di stati e transizioni determinate dagli input. Dotato di memoria limitata e fissa, riconosce i linguaggi regolari e viene impiegato nell'analisi lessicale, nei protocolli di comunicazione e nella progettazione di circuiti sequenziali.

Principio dei sistemi di numerazione in cui il valore di una cifra dipende dalla sua posizione, ossia dalla potenza della base a essa associata. In base b la cifra di posto n vale la cifra moltiplicata per b elevato a n; così in base 10 il 3 di 300 pesa 3x10^2. Binario, decimale ed esadecimale ne sono esempi.

Unità di misura della velocità di segnalazione, pari al numero di simboli o variazioni di stato trasmessi al secondo su un canale; prende nome da Émile Baudot. Non coincide col bit rate: se ogni simbolo codifica più bit, la velocità in bit al secondo è un multiplo del baud rate.

Convenzione di ordinamento dei byte in memoria in cui il byte più significativo di un valore multibyte viene memorizzato all'indirizzo più basso, cioè per primo. È l'ordine usato nei protocolli di rete (network byte order) e da architetture come Motorola 68000, in contrapposizione al little-endian di x86.

Circuito elettronico che possiede due stati stabili e può permanere in uno di essi finché un segnale esterno non lo commuta, memorizzando così un bit. Il flip-flop ne e l'esempio tipico ed e l'elemento base delle memorie statiche (SRAM) e dei registri nei processori.

Unità elementare di informazione (binary digit), che può assumere solo due valori, 0 o 1. È il mattone della codifica digitale: aggregando n bit si rappresentano 2^n stati distinti e otto bit formano un byte. Nella teoria dell'informazione di Shannon il bit misura anche la quantità media di informazione o incertezza di una sorgente.

Bit aggiuntivo inserito in un blocco di dati per rilevare o correggere errori di trasmissione o memorizzazione. Il caso più semplice e il bit di parita, che rende pari o dispari il numero di uni; schemi più ricchi come i codici di Hamming o i CRC usano più bit per individuare e talvolta correggere le alterazioni.

Bit di controllo aggiunto a un gruppo di bit per rendere pari (parita pari) o dispari (parita dispari) il numero totale di uno, così da rilevare errori di trasmissione. Individua un numero dispari di bit alterati ma non lo corregge e non riconosce gli errori doppi; e la forma più semplice di codice rilevatore.

Bit più significativo di una rappresentazione binaria che indica il segno del numero: convenzionalmente 0 per un valore positivo e 1 per uno negativo. È usato nelle codifiche degli interi con segno come modulo e segno e complemento a due, dove ne definisce l'estremo negativo.

Least Significant Bit (LSB), il bit di peso minore in un numero binario, corrispondente alla potenza 2^0 e posto convenzionalmente all'estremita destra. Determina la parita del valore e, nella conversione da decimale, e il primo resto della divisione per 2; e sfruttato ad esempio in steganografia per nascondere dati.

In un numero binario è la cifra con peso maggiore, posta più a sinistra, che contribuisce di più al valore complessivo (MSB, most significant bit). Nella rappresentazione con segno indica tipicamente il segno del numero; il suo opposto è il bit meno significativo (LSB), di peso unitario.

Quantità di bit trasmessi o elaborati nell'unità di tempo, misurata in bit al secondo (bps) e nei multipli kbps, Mbps, Gbps. Caratterizza la velocità di un canale di comunicazione o la qualità di un flusso audio o video compresso; va distinta dal baud rate, che conta i simboli al secondo.

Insieme di linee elettriche parallele che trasporta i dati tra la CPU, la memoria e le periferiche. La sua ampiezza in bit (ad esempio 32 o 64) determina quanti dati si trasferiscono per ciclo. Insieme al bus indirizzi e al bus di controllo forma il sistema di bus che collega i componenti del calcolatore.

Insieme di linee che trasporta i segnali di comando e temporizzazione con cui la CPU coordina memoria e periferiche, ad esempio read/write, clock, interrupt e segnali di ready. Affianca il bus dati e il bus indirizzi nel bus di sistema, sincronizzando e regolando le operazioni di trasferimento tra i componenti del calcolatore.

Insieme di linee del bus di sistema su cui il processore trasmette l'indirizzo della cella di memoria o della periferica da leggere o scrivere. E tipicamente unidirezionale, dalla CPU verso memoria e I/O, e la sua ampiezza in bit determina lo spazio indirizzabile: n linee indirizzano 2 elevato a n locazioni distinte.

Unità di informazione digitale formata da otto bit, capace di rappresentare 256 valori distinti (da 0 a 255), sufficienti per un carattere ASCII. E l'unità di base per misurare memoria e dati, da cui derivano i multipli kilobyte, megabyte, gigabyte e le corrispondenti forme binarie kibibyte e mebibyte.

Branca della teoria della computazione che studia quali funzioni o problemi possono essere risolti in linea di principio da un modello di calcolo astratto come la macchina di Turing. Distingue i problemi decidibili da quelli indecidibili, come il celebre problema dell'arresto.

Operazione che converte un segnale analogico continuo in una sequenza discreta rilevandone l'ampiezza a istanti regolari a frequenza fissa. Per il teorema di Nyquist-Shannon la frequenza deve essere almeno doppia della massima componente del segnale, per evitare l'aliasing e consentirne la ricostruzione.

Mezzo fisico o logico attraverso cui un segnale viaggia dalla sorgente al destinatario in un sistema di comunicazione, ad esempio un cavo, una fibra ottica o l'etere. È caratterizzato da banda, capacità e rumore; secondo il teorema di Shannon la capacità massima dipende dalla banda e dal rapporto segnale-rumore.

Massima velocità di trasmissione, in bit al secondo, alla quale l'informazione può viaggiare su un canale con probabilità di errore arbitrariamente piccola. Definita da Shannon nel 1948 come massimo dell'informazione mutua tra ingresso e uscita; per un canale gaussiano è data dalla formula di Shannon-Hartley.

Codice di un set di caratteri che non rappresenta un simbolo stampabile ma impartisce un comando di formattazione o di trasmissione. In ASCII occupa le posizioni 0-31 e 127; esempi sono il ritorno a capo (CR), l'avanzamento riga (LF), la tabulazione e il carattere di escape.

Valore di controllo calcolato dai dati con una funzione deterministica e trasmesso o memorizzato insieme a essi; ricalcolandolo alla ricezione si rilevano alterazioni accidentali. Usato in protocolli di rete e file, come il checksum di TCP/IP o i CRC. Rileva errori casuali ma non protegge da manomissioni intenzionali, per cui non è un meccanismo di sicurezza.

Ciclo base del processore, ripetuto per ogni istruzione: nella fase di fetch l'istruzione viene prelevata dalla memoria all'indirizzo del program counter, nella fase di decode viene interpretata dall'unità di controllo, nella fase di execute viene svolta dalla ALU o da altre unità. Poi il ciclo riprende.

Cifre che contano. Cifre di un numero che ne determinano la precisione, contate dalla prima diversa da zero fino all'ultima nota, esclusi gli zeri iniziali usati solo per collocare la virgola.

Circuito logico la cui uscita dipende esclusivamente dalla combinazione degli ingressi presenti in quell'istante, senza memoria dello stato passato. E realizzato con porte logiche come AND, OR e NOT; esempi tipici sono sommatori, multiplexer e decoder, in contrapposizione ai circuiti sequenziali dotati di memoria.

Circuito logico la cui uscita dipende sia dagli ingressi attuali sia dallo stato interno memorizzato in elementi come i flip-flop. A differenza dei circuiti combinatori possiede memoria ed è tipicamente sincronizzato da un clock; realizza registri, contatori e macchine a stati.

In teoria della complessità, classe dei problemi decisionali la cui soluzione, una volta fornita, e verificabile in tempo polinomiale da una macchina di Turing deterministica (ovvero risolvibili in tempo polinomiale da una macchina non deterministica). Include P; se P sia uguale a NP resta un problema aperto.

In teoria della complessità è l'insieme dei problemi decisionali risolvibili da una macchina di Turing deterministica in tempo polinomiale rispetto alla dimensione dell'input. Rappresenta i problemi considerati trattabili in modo efficiente ed è al centro della questione aperta P contro NP.

Segnale periodico a onda quadra che scandisce e sincronizza le operazioni dei circuiti digitali sequenziali. Ogni fronte, di salita o di discesa, coordina l'aggiornamento di registri e stati; la sua frequenza, misurata in hertz fino ai gigahertz, determina il ritmo di esecuzione delle istruzioni del processore.

Valore numerico intero che uno standard di codifica come Unicode assegna univocamente a un carattere astratto. Si annota come U+ seguito da cifre esadecimali, per esempio U+0041 per la lettera A. Unicode ne prevede oltre un milione; la trasformazione in byte avviene tramite codifiche come UTF-8 o UTF-16.

Standard di codifica dei caratteri a 7 bit (American Standard Code for Information Interchange) che associa un numero da 0 a 127 a lettere, cifre, punteggiatura e caratteri di controllo. Definito negli anni '60, è alla base di codifiche estese come Latin-1 ed è compatibile con UTF-8, che ne riproduce identici i primi 128 punti di codice.

Famiglia di codici a correzione d'errore ideata da Richard Hamming intorno al 1950, che inserisce bit di parita in posizioni potenza di due per individuare e correggere qualsiasi errore su singolo bit. Con un bit di parita globale aggiuntivo diventa SECDED, correggendo un errore singolo e rilevando quelli doppi.

Sistema di codifica binaria in cui due valori consecutivi differiscono per un solo bit. Questa proprietà riduce gli errori di lettura negli encoder di posizione e nei circuiti, perché evita transizioni multiple simultanee che potrebbero essere campionate in stati intermedi errati.

Trasformazione dell'informazione in simboli. Processo che rappresenta un dato o un messaggio mediante un insieme prestabilito di simboli, secondo una corrispondenza definita, allo scopo di trasmetterlo, memorizzarlo o elaborarlo.

Binary-Coded Decimal. Sistema che rappresenta ogni singola cifra decimale con un gruppo di quattro bit, mantenendo separate le cifre invece di convertire l'intero numero in binario; semplifica la conversione e la visualizzazione ma non sfrutta tutte le combinazioni disponibili.

Circuito combinatorio che trasforma un ingresso attivo tra molti in un corrispondente codice binario di uscita, riducendo numerose linee di segnale a poche linee codificate; svolge la funzione inversa del decodificatore.

Tecnica standard per rappresentare interi con segno: i valori negativi si ottengono invertendo tutti i bit del corrispondente positivo e sommando uno. Con n bit copre l'intervallo da -2^(n-1) a 2^(n-1)-1 e unifica addizione e sottrazione.

Rappresentazione di un intero negativo ottenuta invertendo tutti i bit del corrispondente valore positivo. Presenta due configurazioni distinte per lo zero, positivo e negativo, limite superato dalla rappresentazione in complemento a due.

Ramo dell'informatica teorica che studia le risorse di tempo e di spazio richieste da un algoritmo per risolvere un problema in funzione della dimensione dell'input, classificando i problemi in base alla loro difficoltà intrinseca.

Tecnica che riduce la dimensione dei dati scartando in modo irreversibile informazioni ritenute poco percepibili, come in JPEG o MP3; consente rapporti di compressione elevati a scapito della fedeltà all'originale.

Tecnica che riduce la dimensione dei dati eliminando la ridondanza in modo reversibile, così da poter ricostruire l'originale bit per bit; impiegata per testo, dati ed eseguibili, con esempi come ZIP e PNG.

Procedimento che riscrive uno stesso valore numerico passando da un sistema di numerazione a un altro, per esempio da decimale a binario o a esadecimale, senza alterare la quantità rappresentata ma solo la sua notazione.

Capacità di un codice di individuare e ripristinare automaticamente i bit alterati durante trasmissione o memorizzazione, aggiungendo ridondanza controllata come nei codici di Hamming, senza dover ritrasmettere i dati.

Cyclic Redundancy Check, controllo a ridondanza ciclica. Tecnica di rilevamento errori che tratta il blocco di dati come un polinomio e ne calcola il resto della divisione per un polinomio generatore, allegandolo come codice di controllo.

Elemento grezzo, privo di contesto o interpretazione, che rappresenta un fatto, una misura o un simbolo; acquista significato solo quando viene elaborato e messo in relazione, trasformandosi così in informazione.

Proprietà di un problema per cui esiste un algoritmo che, in un numero finito di passi, risponde sempre con certezza sì o no per ogni istanza; il problema della fermata è un classico esempio di problema indecidibile.

Processo inverso della codifica che, applicando la stessa corrispondenza usata in origine, ricostruisce l'informazione di partenza a partire dalla sua rappresentazione in simboli o in codice.

Circuito combinatorio che converte un codice binario in ingresso in un segnale attivo su una sola tra le sue molte uscite, selezionando l'output corrispondente al valore ricevuto; svolge la funzione inversa del codificatore.

Circuito combinatorio che instrada un singolo segnale di ingresso verso una sola tra molte uscite possibili, scelta in base ai bit di selezione; svolge la funzione opposta del multiplexer.

Rappresentazione grafica dei passi di un algoritmo o di un procedimento mediante blocchi di forma convenzionale collegati da frecce, dove ogni simbolo indica un'operazione, una decisione o il flusso di controllo tra le fasi.

Processo che converte un segnale o un'informazione analogica, di natura continua, in una sequenza di valori numerici discreti tramite campionamento e quantizzazione, rendendola così trattabile da un elaboratore.

Numero di posizioni in cui due stringhe di uguale lunghezza differiscono; per le stringhe binarie corrisponde al numero di bit diversi ed è alla base della capacità di un codice di rilevare e correggere gli errori.

Convenzione che stabilisce l'ordine con cui i byte di un dato multibyte vengono memorizzati o trasmessi: nel formato big-endian viene per primo il byte più significativo, nel little-endian quello meno significativo.

Misura della quantità media di informazione, o incertezza, prodotta da una sorgente di messaggi; definita da Claude Shannon come H = -somma di p·log2(p), fissa il limite inferiore ai bit necessari per codificarla senza perdita.

Componente della rappresentazione in virgola mobile che indica la potenza della base per cui va moltiplicata la mantissa, determinando l'ordine di grandezza del numero; nello standard IEEE 754 è memorizzato in forma polarizzata.

Notazione formale che descrive in modo compatto un insieme di stringhe tramite un modello di caratteri e operatori come concatenazione, alternativa e ripetizione; definisce i linguaggi regolari ed è usata per ricerca e validazione di testo.

Software di basso livello memorizzato in modo stabile nella memoria non volatile di un dispositivo, che ne controlla le funzioni fondamentali e fa da ponte tra l'hardware e il software di livello superiore.

Elemento di memoria sequenziale bistabile che conserva un singolo bit e ne aggiorna lo stato in risposta a un segnale di comando o al fronte del clock; è la cella elementare con cui si costruiscono registri e contatori.

Modo normalizzato di esprimere una funzione booleana come somma di prodotti (mintermini) o prodotto di somme (maxtermini), in cui ogni termine contiene tutte le variabili, così da ottenere una scrittura univoca della funzione.

Numero di cicli che il segnale di clock di un processore genera in un secondo, misurato in hertz; scandisce il ritmo delle operazioni ed è uno dei fattori che ne influenzano le prestazioni.

Circuito combinatorio che somma tre bit, i due addendi e il riporto entrante, producendo un bit di somma e un bit di riporto uscente; concatenandone più stadi si costruiscono sommatori binari a più bit.

Funzione che associa a una o più variabili logiche, ciascuna con valore vero o falso, un unico valore d'uscita vero o falso, secondo le operazioni dell'algebra di Boole; è il modello matematico dei circuiti digitali.

Classificazione dei linguaggi formali in quattro classi di potenza espressiva crescente (regolari, liberi dal contesto, dipendenti dal contesto, ricorsivamente enumerabili), ciascuna associata a un tipo di grammatica e di automa riconoscitore.

Unità binaria di quantità di dati pari a 2^30 byte, cioè 1024 mebibyte ovvero 1.073.741.824 byte; introdotta dallo standard IEC per distinguere in modo non ambiguo la potenza di due dal gigabyte decimale.

Unità di misura della quantità di dati pari, in base decimale, a un miliardo di byte (10^9), cioè 1000 megabyte; nel Sistema Internazionale corrisponde al prefisso giga applicato al byte, distinto dal gibibyte binario.

Insieme finito di regole di produzione che, a partire da un simbolo iniziale, genera tutte e sole le stringhe valide di un linguaggio formale, definendone la sintassi in modo rigoroso e non ambiguo.

Circuito combinatorio che somma due singoli bit producendo un bit di somma e un bit di riporto, senza tenere conto di un eventuale riporto entrante; è il blocco elementare da cui si compongono i sommatori binari.

Insieme dei componenti fisici e tangibili di un sistema di calcolo, come processore, memorie, schede e periferiche, contrapposto al software che ne definisce il comportamento tramite le istruzioni.

Unità di misura della frequenza nel Sistema Internazionale, pari a un ciclo o evento che si ripete una volta al secondo; ha simbolo Hz ed è usata per esprimere clock, frequenze di segnali e onde.

Standard tecnico che definisce la rappresentazione binaria dei numeri in virgola mobile e le relative operazioni; specifica i formati (segno, esponente polarizzato, mantissa), i valori speciali come infinito e NaN e le regole di arrotondamento.

Operazione booleana tra due proposizioni, premessa e conseguenza, che risulta falsa soltanto quando la premessa è vera e la conseguenza è falsa, mentre è vera in tutti gli altri casi.

Dato interpretato: risultato dell'elaborazione di uno o più dati che, collocati in un contesto, acquistano significato e riducono l'incertezza di chi li riceve. Nella teoria di Shannon la sua quantità si misura in bit ed è legata alla probabilità e all'imprevedibilità del messaggio.

Dato in ingresso: informazione che entra in un sistema, programma o funzione per essere elaborata e produrre un risultato. Può provenire da un utente, da una periferica come tastiera o sensore, da un file o da un altro processo, ed è contrapposto all'output generato dall'elaborazione.

Segnale che sospende temporaneamente l'esecuzione del programma corrente per far gestire alla CPU un evento urgente, come l'input da una periferica. Al termine della routine di servizio l'esecuzione riprende dal punto interrotto, evitando l'attesa attiva e migliorando l'efficienza.

Unità di misura binaria della quantita di dati pari a 1024 (2 alla decima) byte esatti, definita dallo standard IEC 80000-13 e indicata dal simbolo KiB. E stata introdotta per eliminare l'ambiguita del kilobyte, spesso usato impropriamente per 1024 byte anziché per i 1000 byte del sistema decimale SI.

Unità di misura dei dati pari a 1000 byte nel sistema decimale (simbolo kB); nell'uso informatico tradizionale indica spesso 1024 byte, valore oggi indicato più propriamente come kibibyte.

Elemento bistabile di memoria sensibile al livello: e trasparente quando il segnale di abilitazione e attivo, lasciando passare l'ingresso in uscita, e mantiene memorizzato l'ultimo bit quando l'abilitazione e disattiva.

Insieme di stringhe costruite con i simboli di un alfabeto secondo regole sintattiche precise, definito da una grammatica o riconosciuto da un automa. E oggetto della teoria degli automi, che li classifica nella gerarchia di Chomsky: regolari, liberi dal contesto, contestuali e ricorsivamente enumerabili.

Insieme di istruzioni codificate in binario che il processore esegue direttamente, senza bisogno di traduzione. Ogni istruzione è una sequenza di bit interpretata dall'hardware secondo l'architettura della CPU, ed è il livello a cui corrispondono i linguaggi assembly leggibili dall'uomo.

Convenzione di ordinamento dei byte in memoria che colloca per primo, all'indirizzo più basso, il byte meno significativo di un valore multibyte. È adottata dalle architetture x86 e si contrappone al big-endian, usato in altri sistemi e nei protocolli di rete.

Sistema logico fondato su due soli valori, convenzionalmente vero e falso (1 e 0), che costituisce la base dell'algebra booleana e dell'elaborazione digitale. Le variabili si combinano con operatori come AND, OR e NOT, implementati fisicamente da porte logiche e circuiti che elaborano segnali a due stati.

Modello teorico e idealizzato di dispositivo di calcolo, definito dalle operazioni che sa eseguire, usato per studiare algoritmi e livelli di esecuzione indipendentemente dall'hardware reale.

Modello di calcolo astratto con nastro potenzialmente infinito e testina di lettura/scrittura che, tramite regole di transizione, definisce formalmente la nozione di funzione calcolabile.

Nella rappresentazione in virgola mobile, la sequenza di cifre significative che porta la precisione del numero; detta anche significando, viene moltiplicata per la base elevata all'esponente.

Rappresentazione grafica a griglia di una funzione booleana che ne facilita la minimizzazione manuale. Disponendo gli ingressi in codice Gray, celle adiacenti differiscono per un solo bit: raggruppando gli '1' in blocchi di potenze di due si eliminano le variabili ridondanti e si ottiene l'espressione minima.

Unità di misura binaria della quantita di dati pari a 1024 kibibyte, ossia 1.048.576 (2 alla ventesima) byte esatti; simbolo MiB, definita dallo standard IEC 80000-13. Costituisce l'alternativa precisa al megabyte decimale (10 alla sesta byte), evitando la confusione tra le due convenzioni nel calcolo delle dimensioni.

Unità di misura della quantità di dati pari nel sistema decimale a un milione (10 alla sesta) di byte, simbolo MB. Nell'uso storico e in alcuni contesti indicava 1.048.576 byte, cioè 2 alla ventesima, valore che lo standard IEC chiama oggi mebibyte (MiB) per evitare ambiguità.

Memoria piccola e molto veloce interposta fra CPU e memoria centrale, che conserva dati e istruzioni usati di recente. Sfruttando la localita temporale e spaziale degli accessi, riduce drasticamente i tempi medi di attesa colmando il divario di velocità con la RAM.

Strato di controllo interno al processore che traduce ogni istruzione macchina in una sequenza di micro-operazioni elementari su registri e unità funzionali. Risiede in una memoria di controllo e consente di implementare set di istruzioni complessi (CISC) e di correggerne il comportamento via aggiornamenti firmware.

Circuito combinatorio che seleziona uno tra più ingressi di dati e lo instrada su una singola uscita, in base al valore codificato sulle linee di selezione. Un multiplexer con n linee di selezione gestisce fino a 2^n ingressi; è usato per condividere risorse, instradare segnali e costruire funzioni logiche.

Gruppo di quattro bit, pari a meta di un byte. Può assumere sedici valori (da 0 a 15) e corrisponde esattamente a una cifra esadecimale, per cui un byte si scrive con due caratteri esadecimali. Il termine si usa quando si manipolano dati a livello di singole cifre esadecimali.

Rappresentazione binaria che codifica anche il segno del valore, così da esprimere quantità positive e negative. La forma più diffusa è il complemento a due, che rende uniformi somma e sottrazione ed evita il doppio zero; su n bit copre l'intervallo da -2^(n-1) a 2^(n-1)-1.

Rappresentazione binaria che impiega tutti i bit disponibili per la magnitudine, senza un bit riservato al segno, e codifica quindi solo valori interi non negativi. Con n bit copre l'intervallo da 0 a 2^n-1; è usata per indirizzi, contatori e dati non negativi. Si contrappone alle rappresentazioni con segno come il complemento a due.

Classe dimensionale di una quantita espressa come potenza di dieci più vicina, ricavabile dal logaritmo decimale del valore. Consente di confrontare in modo sintetico grandezze molto diverse e di ottenere stime approssimate: due valori differiscono di un ordine di grandezza quando il loro rapporto e circa dieci.

Risultato in uscita di un'elaborazione: l'informazione o il dato prodotto da un sistema, programma o dispositivo al termine del processo e reso disponibile all'utente, a una periferica o a un altro processo. Si contrappone all'input; esempi tipici sono il testo a schermo, un file salvato o un segnale inviato in rete.

Condizione di errore che si verifica quando il risultato di un'operazione supera l'intervallo di valori rappresentabile con il numero di bit disponibili. Ad esempio la somma di due interi molto grandi può eccedere la capacità del registro, producendo un valore errato o un ritorno ciclico (wrap-around).

Schema di controllo d'errore in cui un bit aggiuntivo viene impostato affinché il numero totale di bit a uno nella parola risulti dispari. Alla ricezione si ricalcola la parita: se e diventata pari si e verificato un errore. Rileva un numero dispari di bit errati ma non li corregge.

Schema di rilevamento d'errore che aggiunge un bit di parità impostato affinché il numero totale di bit a uno nella parola risulti pari. In ricezione un conteggio dispari segnala un errore; il metodo rileva un numero dispari di bit alterati ma non è in grado di correggerli.

Tecnica di progettazione del processore che suddivide l'esecuzione delle istruzioni in stadi sovrapposti, così che mentre un'istruzione viene decodificata la successiva viene già prelevata. Aumenta il throughput sfruttando il parallelismo, ma introduce complicazioni come gli hazard da gestire.

Porta logica fondamentale che realizza la congiunzione booleana: l'uscita e a livello alto (1) solo quando tutti gli ingressi sono a livello alto, altrimenti e 0. La sua tavola di verita da 1 unicamente per la combinazione con tutti gli ingressi a 1; si costruisce con transistor ed e un mattone dei circuiti digitali.

Porta logica la cui uscita è la negazione dell'AND degli ingressi: vale 0 solo quando tutti gli ingressi sono a 1. È funzionalmente completa, cioè da sole porte NAND si può realizzare qualsiasi funzione booleana, motivo per cui è un mattone fondamentale nella progettazione dei circuiti digitali.

Porta logica la cui uscita e la negazione della disgiunzione (OR) degli ingressi: vale 1 solo quando tutti gli ingressi valgono 0. E funzionalmente completa, cioè da sola può realizzare qualsiasi altra funzione booleana, per cui e impiegata come blocco elementare nella progettazione dei circuiti digitali.

Porta logica elementare a un solo ingresso, detta anche invertitore, che produce in uscita il valore logico complementare di quello in ingresso: 0 diventa 1 e viceversa. Realizza la negazione dell'algebra di Boole ed è un mattone fondamentale dei circuiti digitali, spesso costruita con transistor CMOS.

Porta logica fondamentale che realizza la disgiunzione booleana: l'uscita è a livello alto (1) quando almeno uno degli ingressi è a 1, e vale 0 solo se tutti gli ingressi sono a 0. Con due ingressi A e B calcola A OR B; combinata con AND e NOT permette di costruire qualsiasi funzione logica.

Porta logica che realizza la negazione dello XOR: produce un'uscita a livello alto solo quando gli ingressi hanno lo stesso valore. Con due ingressi funge da comparatore di uguaglianza ed è impiegata nei circuiti di confronto e nel controllo di parità dei dati.

Porta logica che realizza la disgiunzione esclusiva: con due ingressi l'uscita è alta solo quando i valori differiscono. Serve per confronti, calcolo della parità e addizione binaria, dove genera il bit di somma; nelle reti più ampie permette di rilevare la disparità tra i bit degli ingressi.

Nella rappresentazione numerica, il grado di finezza con cui un valore può essere espresso, determinato dal numero di bit dedicati a rappresentarlo, in particolare quelli della mantissa nel formato in virgola mobile. Una precisione maggiore riduce l'errore di arrotondamento e va distinta dall'accuratezza del risultato.

Problema indecidibile che dimostra l'impossibilità di un algoritmo generale capace di stabilire, per ogni programma e ogni input, se l'esecuzione terminerà oppure proseguirà all'infinito. La sua indecidibilità risale al lavoro di Alan Turing del 1936 e segna un limite fondamentale della calcolabilità.

Problema di decisione che appartiene alla classe NP ed è al tempo stesso NP-arduo: ogni altro problema di NP vi si riduce in tempo polinomiale. Sono i più difficili di NP e se ne esistesse un algoritmo polinomiale seguirebbe P=NP; esempi classici sono la soddisfacibilità booleana e il commesso viaggiatore.

Forma canonica di un'espressione booleana costituita da una congiunzione (AND) di più termini, ciascuno dei quali e una disgiunzione (OR) di variabili, detti termini somma o maxtermini. Si ricava dalle righe con uscita 0 della tavola di verita ed e la forma duale della somma di prodotti (mintermini).

Registro della CPU che contiene l'indirizzo di memoria della prossima istruzione da prelevare ed eseguire. Si aggiorna automaticamente a ogni ciclo, in genere incrementandosi, mentre i salti e le chiamate a funzione ne modificano il valore per dirigere il flusso del programma.

Descrizione di un algoritmo con sintassi informale, mista di linguaggio naturale e costrutti di programmazione, indipendente da uno specifico linguaggio e non direttamente eseguibile.

Operazione che approssima l'ampiezza di ogni campione di un segnale al livello discreto più vicino tra un numero finito di valori, introducendo l'errore detto rumore di quantizzazione.

Base di un sistema di numerazione posizionale: indica quante cifre distinte sono disponibili e la potenza che pesa ciascuna posizione. In base 10 le cifre vanno da 0 a 9 e le posizioni valgono potenze di dieci; l'informatica usa spesso base 2 (binario), 8 (ottale) e 16 (esadecimale).

Piccola cella di memoria interna al processore, estremamente veloce, che conserva temporaneamente dati, indirizzi o istruzioni durante l'elaborazione. Sta al vertice della gerarchia di memoria; esempi sono l'accumulatore, il program counter e l'instruction register. La sua ampiezza, ad esempio 32 o 64 bit, definisce la dimensione della parola macchina.

Registro composto da flip-flop in cascata che a ogni impulso di clock trasferisce i bit memorizzati di una posizione. È usato per convertire dati tra formato serie e parallelo, per introdurre ritardi e nei generatori di sequenze; ingresso e uscita possono essere seriali o paralleli secondo il tipo.

Registro strettamente collegato alla ALU che conserva uno degli operandi e ne riceve il risultato delle operazioni aritmetiche e logiche. Accumula i valori intermedi nei calcoli a più fasi, riducendo gli accessi alla memoria; e un elemento centrale nelle architetture di CPU più semplici e nelle prime macchine.

Registro speciale della CPU i cui bit, detti flag, riassumono l'esito dell'ultima operazione segnalando riporto, zero, segno o overflow, e guidano le istruzioni di salto condizionato.

Parte di un messaggio che non aggiunge informazione perché prevedibile o deducibile dal resto; può essere sfruttata per la compressione o per il rilevamento e la correzione degli errori.

Capacità di accorgersi che i dati sono stati alterati durante la trasmissione o la memorizzazione, aggiungendo ridondanza come bit di parità, checksum o CRC. A differenza dei codici correttori segnala l'errore senza necessariamente ripararlo, richiedendo di norma una ritrasmissione.

Alterazione casuale e indesiderata che si sovrappone a un segnale durante trasmissione, acquisizione o elaborazione, degradandone la qualità. Riduce l'informazione utile e il rapporto segnale-rumore; se ne limita l'effetto con filtri, ridondanza e codici di rilevazione e correzione degli errori.

Grandezza che varia con continuita nel tempo, assumendo infiniti valori intermedi entro un intervallo, in modo analogo alla grandezza fisica che rappresenta, come la tensione prodotta da un microfono. Si contrappone al segnale digitale, discreto e quantizzato; per essere elaborato da un calcolatore va convertito con un ADC.

Grandezza che rappresenta l'informazione mediante un insieme finito di livelli discreti, tipicamente due (0 e 1), definiti in istanti determinati. A differenza dell'analogico, continuo nel tempo e nei valori, e più robusto al rumore e adatto ai calcolatori; si ricava dall'analogico per campionamento e quantizzazione.

Insieme di tutti i comandi elementari che un processore riconosce ed esegue, con i relativi formati e modalita di indirizzamento. Costituisce l'architettura del set di istruzioni (ISA), l'interfaccia tra hardware e software; esempi sono x86, ARM e RISC-V, distinti nelle filosofie CISC e RISC.

Sistema di numerazione posizionale in base due che rappresenta ogni valore usando solo le cifre 0 e 1. Ogni posizione vale una potenza di due e si mappa naturalmente sui due stati elettrici di un circuito, il che lo rende la base della codifica e dell'elaborazione nei calcolatori.

Sistema di numerazione posizionale in base dieci che impiega le dieci cifre da 0 a 9. Ogni posizione ha peso pari a una potenza di dieci, così che la stessa cifra assume un valore diverso a seconda della posizione occupata; è il sistema di numerazione di uso quotidiano.

Insieme di convenzioni che associa in modo univoco simboli, caratteri o valori a sequenze di bit, così da rappresentarli, memorizzarli e trasmetterli. Esempi diffusi sono ASCII e Unicode (UTF-8) per i caratteri e il complemento a due per gli interi con segno; deve essere decodificabile senza ambiguita.

Sistema di numerazione posizionale in base sedici che impiega le cifre da 0 a 9 e le lettere da A a F per i valori da dieci a quindici. Offre una notazione compatta del binario, poiché ogni cifra corrisponde esattamente a quattro bit; è molto usato per indirizzi di memoria, byte e codici colore.

Sistema di numerazione posizionale in base otto che usa le cifre da 0 a 7. Ogni cifra ottale corrisponde esattamente a un gruppo di tre bit, il che lo rende una notazione compatta del binario, un tempo assai diffusa; oggi e in gran parte soppiantato dall'esadecimale, che raggruppa invece quattro bit per cifra.

Insieme dei programmi, delle istruzioni e dei dati che determinano il funzionamento di un elaboratore, in contrapposizione all'hardware fisico. Si distingue in software di sistema, come il sistema operativo che gestisce le risorse, e software applicativo, destinato a svolgere i compiti dell'utente.

Forma canonica di un'espressione booleana costituita da una disgiunzione (OR) di termini prodotto, ciascuno dei quali è una congiunzione (AND) di variabili o loro negazioni. Deriva direttamente dalle righe vere della tavola di verità e si presta alla semplificazione con le mappe di Karnaugh.

Nel modello di comunicazione di Shannon, l'entità che genera i messaggi o i simboli da trasmettere, primo elemento della catena prima di trasmettitore, canale e ricevitore. Spesso modellata come processo stocastico, la sua entropia misura l'informazione media prodotta e il limite di compressione senza perdite.

In un automa a stati finiti, stato che, se raggiunto al termine della lettura dell'input, segnala che la stringa appartiene al linguaggio riconosciuto; altrimenti la stringa e rifiutata. Detto anche stato finale, nei diagrammi si disegna con un doppio cerchio ed e centrale nella teoria dei linguaggi formali.

Stringa di lunghezza zero, priva di simboli, indicata di solito con epsilon o con la lettera greca lambda. È l'elemento neutro della concatenazione: unità a qualsiasi stringa la lascia invariata. Compare di frequente nella teoria dei linguaggi formali, negli automi e nelle espressioni regolari.

Schema che elenca il valore di uscita di una funzione logica per ogni possibile combinazione dei valori di verità degli ingressi; con n ingressi ha 2^n righe. Definisce operatori booleani come AND, OR e NOT e serve a specificare, verificare e semplificare circuiti logici ed espressioni booleane, base della progettazione digitale.

Misura dell'efficacia di una compressione, data dal rapporto tra la dimensione dei dati originali e quella dei dati compressi; un valore più alto, ad esempio 4:1, indica una riduzione maggiore. Dipende dall'algoritmo e dal tipo di dato e, nella compressione con perdita, si bilancia con la qualità del risultato.

Regola dell'algebra di Boole secondo cui la negazione di una congiunzione equivale alla disgiunzione delle negazioni, e la negazione di una disgiunzione alla congiunzione delle negazioni, scambiando così AND con OR. È fondamentale per manipolare espressioni logiche e progettare circuiti digitali.

Disciplina matematica fondata da Claude Shannon nel 1948 con 'A Mathematical Theory of Communication'. Quantifica l'informazione tramite l'entropia, misura dell'incertezza, e studia codifica, compressione e trasmissione affidabile su canali rumorosi, definendo limiti come la capacità di canale.

Unità di misura della quantita di dati pari a mille miliardi (10 alla dodicesima) di byte, ossia mille gigabyte nel sistema decimale SI; simbolo TB, adottato di norma per le capacità di dischi e archivi. Va distinto dal tebibyte (TiB), unità binaria pari a 2 alla quarantesima byte, circa il 10% più grande.

Regola di un automa o macchina a stati finiti che, dato lo stato corrente e il simbolo di ingresso, determina lo stato successivo ed eventualmente un'uscita. L'insieme delle transizioni forma la funzione di transizione, resa con diagramma o tabella; e alla base di parser, protocolli e circuiti sequenziali.

Standard internazionale che assegna a ogni carattere dei sistemi di scrittura del mondo un identificatore numerico univoco, detto code point, indipendente dalla codifica in byte. Codifiche come UTF-8 e UTF-16 traducono poi i code point in sequenze di byte, garantendo l'interoperabilità dei testi.

Componente del processore che dirige l'esecuzione delle istruzioni: le preleva, le decodifica e genera i segnali che coordinano e sincronizzano ALU, registri e memoria. Può essere realizzata con logica cablata o microprogrammata e, insieme all'ALU, costituisce il cuore operativo della CPU.

Codifica a lunghezza variabile dello standard Unicode che rappresenta ogni carattere con una o due unità da sedici bit. I caratteri del piano multilingue di base usano una sola unità, mentre quelli oltre il valore U+FFFF, come molti emoji, richiedono una coppia surrogata di due unità.

Codifica a lunghezza variabile dello standard Unicode che rappresenta ogni carattere con una sequenza di uno a quattro byte. È retrocompatibile con l'ASCII, che occupa un solo byte, è la codifica dominante sul web ed evita le ambiguità di ordinamento dei byte tipiche di altre codifiche.

Grandezza dell'algebra di Boole che può assumere soltanto due valori, vero o falso (1 o 0), corrispondenti agli stati della logica binaria. Combinata tramite gli operatori AND, OR e NOT compare nelle espressioni booleane e modella lo stato di ingressi, uscite e segnali nei circuiti digitali.

Rappresentazione dei numeri frazionari in cui la posizione della virgola e fissata a priori, con un numero predefinito di bit per la parte intera e per quella frazionaria. E più semplice e veloce della virgola mobile ma con intervallo e precisione limitati; si usa dove servono efficienza e determinismo, come nei DSP.

Rappresentazione dei numeri reali mediante una mantissa e un esponente rispetto a una base fissa, che permette di coprire un ampio intervallo di valori con precisione relativa. Lo standard IEEE 754 ne definisce i formati a 32 e 64 bit usati dai processori, con arrotondamenti e valori speciali.

Insieme di bit che il processore elabora come unità fondamentale nelle operazioni e nei trasferimenti. La sua ampiezza, tipicamente 16, 32 o 64 bit, caratterizza l'architettura della macchina e determina la dimensione dei registri e la quantità di dati gestita in un singolo ciclo.