Randomiserade algoritmer används ofta antingen för att hitta effektivt approximerade lösningar på komplexa problem, till exempel primality testing, eller för att få bra genomsnittliga beteende. Bevisande egenskaper hos sådana algoritmer kräver subtilt resonemang både om algoritmiska och probabilistiska aspekter av programmen. Att tillhandahålla verktyg för att mekanisera resonemanget är därför en viktig fråga. Vår uppsats presenterar en ny metod för att bevisa egenskaper hos randomiserade algoritmer i en bevisassistent baserad på högre ordning logik. Den bygger på den monadiska tolkningen av randomiserade program som probabilistisk distribution (Giry, 1982; Ramsey och Pfeffer, 2002). Den kräver inte definition av en operationell semantik för språket eller utveckling av en komplex formalisering av mätteorin, men den använder endast funktionella och algebraiska egenskaper hos enhetsintervallet. Med hjälp av denna modell visar vi giltigheten av allmänna regler för att uppskatta sannolikheten för en randomiserad algoritm för att uppfylla vissa egenskaper. Vårt tillvägagångssätt omfattar endast diskreta fördelningar men ger regler för analys av allmänna rekursiva funktioner. Vi tillämpar denna teori för att formellt bevisa ett program genomföra en Bernoulli distribution från en myntflip och (partiell) avslutande av olika program. Alla teorier och resultat som presenteras i denna uppsats har formaliserats och bevisats i Coq proof assistent (Coq Development Team, 2006).
Andra metoder baserade på interaktiva teorem visare inkluderar arbetet av Audebaud och Paulin-Mohring REF, som axiomatize (diskrete) sannolikhetsteori och verifiera några exempel på randomiserade algoritmer med hjälp av Coq proof assistent.
Proofs of randomized algorithms in Coq
{'venue': 'Sci. Comput. Program.', 'journal': None, 'mag_field_of_study': ['Computer Science']}