Skip to content

Progetto d'esame OCaml per la materia Artificial Intelligent Systems: mod. Intelligent Application Development (A.A. 2022/2023)

Notifications You must be signed in to change notification settings

Meht-evaS/MassimaSottosequenzaComune_OCaml

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

11 Commits
 
 
 
 
 
 

Repository files navigation

Problema della massima sottosequenza comune: ricerca in profondità

Progetto d'esame, in linguaggio OCaml, per la materia Artificial Intelligent Systems: mod. Intelligent Application Development

📝 Sommario

🎯 Obiettivo

L'obiettivo di questo progetto è la creazione di un codice, in linguaggio OCaml, che permetta di risolvere il problema intitolato "Massima sottosequenza comune: ricerca in profondità".

❓ Problema

Si consideri un insieme finito S di stringhe ed un intero K. Determinare, se esiste, una stringa x di lunghezza maggiore o uguale a K che sia sottosequenza di ogni stringa s∈S . Si risolva il problema utilizzando una ricerca in profondità.

💻 Ambiente di lavoro

Il progetto è stato realizzato su Windows dove sono andato ad emulare l'ambiente Unix tramite il software Cygwin. Per installarlo, insieme ad OCaml, sono andato a sfruttare la procedura di installazione grafica disponibile alla seguente pagina GitHub.

⚙️ Setup

Per eseguire questo progetto puoi scaricare OCaml dal seguente sito web (lo stesso fornito al punto precedente) oppure utilizzare uno dei seguenti compiler online, onlinegdb OCaml e TryOCaml, dove puoi usare questo linguaggio in modalità interattiva senza scaricare nulla. Se preferisci usarlo localmente (tramite Cygwin), dovrai:

  1. Aprire l'applicazione Cygwin
  2. Andare al path del progetto: cd C:\\path\\to\\project
  3. Digitare: ocaml
  4. Importare le funzioni del progetto così da poterle richiamare; digitare:
#use "massima_sottosequenza_comune.ml";;

👨‍💻 Funzionamento codice

La spiegazione del codice è presente all'interno del file "Relazione_progetto.pdf", dove si possono vedere anche alcuni esempi di test del programma.

Le due funzioni principali sono:

  • ricerca_substring lista k: avvia la ricerca di una substring in comune tra tutte le stringhe presenti nella lista che viene passata in input alla funzione. Tale funzione va inoltre ad effettuare dei controlli di sicurezza per verificare che:
    • la lunghezza (K) della substring da cercare sia >= 0
    • la lunghezza (K) della substring da cercare sia <= lunghezza stringa più corta all'interno della lista in input
    • la lista in input contenga almeno un elemento La funzione restituisce in output una tupla (bool * string) in cui il valore bool ci indica se la ricerca ha avuto successo o meno mentre il valore string ci ritorna "" se la ricerca non ha avuto successo, altrimenti il valore della substring in comune tra tutte le stringhe.
  • genera_lista (): Genera una lista di stringhe, che viene poi salvata nel file "lista.txt", in base ad alcuni parametri che vengono chiesti interattivamente all'utente quali:
    • numero di stringhe da generare
    • lunghezza minima stringhe da generare
    • lunghezza massima stringhe da generare
    • valore della substring che avranno in comune tutte le stringhe generate

About

Progetto d'esame OCaml per la materia Artificial Intelligent Systems: mod. Intelligent Application Development (A.A. 2022/2023)

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages