Automatische Komplexitätsanalyse funktionaler Programme

ابزارهای زیادی در زمینه مهندسی نرم افزار وجود دارد که از فرآیند توسعه برنامه پشتیبانی می کند. آنها صحت اجرا را تضمین می کنند، اما نه از کارایی آن. بنابراین، کار حاضر روشی را معرفی می کند که امکان تعیین خودکار پیچیدگی زمانی برنامه های کاربردی را فراهم می کند. ایده اصلی این روش ترجمه یک برنامه کاربردی به سیستم معادلات تکراری است که حل آن رفتار زمانی برنامه را مشخص می کند. با معرفی عودهای مشروط و خانواده های عود، می توان کران های بالا و پایین را برای پیچیدگی زمانی پیدا کرد. به منظور تعیین میانگین پیچیدگی زمانی، احتمالات باید برای درست یا نادرست بودن شرایط رخ داده در برنامه محاسبه شود. این احتمالات با استفاده از معناشناسی احتمالی برنامه محاسبه می شوند. برای به دست آوردن دقیق ترین مرزها برای پیچیدگی زمانی، باید یک تحلیل وابستگی انجام شود. این امکان تجزیه و تحلیل دقیق برنامه های Divide and Conquer را فراهم می کند.

Es gibt im Bereich der Softwaretechnik viele Werkzeuge, die den Programmentwicklungsprozeß unterstützen. Sie stellen die Korrektheit der Implementierung sicher, nicht aber ihre Effizienz. Die vorliegende Arbeit führt daher eine Methode ein, die es erlaubt, die Zeitkomplexität funktionaler Programme automatisch zu ermitteln. Die Grundidee dieser Methode besteht darin, ein funktionales Programm in ein System von Rekurrenzgleichungen zu übersetzen, dessen Lösung das Zeitverhalten des Programms angibt. Durch Einführung von bedingten Rekurrenzen und Rekurrenzfamilien ist es möglich, obere und untere Schranken für die Zeitkomplexität zu finden. Um die mittlere Zeitkomplexität zu bestimmen, müssen Wahrscheinlichkeiten dafür berechnet werden, daß im Programm vorkommende Bedingungen wahr bzw. falsch werden. Diese Wahrscheinlichkeiten werden anhand einer probabilistischen Semantik des Programms berechnet. Um möglichst genaue Schranken für die Zeitkomplexität zu erhalten, muß eine Abhängigkeitsanalyse durchgeführt werden. Dies ermöglicht eine genaue Analyse von Divide-and-Conquer-Programmen.