Pratica TLP 1920 (Italiano)

Lingue di programmazione

Fernando López Ostenenero e Ana García Serrano

Il concorso noto “Figures and lyrics” propongono due tipi di test ai suoi partecipanti: una delle figure in cui dovrebbero essere affrontati il più possibile per un numero target composizioni di base su un numero di numeri e una prova di lettere, dove devono trovare lapalabra ( valido) più a lungo che è possibile scrivere con una serie di lettere.

In questa pratica creeremo un programma che risolverà il secondo di tali test. Il programma riceverà una serie di lettere e tornerà tutte le parole valide costruite con loro. Per verificare se una parola è valida o meno, è essenziale utilizzare un dizionario.

Per fare ciò, un file verrà fornito con il dizionario 79517 WorderPene del Rae in modo che gli studenti possano Metti alla prova il tuo programma. Problemi di paravita A causa della codifica dei caratteri, tutte le parole sono state cancellate e gli accenti grafici sono stati rimossi.

Quindi, la pratica sarà divisa in due diverse fasi:

1. Creazione del dizionario: un file di testo che contiene le parole che considereremo valide (una parola per riga) sarà inserita e ognuna di esse verrà inserita in una struttura del dizionario su cui verranno consultate le parole possibili.
2. Ricerca di parole: Una volta disponibile il dizionario, il programma chiederà all’utente la sequenza di lettere di analizzare e restituire tutte le possibili parole valide che possono essere costruite da tali lettere, ordinate alfabeticamente e raggruppate per dimensioni da più alto per minore.

Affari che la voce / uscita nel paradigma funzionale non fa parte dell’agenda che è studiato l’argomento, tutte le funzioni responsabili della lettura del dizionario da un file o l Gli affari con l’utente saranno programmati per gli studenti. In questa affermazione ci sarà la presentazione del funzionamento di tali funzioni.

Dichiarazione pratica

La pratica è quella di elaborare un programma a Haskell che carica un file di testo di cospalabra valido e crede un dizionario . Una volta terminato, il programma chiederà all’utente sequenze di lettere diverse e restituiranno le parole valide (quelle presenti in Eldictionary) che possono essere costruite in base alle lettere disponibili.

Esempio 1: il programma cerca il programma File di dizionario da words (dic 80.txt), costruisce il dizionario e si aspetta che l’utente inserisci una sequenza di lettere:

* principale > elenco di parole Maincargo dal Dizionario file.txt79517 Leggi le parole

Inserire la sequenza di lettere:

Esempio 2: con il dizionario già caricato sopra, l’utente inserisce la sequenza delle lettere “ACS” e il programma restituisce tutto il parole del dizionario che possono essere costruite usando lettere:

Qui possiamo vedere il dizionario risultante rappresentato graficamente in una forma di albero. Come precedentemente sedicato, i nodi intermedi (tranne la radice, rappresentati come RN) sono i Unico che conosce i personaggi. E la concatenazione dei personaggi che formano il percorso dalla radice accessibile ai nodi foglia (rappresentati come WN) indica le parole presenti in Eldictionary.

per una migliore comprensione della struttura dei dati da utilizzare, noi Suggerisci agli studenti che eseguono un time touring del dizionario mostrato in figura 1 per verificare esattamente le undici parole indicate nell’elenco che è stato utilizzato per crearlo.

2.2 Struttura dei moduli di pratica

La pratica è divisa in due moduli, ciascuno in un file indipendente il cui nome (incluso maiuscolo e minuscolo) con il nome del modulo e il cui estensione è .hs:

1. del dizionario del modulo: All’interno di questo Modulo, le funzioni di costruzione e accesso al dizionario saranno pianificate. Include anche la definizione del tipo di dati del dizionario.
2. Modulo principale: questo modulo contiene il programma principale e tutte le funzioni responsabili del caricamento dell’elenco di parole e interagire con l’utente.

Poiché uno studio più profondo dei moduli di Haskell è al di fuori dell’ambito della laessignazione, indicheremo che ciascun modulo importa una serie di moduli necessari per il loro funzionamento. Nella nostra pratica le importazioni del modulo principale (oltre al modulo del modulo) moduli aggiuntivi per essere in grado di lavorare con l’output, i file e convertire tutte le lettere aminisse. Inoltre, l’elenco degli identificatori tra parentesi che accompagna l’annullamento del modulo dizionario rappresenta le definizioni dei tipi e delle funzioni che il ModuleExport.Qualsiasi altra definizione sarà considerata privata, essendo accessibile solo dal modulo.

