• Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X

Markov, algoritmo di

Enciclopedia della Matematica (2013)
  • Condividi

Markov, algoritmo di


Markov, algoritmo di sistema di riscrittura di stringhe costruito sulla base di una lista di regole. Gli algoritmi di Markov possono rappresentare ogni espressione matematica calcolabile e sono quindi un modello generale di calcolo (si usa dire che è un sistema Turing completo, nel senso che ogni funzione Turing-calcolabile è rappresentabile in questo simbolismo). Essi sono costituiti da un insieme di regole di riscrittura della forma

formula

e da alcune regole di terminazione.

Data una stringa come input, si cerca nell’elenco delle regole, in ordine a partire dalla prima, quella che contiene come pattern una parte dell’input dato. Se essa non viene trovata l’algoritmo termina, altrimenti viene rimpiazzato il pattern trovato più a sinistra nella stringa e la procedura continua. Per esempio, il sistema di regole che segue riscrive un numero naturale n scritto in forma binaria come una sequenza di n barrette verticali.

Regole:

a) | 0 → 0 ||

b) 1 → 0 |

c) 0 →

L’ultima è una regola di terminazione che al simbolo 0 sostituisce il carattere vuoto (qui indicato come assenza di caratteri).

Input:

110 (rappresenta nel sistema binario il numero sei)

Esecuzione (l’applicazione di una delle regole da una stringa a un’altra è indicata con ⇒):

formula

Vedi anche
Markov, Andrej Andreevič, iunior Matematico e logico russo (Pietroburgo 1903 - Mosca 1979), figlio del precedente. Il suo nome è legato agli algoritmi normali o di M., alla computabilità secondo M., che è equivalente alla ricorsività, al principio di normalizzazione o principio di Markov. Questo principio, che corrisponde in termini ... algoritmo Matematica Termine, derivato dall’appellativo al-Khuwārizmī («originario della Corasmia») del matematico Muḥammad ibn Mūsa del 9° sec., che designa qualunque schema o procedimento sistematico di calcolo (per es. l’a. euclideo, delle divisioni successive, l’a. algebrico, insieme delle regole del calcolo ...
Tag
  • NUMERO NATURALE
  • MATEMATICA
Vocabolario
algoritmo
algoritmo (ant. algorismo) s. m. [dal lat. mediev. algorithmus o algorismus, dal nome d’origine, al-Khuwārizmī, del matematico arabo Muḥammad ibn Mūsa del 9° sec. (così chiamato perché nativo di Khwarizm, regione dell’Asia Centrale)]. –...
markoviano
markoviano (o marcoviano; anche marcoffiano) agg. – Relativo al matematico russo A. A. Markov senior (1856-1922): catene m. o processi m., sequenze di eventi aleatorî in cui la probabilità che un particolare evento della catena sia caratterizzato...
  • Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X
  • Ricerca
    • Enciclopedia
    • Vocabolario
    • Sinonimi
    • Biografico
    • Indice Alfabetico

Istituto della Enciclopedia Italiana fondata da Giovanni Treccani S.p.A. © Tutti i diritti riservati

Partita Iva 00892411000

  • facebook
  • twitter
  • youtube
  • instagram
  • Contatti
  • Redazione
  • Termini e Condizioni generali
  • Condizioni di utilizzo dei Servizi
  • Informazioni sui Cookie
  • Trattamento dei dati personali