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

    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</p> Signup and view all the answers

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

    <p>True</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.</p> Signup and view all the answers

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

    <p>True</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.</p> Signup and view all the answers

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

    <p>False</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.</p> Signup and view all the answers

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

    <p>True</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</p> Signup and view all the answers

    Esiste sempre un picco in un vettore di numeri interi.

    <p>True</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</p> Signup and view all the answers

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

    <p>False</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</p> Signup and view all the answers

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

    <p>True</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)</p> Signup and view all the answers

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

    <p>False</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).</p> Signup and view all the answers

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

    <p>False</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</p> Signup and view all the answers

    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