figura 1: dizionario rappresentato in albero sagomato

2.3 DATA DATA TIPO (Docia dizionario)

In questa sezione introdurremo il tipo di dati che useremo per memorizzarsi in pratica. È definito nella parte del modulo dizionario che fornisce l’insegnamento eleger. Come abbiamo visto nella sezione precedente, un dizionario sarà un albero in cui i nodi intermedi conterranno un personaggio, mentre i nodi fogliame ci darà la formazione di quali parole appartengono al dizionario. Quindi, la definizione del tipo di dizionario:

dizionario dati = rootnode | char letternode | wordnode

ie, un dizionario è un rootnode (nodo root) che contiene un elenco di dizionari , Unletoternede (lettera nodo) che contiene un char e un dizionario, un elenco di dizionari, un wordnode (nodo parola) che sarà un nodo foglio che segnalizzerà che la concatenazione di tutti i letterecontenses nei nodi dalla radice (che non lo fa contenere nessuno) fino al padre del nodo foglia forma una parola valida del dizionario.

Questo tipo di dati viene aggiunto come istanza della classe Mostra, per essere in grado di visualizzare il contenuto di un tipo di dizionario Elemento e quindi facilitare il compito di programmare le funzioni Decrey del dizionario.

La rappresentazione interna del dizionario di figura 1 sarebbe il seguente:

rootnode]]], itternode ‘c’ ], Letternode ‘S’, Letternode ‘C’], LetterDe ‘O’]]], Leterde’o ‘]]], LetterDe’ O ‘]]]], LetterDe’ S ‘] ], Letternode ‘o’]]]]]

che è un po ‘più complicato da leggere rispetto alla rappresentazione grafica.

2.4 Programma principale (modulo principale)

Il modulo principale contiene il programma principale, già programmato dal team di insegnamento. Hayfunctions che usano monadi e sono scritti usando la “notazione di do”, che è una notazione per facilitare la scrittura di concatenazioni delle funzioni monordiche. Senza entrare troppo. Prendi il controllo del funzionamento delle monade, spiegheremo i tipi di dati definiti e noi spiegheremo i tipi di dati definiti e che ogni funzione.

tipi di dati

• wordsn: rappresenta un elenco di parole. Utilizzeremo questo tipo per fare riferimento a un elenco di tutte le stesse lunghezze e disposte alfabeticamente .
• parole: rappresenta un’elenco di parole. Utilizzeremo questo tipo per fare riferimento a un elenco di parole raggruppate in elenchi di parole di lunghezza uguale e disposti alfabeticamente.

Funzione di inserimento

Il tuo tipo sarebbe inserito inserimento :: stringa – > dizionario – > dizionario. Questa funzione è il si inserisce una parola nel dizionario ma già pensava come un albero. Il firstpameter dovrebbe essere Il resto della parola che rimane da inserire e il secondo parametro il nodododello dell’albero da cui è necessario inserire l’altro riposo di parole.

Funzione di insertchild

di tipo insertchild :: char – > – > – >. Nel firstpameter riceve il primo carattere del resto della parola da inserire, il secondo parametro il resto della parola da inserire (senza quel primo carattere), il terzo parametro un elenco di elementi di tipo di tipico (che sarà il Bambini di un nodo). Restituisce l’elenco dei bambini del nodo modificato correttamente.

Questa funzione è responsabile per cercare il bambino dal nodo corrente in cui è continuato l’inserimento dei caratteri che rimangono ancora della parola corrente. Nel caso in cui quel bambino non esistesse, la funzione lodeber creerà. Una volta localizzato (o creato) il bambino giusto, la funzione deve continuare il resto dei caratteri di parole da quel bambino. A questo punto suggeriamo agli studenti degli studenti “a mano” il dizionario rappresentato nella figura 1 per una migliore comprensione del processo inserendo parole nel dizionario.

2.6 Query al dizionario (modulo dizionario)

In questa sezione proveremo sulle consultazioni al dizionario. Il nostro obiettivo sarà quello di programmare la ricerca della sequenza che riceve una sequenza di caratteri e di un dizionario. Viene restituito dalla lista dei Scutrari, ordinata in ordine alfabetico, che sono contenute in Il dizionario e che possono essere convertiti con i caratteri sequenzi.

