Come costruire le stringhe combinatorie di Dyck

tramite: O2O
Difficoltà: facile
16

Introduzione

Walther F. A. Von Dyck è stato un matematico tedesco che ha vissuto tra l'Ottocento e il Novecento e tra le problematiche più importanti che ha analizzato negli anni ricordiamo l'analisi combinatoria. Nella guida vediamo come costruire le stringhe combinatorie che prendono il suo nome: le stringhe o parole di Dyck. Ti spiegherò nella maniera più semplice e completa possibile cosa sono e come si costruiscono, ma nel caso tu continuassi a non capire, ti invito ad approfondire l'argomento e a rivolgerti a qualcuno competente. Vediamo quindi cosa fare.

26

Per prima cosa devi sapere che, affrontando l'argomento di questa guida, ti troverai di fronte a un problema di natura combinatoria a prima vista non particolarmente complicato. Ti dico innanzitutto che le stringhe o parole (ovviamente non di senso compiuto) di Dyck utilizzano solo due lettere e prevedono un numero rigorosamente pari come lunghezza totale della parola stessa.

36

Per costruire una parola valida di Dyck, se chiami le due lettere utilizzabili A e B e ti poni, ad esempio, come obiettivo di costruire delle parole di lunghezza otto, ti è sufficiente sapere che devi costruire delle stringhe alfabetiche di otto lettere dotate dello stesso numero di occorrenze delle lettere A e B (in questo caso quattro), in modo tale però che non vengano mai costruite delle sequenze iniziali in cui il numero di lettere B utilizzato sia maggiore del numero di lettere A presenti nella medesima sequenza iniziale.

Continua la lettura
46

Puoi considerare immediatamente la parola-candidato AAABBBAB: essa è composta da otto lettere complessive, quattro sono A, quattro sono B, per verificare la restrizione imposta da Dyck devi considerare tutte le possibili sequenze iniziali della parola AAABBBAB.
In una parola di otto lettere puoi convenire che le sequenze iniziali possibili siano proprio otto, dove l'ultima è banalmente la parola di partenza.

56

Esamina la prima sequenza iniziale A, qui il numero di A è uno e quello di B è zero e puoi affermare che zero non è maggiore di uno. Analogamemte fino alla sequenza AAA in cui non ci sono ancora occorrenze della lettera B. Puoi agevolmente continuare fino alla sesta sequenza iniziale, costituita da AAABBB in cui raggiungi l'uguaglianza tra le quantità di A e B usate, ma comunque non la maggioranza per le B. Stesso discorso per la penultima (AAABBBA) e ultima sequenza iniziale (AAABBBAB): verifiche finali, queste, che ti consentono di concludere di aver costruito una stringa combinatoria di Dyck.

66

Applica nuovamente le regole dettagliate nella guida e riesci velocemente a verificare che le stringhe AABBAABB e ABABABAB sono sempre valide stringhe di Dyck, mentre non lo può essere la parola ABBAABBA (dove già nella terza sequenza iniziale ABB puoi constatare un numero di occorrenze di lettere B maggiore di quello delle occorrenze di A). Capire come costruire queste stringhe e il linguaggio creato da Dyck non è certamente semplice. Per comprenderlo al meglio è necessario studiarle per bene, con attenzione e poi metterle in pratica. Solo così se ne potrà avere una comprensione maggiore e migliore. Se proprio non riesci a capirlo da solo, e nemmeno questa guida fa al caso tuo, allora è meglio che tu ti rivolga a qualcuno esperto, che sappia spiegartelo nella maniera migliore e competente possibile. Non mi rimane altro che augurarti buon lavoro. Alla prossima.

Potrebbe interessarti anche

Segnala contenuti non appropriati

Tipo di contenuto
Devi scegliere almeno una delle opzioni
Descrivi il problema
Devi inserire una descrizione del problema
Si è verificato un errore nel sistema. Riprova più tardi.
Verifica la tua identità
Devi verificare la tua identità
chiudi
Grazie per averci aiutato a migliorare la qualità dei nostri contenuti

Guide simili

Università e Master

I numeri più strani della teoria delle stringhe

In fisica, la teoria delle stringhe ha completamente rivoluzionato il mondo scientifico grazie alle sue intuizioni innovative che sono ancora oggi oggetto di molteplici studi da parte di ricercatori in tutto il mondo. Il termine deriva dall'inglese "string"...
Università e Master

Come utilizzare le mappe di Karnaugh

La mappa di Karnaugh è un metodo di rappresentazione esatta di sintesi di reti combinatorie a uno o più livelli. Una tale mappa costituisce una rappresentazione visiva di una funzione booleana in grado di mettere in evidenza le coppie di mintermini...
Superiori

Come disegnare un diagramma delle classi

Nel linguaggio di modellizzazione unificato (UML), il diagramma delle classi è una delle rappresentazioni essenziali più comunemente utilizzate ed è utile per illustrare la struttura statica del sistema object-oriented, scomponendolo in classi definite...
Elementari e Medie

Come usare l'interpunzione in italiano: le virgolette, il trattino e le parentesi

La lingua italiana non è una lingua complicata, a patto che si conoscano le regole basilari. Alcune di queste riguardano all'interpunzione, ossia la punteggiatura. Nella seguente guida, passo dopo passo, vedremo come usare alcuni di questi segni indispensabili...
Università e Master

Appunti di Linguaggi Formali

Tra tutti i concetti legati al mondo dell'informatica, quello del "linguaggio" riveste sicuramente un ruolo di rilievo, essendo alla base di ogni tipo di programmazione. Esso è definito come un insieme di stringhe basate su un determinato alfabeto. L'informatica...
Superiori

Come calcolare i quartili in una distribuzione in classi

La statistica è una scienza che si occupa di elaborare e raccogliere dati. Lo studio dei dati a disposizione si basa su strumenti matematici molto potenti. Questi a sua volta ci consentono di trarre diverse conclusioni dall'analisi dei dati. Uno di questi...
Università e Master

Come scoprire il numero di Eulero

In matematica, ed in particolare in teoria dei numeri e in combinatoria, i numeri di Eulero En sono i componenti di una successione di interi che possono essere definiti dal seguente sviluppo in serie di Maclaurin della funzione secante iperbolica: Alcuni...
Università e Master

Come Costruire La Versione Matriciale Di Un Grafo

I grafi sono strutture matematiche discrete che rivestono interesse sia per la matematica che per un'ampia gamma di campi applicativi. In ambito matematico il loro studio, la teoria dei grafi, costituisce un'importante parte della combinatoria; i grafi...
I presenti contributi sono stati redatti dagli autori ivi menzionati a solo scopo informativo tramite l’utilizzo della piattaforma www.o2o.it e possono essere modificati dagli stessi in qualsiasi momento. Il sito web, www.o2o.it e Arnoldo Mondadori Editore S.p.A. (già Banzai Media S.r.l. fusa per incorporazione in Arnoldo Mondadori Editore S.p.A.), non garantiscono la veridicità, correttezza e completezza di tali contributi e, pertanto, non si assumono alcuna responsabilità in merito all’utilizzo delle informazioni ivi riportate. Per maggiori informazioni leggi il “Disclaimer »”.