01: Problemi e Algoritmi
42 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Quale di queste affermazioni descrive meglio un problema computazionale?

  • È limitato a operazioni aritmetiche semplici.
  • È un insieme di istanze senza criteri di risposta.
  • È un algoritmo ben definito per risolvere problemi complessi.
  • È una collezione di domande con una regola per riconoscere le risposte corrette. (correct)

Tutti i problemi computazionali sono univoci e ammettono una sola risposta.

False (B)

Cos'è un dominio in un problema computazionale?

L'insieme di istanze che hanno una risposta.

Il ________ comune divisore di due numeri interi positivi è il maggiore intero positivo che divide entrambi.

<p>massimo</p> Signup and view all the answers

Abbina i termini ai loro significati corretti:

<p>Algoritmo = Procedura per risolvere un problema Istanza = Un caso specifico di un problema computazionale Relazione binaria = Insieme di coppie ordinate Dominio = Insieme di istanze con risposta</p> Signup and view all the answers

Quale dei seguenti algoritmi è menzionato come importante nel cambiamento del mondo?

<p>PageRank (C)</p> Signup and view all the answers

Il pensiero computazionale è considerato una nuova abilità fondamentale oltre alla lettura, scrittura e calcolo.

<p>True (A)</p> Signup and view all the answers

Fornisci un esempio di un problema computazionale univoco.

<p>Moltiplicazione fra interi.</p> Signup and view all the answers

Quale delle seguenti affermazioni è vera riguardo agli algoritmi?

<p>Ogni algoritmo deve terminare per ogni ingresso ammissibile. (B)</p> Signup and view all the answers

L'algoritmo di Euclide è considerato il primo algoritmo conosciuto.

<p>True (A)</p> Signup and view all the answers

Qual è la definizione di un algoritmo deterministico?

<p>Un algoritmo deterministico è un algoritmo che produce sempre lo stesso output per lo stesso input.</p> Signup and view all the answers

Il problema della ________ è un famoso esempio di problema indecidibile.

<p>terminazione</p> Signup and view all the answers

Quale affermazione è corretto riguardo ai programmi?

<p>Un programma è scritto in un linguaggio di programmazione e può contenere diversi algoritmi. (C)</p> Signup and view all the answers

Esistono problemi computazionali che ammettono una soluzione algoritmica per qualsiasi input.

<p>False (B)</p> Signup and view all the answers

Abbina i nomi degli algoritmi ai loro scopi principali:

<p>Algoritmo di Euclide = Calcolo del massimo comune divisore Algoritmo di ordinamento = Ordinare una lista di elementi Algoritmo di ricerca binaria = Ricerca di un elemento in una lista ordinata Algoritmo di fattorizzazione = Scomporre un numero in fattori primi</p> Signup and view all the answers

Un ________ è una sequenza finita di operazioni meccanicamente eseguibili.

<p>procedura</p> Signup and view all the answers

Quale delle seguenti affermazioni sui problemi intrattabili è vera?

<p>Un problema intrattabile non ha un algoritmo con complessità polinomiale. (A)</p> Signup and view all the answers

Il numero di spostamenti richiesti per la Torre di Hanoi con n dischi è 2n - 1.

<p>True (A)</p> Signup and view all the answers

Cosa definisce un cammino hamiltoniano in un grafo?

<p>Un cammino che tocca tutti i vertici del grafo una e sola volta.</p> Signup and view all the answers

Il problema del ___________ cerca un picco in un vettore di numeri interi.

<p>peak finding</p> Signup and view all the answers

Nel caso peggiore dell'algoritmo Peak-Find, quanti confronti vengono effettuati?

<p>n-1 (B)</p> Signup and view all the answers

Esiste sempre un picco in un vettore di numeri interi.

<p>True (A)</p> Signup and view all the answers

L'algoritmo ___________ trova il picco più alto in un vettore.

<p>Peak-Find-Max</p> Signup and view all the answers

Abbina i seguenti termini ai loro rispettivi significati:

<p>Problema intrattabile = Un problema senza soluzione in tempo polinomiale NP-completo = Problemi che ammettono soluzioni in tempo polinomiale solo in alcuni casi Cammino hamiltoniano = Visita tutti i vertici del grafo una sola volta Picco = Elemento maggiore rispetto ai suoi vicini nel vettore</p> Signup and view all the answers

Se i = j in un vettore, quale delle seguenti affermazioni è corretta?

<p>A[i] è un picco (B)</p> Signup and view all the answers

Se A[q1 - 1] > A[q1], allora q1 è sicuramente un picco.

<p>False (B)</p> Signup and view all the answers

Definisci un picco in un vettore.

<p>Un picco è un elemento A[i] tale che A[i-1] ≤ A[i] ≥ A[i+1].</p> Signup and view all the answers

La dimostrazione suggerisce di scegliere la posizione arbitraria nel segmento considerato come _____.

<p>$q_k = igg floor rac{i_{k-1} + j}{2} igg floor$</p> Signup and view all the answers

Quale sequenza di operazioni è suggerita per trovare un picco?

<p>Scegliere sempre una posizione arbitraria poi ripetere la verifica (C)</p> Signup and view all the answers

Il teorema garantisce la presenza di un picco nel vettore A[0...n - 1].

<p>True (A)</p> Signup and view all the answers

Qual è la condizione necessaria affinché A[i1] e A[j1] siano considerati picchi?

<p>A[i1 - 1] ≤ A[i1] e A[j1] ≥ A[j1 + 1]</p> Signup and view all the answers

Abbina le seguenti variabili con il loro significato:

<p>i = Estremo sinistro del segmento j = Estremo destro del segmento q1 = Posizione arbitraria scelta nel segmento n = Numero totale di elementi nel vettore</p> Signup and view all the answers

Qual è la complessità temporale nella situazione peggiore per l'algoritmo Peak-Find-DI?

<p>O(log n) (A)</p> Signup and view all the answers

L'algoritmo Peak-Find-DI utilizza un metodo di ricerca lineare per trovare il picco.

<p>False (B)</p> Signup and view all the answers

Qual è l'output dell'algoritmo Peak-Find-DI quando viene applicato al vettore A = |1, 2, 6, 6, 5, 3, 3, 3, 7, 4, 5|?

<p>6 o 7</p> Signup and view all the answers

Nell'algoritmo Peak-Find-DI, viene effettuato un confronto tra __________ e i suoi elementi vicini.

<p>A[q]</p> Signup and view all the answers

Abbina le seguenti variabili con la loro descrizione corretta nell'algoritmo Peak-Find-DI:

<p>q = Indice medio del vettore A = Vettore di input i = Inizio del sotto-vettore j = Fine del sotto-vettore</p> Signup and view all the answers

Quale affermazione è vera riguardo alla variante Peak-Find-Left?

<p>Ha una complessità di O(n-1). (C)</p> Signup and view all the answers

Peak-Find-DI garantisce sempre di trovare un picco che è il valore massimo dell'array.

<p>False (B)</p> Signup and view all the answers

Cosa verifica l'algoritmo per determinare se A[q] è un picco?

<p>A[q-1] ≤ A[q] ≥ A[q+1]</p> Signup and view all the answers

Nel caso peggiore, il numero di confronti in Peak-Find-DI è $T(n) = T(2k) + k$ per __________.

<p>1 ≤ k ≤ log2 n</p> Signup and view all the answers

Quale operazione viene eseguita per la prima volta nel passo 3 dell'algoritmo Peak-Find-DI?

<p>Controllo della condizione del picco (D)</p> Signup and view all the answers

Flashcards

Problema computazionale

Un problema computazionale è un insieme di domande (istanze) per cui esiste un criterio (astratto) che definisce le risposte corrette.

Algoritmo

Un algoritmo è una sequenza di istruzioni che descrive come risolvere un problema computazionale.

Problema insolubile

Un problema computazionale è insolubile se non esiste un algoritmo che può risolvere tutte le sue istanze.

Problema intrattabile

Un problema computazionale è intrattabile se esiste un algoritmo che può risolverlo, ma l'algoritmo richiede un tempo o risorse eccessive per essere completato.

Signup and view all the flashcards

Problema del picco

Il problema del picco è un problema computazionale che chiede di trovare il punto più alto in un grafico o un insieme di dati.

Signup and view all the flashcards

Pensiero computazionale

Il pensiero computazionale è una capacità cognitiva che permette di problematizzare, analizzare ed elaborare soluzioni utilizzando il ragionamento logico e algoritmico.

Signup and view all the flashcards

Problema univoco

Un problema computazionale è univoco se ogni istanza ha una sola e unica soluzione.

Signup and view all the flashcards

Dominio di un problema

Il dominio di un problema computazionale è l'insieme di tutte le istanze che hanno una soluzione valida.

Signup and view all the flashcards

Procedura

Una procedura è una sequenza di operazioni meccanicamente eseguibili, che producono univocamente un'uscita a partire da certi ingressi.

Signup and view all the flashcards

Algoritmo Deterministico

Un algoritmo è deterministico se, eseguito più volte sullo stesso input, fornisce sempre lo stesso output.

Signup and view all the flashcards

Algoritmo Corretto

