- Questo topic ha 0 risposte, 1 partecipante ed è stato aggiornato l'ultima volta 10 anni, 9 mesi fa da .
-
Topic
-
Non riesco ad ottimizzare la visualizzazione grafica di questa porzione di testo contenente formule matematiche semplici, ma non chiare al lettore:`
\documentclass[11pt,a4paper,oneside]{book}\usepackage[utf8]{inputenc}
\usepackage[italian]{babel}\usepackage{layaureo}
\usepackage{graphicx}\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}\usepackage[usenames,dvipsnames]{xcolor}
\usepackage[colorlinks=true,urlcolor=blue,citecolor=ForestGreen,linkcolor=blue]{hyperref}\date{}
\usepackage{listings}
\begin{document}
Valutiamo il numero di messaggi richiesti dall'algoritmo: nella generica fase \textit{h}, la lunghezza della catena attraversata da un messaggio di candidatura è $ 2^h $. Per $ h > 0 $ un processo lancia la sua candidatura su una catena di lunghezza raddoppiata (pari a $ 2 * 2^{h-1} $ solo se non è stato sconfitto nella consultazione precedente da un processo che dista da lui al più $ 2^{h-1} $ in qualsiasi delle due direzioni dell'anello. Ciò implica che, in un arbitrario gruppo di $ 2^{h-1} + 1 $ processi consecutivi, al più un solo processo può lanciare la propria candidatura nella fase \textit{h}. Nel caso pessimo, nella fase \textit{h}, ci sono al più $ \llcorner \frac{n}{(2^{h-1} + 1)} \lrcorner $ candidati con catene di lunghezza $ 2^h $. Per ogni candidato ci sono 2 messaggi (candidatura e risposta) in ogni direzione, per un totale di 4 messaggi lungo le catene di lunghezza appropriata. Il numero totale di messaggi della fase \textit{h} è limitato da $ 4 \times 2^h \times \llcorner \frac{n}{(2^{h-1} + 1)} \lrcorner \leq 8n $. Ma il numero totale di fasi che sono eseguite prima che vengo eletto il leader è $ 1 + \ulcorner log n \urcorner $ e, quindi, il numero è di messaggi è O (n log n).
\end{document}
`
- Devi essere connesso per rispondere a questo topic.