from math import log, ceil from random import random """ Broadcasting in unsure graphs """ # utils mean1 = lambda f, p, k : sum(f(p) for _ in range(k))/k mean2 = lambda f, n, p, k : sum(f(n,p) for _ in range(k))/k mean3 = lambda f, n, m, p, k : sum(f(n,m,p) for _ in range(k))/k # edge geo = lambda p : ceil(log(random(),1-p)) # star star = lambda n, p : max(geo(p) for _ in range(n)) uninformed_star = lambda n, p, k : sum(1 for _ in range(n) if geo(p) > k) mstar = lambda n, m, p : max(path(n,p) for _ in range(m)) # cost of the star H = lambda n : sum(1/i for i in range(1,n+1)) approx1 = lambda n,p : H(n)/log(1/(1-p))+1/2 approx2 = lambda n,p : log(n*1.781072418,1/(1-p))+1/2 # path path = lambda n, p : sum(geo(p) for _ in range(n)) # bi-path bipath = lambda n, m, p : max(path(n,p),path(m,p)) # ring def ring(n,p): nb_draws, nb_informed = 0, 1 while nb_informed < n: if random() <= p: nb_informed += 1 if random() <= p: nb_informed += 1 nb_draws +=1 return nb_draws cost_circle = lambda n,p : n/(2*p) - (2-p)/(4*p)*(1+pow(p/(2-p),n)) # trees tree = lambda d, h, p : max(tree(d,h-1,p)+geo(p) for _ in range(d)) if h != 0 else 0 ## cost import operator as op from functools import reduce def ncr(n, r): r = min(r, n-r) if r == 0: return 1 numer = reduce(op.mul, range(n, n-r, -1)) denom = reduce(op.mul, range(1, r+1)) return numer//denom from math import sqrt bound = lambda n, k, p : n/p * (1+k*sqrt(1-p)*sqrt(n)) + approx(k,p) lbound = lambda n,k,p : approx(k,p)*n ubound = lambda n,k,p : approx(k,p)*ncr(n+1,2) ### General simulation algorithm ### # Généraliser cet algorithme pour qu'il marche pour n'importe quel graphe def grid(n,m,p): def neighbors(i,j): return [(x,y) for (x,y) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)] if 0<=x