La coppia (input, output) è in R se l'algoritmo risolve correttamente il problema computazionale R per quell'input.

Signup and view all the flashcards

Problema Indecidibile

È un problema che non può essere risolto da un algoritmo.

Signup and view all the flashcards

Problema della Terminazione

Il problema della terminazione chiede se sia possibile sviluppare un algoritmo che, dato un programma e un input, determini se il programma termina o continua per sempre.

Signup and view all the flashcards

Programma (VS. Algoritmi)

Un programma può contenere diversi algoritmi.

Signup and view all the flashcards

Linguaggio di Programmazione

Un linguaggio che specifica come un computer deve eseguire un'azione.

Signup and view all the flashcards

Peak-Find-Left

Un processo per trovare il picco di un array, ovvero il valore massimo in un array, muovendosi da sinistra a destra cercando un valore maggiore.

Signup and view all the flashcards

Spostamenti nella Torre di Hanoi

Il numero di spostamenti necessari per risolvere la Torre di Hanoi con n dischi è 2^n - 1.

Signup and view all the flashcards

Problema NP-Completo

Un problema computazionale in cui tutte le sue istanze sono complesse da risolvere nel senso che la loro soluzione in tempo polinomiale è possibile se e solo se esiste un algoritmo in tempo polinomiale per risolvere tutti i problemi in NP.

Signup and view all the flashcards

Cammino Hamiltoniano

Un cammino in un grafo che visita ogni vertice esattamente una volta.

Signup and view all the flashcards

Peak-Find-Max

Un algoritmo che trova il picco di un array confrontando ogni elemento con il precedente.

Signup and view all the flashcards

Segmento con un Picco

Un segmento dell'array in cui è garantita la presenza di un picco.

Signup and view all the flashcards

Teorema sul Picco

Un teorema che dimostra l'esistenza di un picco in un segmento di un array che soddisfa determinate condizioni.

Signup and view all the flashcards

Divide et Impera

L'algoritmo Divide et Impera suddivide il problema in sottoproblemi più piccoli, risolve questi sottoproblemi e poi combina le soluzioni per ottenere la soluzione finale.

Signup and view all the flashcards

Algoritmo Peak-Find-DI

L'algoritmo inizia dividendo l'array in due metà. Poi, trova il picco in ciascuna delle due metà ed esegue la stessa procedura su ciascuna metà fino a quando non rimane un solo elemento. L'elemento finale è il picco dell'intero array.

Signup and view all the flashcards

Condizione del picco locale

A[q - 1] ≤ A[q] ≥ A[q + 1] indica che l'elemento A[q] è un picco locale, poiché è maggiore o uguale ai suoi vicini.

Signup and view all the flashcards

Ricerca del picco nelle due metà

Se A[q - 1] > A[q] allora il picco si trova a sinistra di q, mentre se A[q] < A[q + 1] allora il picco si trova a destra di q.

Signup and view all the flashcards

Complessità del Peak-Find-DI nel caso peggiore

L'algoritmo Peak-Find-DI esegue un massimo di log2 n confronti nel caso peggiore. Ciò significa che il tempo di esecuzione dell'algoritmo è logaritmico rispetto alla dimensione dell'array.

Signup and view all the flashcards

Complessità del Peak-Find-Left nel caso peggiore

L'algoritmo Peak-Find-Left esegue n - 1 confronti nel caso peggiore. Ciò significa che il tempo di esecuzione dell'algoritmo è lineare rispetto alla dimensione dell'array.

Signup and view all the flashcards

Confronto tra Peak-Find-DI e Peak-Find-Left

Nel caso peggiore, l'algoritmo Peak-Find-DI è più efficiente del Peak-Find-Left perché richiede un numero di confronti logaritmico rispetto alla dimensione dell'array.

Signup and view all the flashcards

Caso peggiore - Peak-Find-DI

Il caso peggiore per l'algoritmo Peak-Find-DI si verifica quando il picco si trova all'estremità dell'array.

Signup and view all the flashcards

Caso peggiore - Peak-Find-Left

Il caso peggiore per l'algoritmo Peak-Find-Left si verifica quando il picco si trova all'estremità dell'array.

Signup and view all the flashcards

Picco in una sequenza

Un picco in una sequenza di numeri è un elemento che è maggiore o uguale ai suoi vicini. Se l'elemento è il primo o l'ultimo della sequenza, allora deve essere maggiore o uguale solo al suo vicino immediato.

Signup and view all the flashcards

Dimostrazione del Teorema del Picco