Ricerca :: stringa – > dizionario – >

Ad esempio, se cerchiamo la sequenza “cascao” sul dizionario rappresentato nella figura 1, dovremmo ottenere il seguente elenco di parole:

nota che “casi” e ” Sunset “, presente nel dizionario, non possono essere formati con le lettere del fideque, poiché contiene solo un ‘S’ (e” casi “ne ha due) e A ‘O’ (e “Sundo” ha due).

Come faremo la ricerca?Assumeremo che abbiamo già fatto un percorso precedente, ci ha portato a un nodo dell’albero (che non è un foglio). Pertanto, avremo ancora un sequenziamento dei caratteri non utilizzati e l’inizio di una parola formato dai caratteri presenta il percorso dalla radice al nodo corrente.

Ora analizziamo tutti i bambini del nodo corrente:

• Se un bambino è un wordnode, significherà che la parola che abbiamo già formato appartiene al dizionario, con il quale, sarà necessario aggiungerlo.
• Se un bambino è un itternode, conterrà un personaggio. Solo se questo personaggio appartiene alla sequenza non ancora esplorato (in qualsiasi posizione, non necessariamente il primo), dobbiamo esplorare ricorsivamente questo bambino, aggiungendo alla parola già formato il carattere del lettertode ed eliminando detto carattere dalla sequenza ancora non esplorata .

Raccomando di nuovo che gli studenti investiamo un tempo nell’esecuzione di questo scrub sull’albero di figura 1 per la sequenza “cascao” e controllare così esattamente le parole indicate.

Come nella sezione precedente, la funzione di ricerca avrà bisogno di una serie di funzioni (che non sarà visibile dall’esterno del modulo). I più importanti sono i seguenti seguenti lasdos:

funzione SearchinTree

Il tuo tipo sarebbe searchintree :: stringa – > stringa – > dizionario – >. Nel firstpameter riceve i caratteri della sequenza, ma non usa Due, nel secondo riceve la parola che è già stata formata finché non raggiunge il nodo dell’albero ricevuto come terzo parametro.

Devi restituire tutte le parole contenute nel dizionario di cui è il contenuto di Alla scoperta del parametro e proseguire dal nodo corrente (terzo parametro) utilizzando solo sequenza sequenziali non ancora esplorati (primo parametro).

searchchild

searchchild :: stringa – > String – > Dizionario – >. La funzione riceve ancora sequenza non esplorata, l’inizio della parola già costruito (in base al percorso occupato per raggiungere questo nodo dalla radice) e un nodo (figlio del nodo attualmente in fase di esplorato). Questa è la funzione che lo farà essere applicato l’algoritmo sopra spiegato per restituire l’elenco dei Scutratari che può essere formato con l’inizio già costruito e con i caratteri che non sono ancora utilizzati.

problemi sulla pratica

La risposta a queste domande è facoltativa. Tuttavia, se lo studente non risponde a queste domande, la qualifica della pratica può raggiungere solo 6 punti oltre 10.

1. (1’5 punti). Supponiamo un’implementazione di pratica in un linguaggio non dichiarativo (come Java, Pascal, C …). Commenta quali vantaggi e quali svantaggi avrei avuto di fronte all’implementazione di Haskell. Rilassati questi vantaggi dal punto di vista dell’efficienza rispetto alla programmazione e all’esecuzione. Quale sarebbe il punto principale a favore dell’attuazione in lingue non dichiarative? E l’implementazione in Haskell?
2. (1’5 punti). Indicare, con le tue parole, che ti consente di gestire il predicato non logico predefinito, tagliare (!), In Prall. Come dovrebbe essere eseguito questo effetto in Java? Giustifica la tua risposta.
3. (1 punto). Per i tipi di problemi del problema definito in Haskell (in entrambi i moduli), indicare quali tipi di costruttori di tipo sono stati utilizzati in ciascun caso (vedere il capitolo 5 del libro del soggetto).

Documentazione per consegnare

Ogni studente deve fornire la seguente documentazione al suo tutor pratico: – codice sorgente in Haskell che risolve il problema posato. Per fare questo, i file lyrics.hs and Dicight.hs devono essere consegnati, con le funzioni descritte in questa informativa, nonché tutte le funzioni ausiliarie necessarie. – Una memoria con: – una piccola descrizione delle funzioni programmate. – Le risposte a problemi sulla pratica.