Galleria mappe mentale Capitolo Uno Introduzione
Un articolo sulle mappe mentali della struttura dei dati, concetti di base delle strutture dei dati, algoritmi e valutazione degli algoritmi, ecc. Spero che questo ti aiuti!
Modificato alle 2023-11-21 17:17:08Microbiologia medica, Infezioni batteriche e immunità riassume e organizza i punti di conoscenza per aiutare gli studenti a comprendere e ricordare. Studia in modo più efficiente!
La teoria cinetica dei gas rivela la natura microscopica dei fenomeni termici macroscopici e le leggi dei gas trovando la relazione tra quantità macroscopiche e quantità microscopiche. Dal punto di vista del movimento molecolare, vengono utilizzati metodi statistici per studiare le proprietà macroscopiche e modificare i modelli di movimento termico delle molecole di gas.
Este é um mapa mental sobre uma breve história do tempo. "Uma Breve História do Tempo" é um trabalho científico popular com influência de longo alcance. Ele não apenas introduz os conceitos básicos da cosmologia e da relatividade, mas também discute os buracos negros e a expansão. Do universo. questões científicas de ponta, como inflação e teoria das cordas.
Microbiologia medica, Infezioni batteriche e immunità riassume e organizza i punti di conoscenza per aiutare gli studenti a comprendere e ricordare. Studia in modo più efficiente!
La teoria cinetica dei gas rivela la natura microscopica dei fenomeni termici macroscopici e le leggi dei gas trovando la relazione tra quantità macroscopiche e quantità microscopiche. Dal punto di vista del movimento molecolare, vengono utilizzati metodi statistici per studiare le proprietà macroscopiche e modificare i modelli di movimento termico delle molecole di gas.
Este é um mapa mental sobre uma breve história do tempo. "Uma Breve História do Tempo" é um trabalho científico popular com influência de longo alcance. Ele não apenas introduz os conceitos básicos da cosmologia e da relatividade, mas também discute os buracos negros e a expansão. Do universo. questões científicas de ponta, como inflação e teoria das cordas.
Capitolo Uno Introduzione
1.1 Concetti base di struttura dei dati
Concetti di base e terminologia
1. Dati
L'insieme di tutti i simboli che possono essere immessi in un computer e riconosciuti ed elaborati da un programma informatico
Tutti i dati sono rappresentati nel computer come binari
2. Elementi dei dati
Gli elementi dei dati sono le unità di base dei dati e vengono generalmente considerati ed elaborati nel loro insieme
3. Dati
Gli elementi di dati sono composti da diversi elementi di dati, che sono le più piccole unità di dati indivisibili.
4. Oggetti dati
Un oggetto dati è una raccolta di elementi dati con le stesse proprietà
5. Tipo di dati
Un tipo di dati è una raccolta di valori e un insieme di operazioni definite su questa raccolta.
Classificazione
Tipo atomico
Tipi di dati i cui valori non sono divisibili
Ad esempio: int
tipo di struttura
Tipi di dati i cui valori possono essere suddivisi
Ad esempio: struttura
Tipo di dati astratti (ADT)
D: oggetto dati
S: relazione dati
P: Operazioni di base
Tre elementi della struttura dei dati
1. Struttura logica dei dati
definizione
Una raccolta di elementi di dati che hanno una o più relazioni specifiche tra loro
Classificazione
struttura lineare
relazione uno a uno
Caratteristiche
Ad eccezione del primo elemento, tutti gli altri elementi hanno un solo "precedente diretto"
Ad eccezione dell'ultimo elemento, tutti gli altri elementi hanno un unico "successore diretto"
raccogliere
Appartengono allo stesso set
Albero
relazione uno-a-molti
Caratteristiche
Ad eccezione del nodo radice, tutti gli altri punti hanno un solo "predecessore diretto"
Ad eccezione dei nodi foglia, tutti gli altri elementi hanno diversi "successori diretti"
griglia (Struttura grafica)
relazione molti-a-molti
Caratteristiche
Per ogni vertice possono esserci diversi "predecessori diretti" e "successori diretti"
2. Struttura fisica dei dati (struttura di stoccaggio)
definizione
La struttura di archiviazione si riferisce alla rappresentazione della struttura dei dati nel computer (chiamata anche immagine), chiamata anche struttura fisica
Classificazione
struttura di archiviazione sequenziale
definizione
Conservare i nodi logicamente adiacenti in unità di storage fisicamente adiacenti.
Generalmente rappresentato da un array
vantaggio
È possibile ottenere l'accesso casuale
Ogni elemento occupa il minimo spazio
discordanza
È possibile utilizzare solo un intero blocco adiacente di spazio di archiviazione, che è soggetto a frammentazione.
Illustrazione
struttura di stoccaggio a catena
definizione
Non è necessario che gli elementi logicamente adiacenti siano anche fisicamente adiacenti.
Utilizzare i puntatori per rappresentare le relazioni logiche tra gli elementi
vantaggio
Sfrutta al massimo tutto lo spazio di archiviazione
discordanza
Solo accesso sequenziale
I puntatori occupano ulteriore spazio di archiviazione
illustrare
Indirizzo dell'unità di storage all'interno del nodo: deve essere continuo
Indirizzi di unità di storage tra nodi: non necessariamente consecutivi
Illustrazione
Struttura di archiviazione dell'indice
definizione
Durante la memorizzazione delle informazioni sugli elementi dati, viene creata anche una tabella degli indici.
La forma generale è: <parola chiave, indirizzo>
vantaggio
Recupero veloce
discordanza
Le tabelle degli indici occupano spazio di archiviazione aggiuntivo
Quando si aggiungono o eliminano dati, è necessario modificare la tabella dell'indice
Struttura di archiviazione hash
definizione
Calcola l'indirizzo dell'elemento dati direttamente in base alla dimensione della parola chiave
Conosciuto anche come archiviazione hash
vantaggio
Il recupero, l'aggiunta e l'eliminazione dei nodi sono rapidi
discordanza
Se la funzione hash non è corretta, si verificheranno conflitti di archiviazione e la risoluzione dei conflitti aumenterà il sovraccarico di tempo e spazio.
struttura di archiviazione non sequenziale
3. Operazioni sui dati
definizione
Le operazioni applicate ai dati includono la definizione e l'implementazione delle operazioni.
Le operazioni sono definite per le strutture logiche
L'implementazione dell'operazione si basa sulla struttura fisica
1.2 Algoritmi e valutazione degli algoritmi
Concetti base di algoritmi
Formula di valore = algoritmo della struttura dati = programma
1. Definizione di algoritmo
È una descrizione dei passaggi per risolvere un problema specifico. È una sequenza finita di istruzioni, dove ciascuna istruzione rappresenta una o più operazioni.
2. Metodo descrittivo dell'algoritmo
linguaggio naturale
diagramma di flusso
pseudocodice
linguaggio di programmazione
3. Cinque caratteristiche degli algoritmi
(1) Finitezza
Termina dopo aver eseguito passaggi finiti e ogni passaggio può essere completato in un tempo finito
Ad esempio: codice di programma a ciclo infinito
(2) Certezza
Ogni istruzione deve avere un significato esatto in modo che non ci siano ambiguità quando il lettore la comprende.
Per lo stesso input è possibile ottenere solo lo stesso output
(3) Fattibilità
Le operazioni descritte nell'algoritmo possono essere realizzate eseguendo le operazioni base un numero limitato di volte.
(4)Ingresso
Un algoritmo ha zero o più input
(5)Uscita
Un algoritmo ha uno o più output
4. Valutazione degli algoritmi
(1) Correttezza
Gli algoritmi risolvono i problemi correttamente
Il livello “giusto”.
a. Il programma non contiene errori grammaticali
b. Per diverse combinazioni di dati di input del metodo, è possibile produrre risultati di output che soddisfano i requisiti.
c. In grado di produrre risultati di output che soddisfano i requisiti per i dati di input illegali
d. Per tutti i dati di input legali, è possibile produrre risultati di output che soddisfano i requisiti
(2) Leggibilità
Aiuta le persone a comprendere l'algoritmo
(3) Robustezza
Gli algoritmi possono anche reagire o elaborarsi in modo appropriato quando i dati di input sono illegali
(4) Alta efficienza e bassi requisiti di stoccaggio
L’efficienza si riferisce al tempo necessario per l’esecuzione di un algoritmo
I requisiti di archiviazione si riferiscono allo spazio di archiviazione massimo richiesto durante l'esecuzione dell'algoritmo.
Metriche degli algoritmi
metrica
complessità temporale
complessità spaziale
Metodo di misurazione
Statistiche post-evento
Utilizzare un timer per computer per cronometrare il tempo di esecuzione del programma sul computer
discordanza
(1) Il programma compilato in base all'algoritmo deve essere eseguito per primo
(2) Il tempo di esecuzione risultante dipende da fattori ambientali quali hardware e software del computer.
(3) Il costo di gestione del programma è relativamente elevato
Preanalisi e stima
Prima della programmazione del computer, gli algoritmi vengono stimati sulla base di metodi statistici
Il tempo necessario per l'esecuzione dipende da
(1) Quale strategia dovrebbe scegliere l’algoritmo?
(2) Entità del problema
(3) Linguaggio per scrivere programmi
(4) La qualità del codice macchina generato dalla compilazione
(5) La velocità con cui la macchina esegue le istruzioni
punto focale
Mettendo da parte i fattori legati all'hardware e al software del computer, si può considerare che la dimensione del "carico di lavoro" di uno specifico algoritmo dipende solo dalla dimensione del problema (n), o in altre parole, è una funzione del dimensione del problema.
complessità temporale
Metodo di calcolo
Frequenza della frase
Il numero di volte in cui l'operazione originale viene eseguita nell'istruzione all'interno del ciclo più profondo
rappresentazione della funzione
In generale, il numero di volte in cui vengono ripetute le operazioni di base dell'algoritmo è una funzione f(n) della dimensione del problema n, e la misurazione del tempo dell'algoritmo viene registrata come T(n)=O(f(n)) (complessità temporale)
punto focale
Guarda solo il livello più alto
Rimuovi il termine costante
ignorare il coefficiente
Relazione comune tra le dimensioni O(n).
tre condizioni
miglior complessità temporale
La peggiore complessità del momento
complessità temporale media
Fattori influenzanti
stato iniziale dei dati
Dimensione del problema
complessità spaziale
Metodo di calcolo
La complessità spaziale dell'algoritmo viene registrata come S(n)=O(f(n))
punto focale
Analizza lo spazio extra oltre l'input e il programma