La dimostrazione del Teorema del Picco utilizza un ragionamento per ricorsione. Si parte da un segmento iniziale della sequenza e si cerca un picco. Se non si trova un picco, si riduce il segmento e si ripete il processo. Alla fine o si trova un picco o si arriva a un segmento di un solo elemento, che è automaticamente un picco.

Signup and view all the flashcards

Algoritmo per trovare un picco

La dimostrazione del Teorema del Picco suggerisce un algoritmo per trovare un picco in una sequenza. L'algoritmo consiste nel suddividere la sequenza in due metà e nel cercare un picco in una delle due metà. Se non si trova un picco, si ripete il processo nella metà restante. Questo processo è chiamato ricerca binaria.

Signup and view all the flashcards

Scelta del punto medio nel Teorema del Picco

Nell'algoritmo per trovare un picco, la scelta del punto medio del segmento considerato è fondamentale. Scegliendo il punto medio, si dimezza il segmento considerato ad ogni passo, il che velocizza la ricerca del picco.

Signup and view all the flashcards

Efficienza della ricerca di un picco

L'utilizzo di metodi di ricerca come la ricerca binaria può rendere più efficiente la ricerca di un picco in una sequenza. Questi metodi permettono di ridurre il numero di passaggi necessari per trovare il picco.

Signup and view all the flashcards

Applicazioni del Teorema del Picco

Il Teorema del Picco ha applicazioni in diversi campi, come l'analisi dei dati, l'ottimizzazione e l'intelligenza artificiale. Ad esempio, può essere utilizzato per trovare i punti massimi in un grafico o per identificare i valori estremi in un set di dati.

Signup and view all the flashcards

Importanza del Teorema del Picco

Il Teorema del Picco è un risultato importante nella teoria dell'informatica e ha un'ampia gamma di applicazioni. Capire questo teorema e le sue applicazioni è essenziale per una comprensione più profonda dell'informatica e delle sue applicazioni.

Signup and view all the flashcards

Study Notes

Introduzione a Problemi e Algoritmi

  • Obiettivi: Introduzione allo sviluppo e all'analisi di algoritmi.
  • Argomenti: Problemi computazionali, algoritmi, insolubilità, intrattabilità e il problema "Peak Finding".
  • Algoritmi e il Mondo: Molti algoritmi hanno profondamente cambiato il mondo (es. motori di ricerca, crittografia, riconoscimento di immagini).
  • Pensiero Computazionale: È una nuova abilità di base (oltre a leggere, scrivere e calcolare) introdotta a scuola per analizzare problemi e risolvere con algoritmi.
  • Definizione di Problema Computazionale: Una collezione di domande (istanze) con un criterio preciso per identificare le risposte corrette.
  • Massimo Comune Divisore (MCD): Un esempio di problema computazionale. Ingressi: due interi positivi; Uscite: il MCD di questi due interi.
  • Problemi Computazionali come Relazioni Binarie: Un problema computazionale è una relazione binaria che associa ingressi alle corrispondenti uscite.

Algoritmi

  • Algoritmo: Un metodo meccanico per risolvere un problema computazionale. Una sequenza di operazioni ben definite per ottenere un risultato.
  • Deterministico: Un algoritmo che produce sempre lo stesso output per lo stesso input.
  • Corretto: Un algoritmo risolve un problema se per ogni input fornisce l'output corretto.
  • Algoritmo di Euclide: Calcola il MCD di due numeri.
  • Programma vs. Algoritmo: Un programma può contenere diversi algoritmi.

Problemi Impossibili e Molto Difficili

  • Problemi Indecidibili: Problemi per i quali non esiste nessun algoritmo che possa sempre determinare una risposta.
  • Problemi Intrattabili: Problemi per i quali non è possibile trovare un algoritmo con una complessità polinomiale.
  • NP-completi: Un classe di problemi computazionali difficili. L'esistenza di un algoritmo efficace per risolverli è ancora un problema aperto.

Esempio: Peak Finding

  • Problema: Trovare un picco in un vettore (un picco è un elemento maggiore dei suoi vicini).
  • Algoritmo PEAK-FIND-LEFT: Un algoritmo per trovare il primo picco da sinistra.
  • Algoritmo PEAK-FIND-MAX: un algoritmo per trovare il picco massimo nell'intero vettore.
  • Algoritmo PEAK-FIND-DI: un algoritmo più efficiente utilizzando la tecnica "divide et impera".

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

Introduzione a Problemi e Algoritmi PDF

Description

Questo quiz esplora vari aspetti dei problemi computazionali, comprese definizioni e algoritmi chiave. Scoprirai l'importanza del pensiero computazionale nell'educazione moderna e come si applica a diverse situazioni. Metti alla prova la tua comprensione e il tuo sapere in questo campo affascinante.

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser