موضوع مقاله: جمع پیشوندی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # جمع پیشوندی | مقدمه: در علوم کامپیوتر، جمع پیشوندی به آرایه‌ای گفته می‌شود که هر عنصر آن از جمع چند عدد ورودی متوالی به صورت زیر حاصل می‌شود. | ## بخش 1: جمع پیشوندی | +اعداد ورودی۱۵۱۰۳۷۹جمع پیشوندی۱۶۱۶۱۹۲۶۳۵ همچنین می‌توان با درنظرگرفتن , را با استفاده از فرمول بدست آورد. علی‌رغم سادگی در پیاده‌سازی، جمع پیشوندی در الگوریتم‌های خاص همچون مرتب‌سازی شمارشی، در زبان‌های برنامه‌نویسی تابعی در تشکیل پایه‌ای برای اسکن توابع مرتبه بالا و در الگوریتم‌های موازی مورد مطالعه قرار گرفته‌است. زمان صرف‌شده برای محاسبهٔ جمع پیشوندی از مرتبهٔ (O(n می‌باشد، حافظه‌ای که برای ساختن آن صرف می‌شود نیز (O(n می‌باشد اما در جمع پیشوندی موازی می‌توان حافظهٔ استعمال‌شده را به (O(logn کاهش داد. در مرتب‌سازی شمارشی، از جمع پیشوندی برای یافتن جایگاه هر عنصر در آرایه مرتب‌شده، استفاده می‌شود. در رتبه‌بندی لیست‌ها، برای تبدیل یک لیست پیوندی به یک آرایه خروجی، از جمع پیشوندی استفاده می‌شود بدین نحو که یک آرایهٔ ورودی از ۱ها به اندازه طول لیست پیوندی ساخته می‌شود سپس با استفاده از جمع پیشوندی این آرایه، اندیس متناظر برای نگاشتن هر عنصر در لیست پیوندی به آرایه خروجی موردنظر ایجاد می‌شود که نشان‌دهنده موقعیت آن عنصر در آرایه خروجی است. یکی از داده ساختارهای پرکاربرد برای ذخیره‌سازی مجموعه‌ای از اطلاعات که به‌طور پیوسته به‌روزرسانی می‌شود یا به آن اطلاعات جدیدی اضافه می‌شود، درخت فنویک است. درخت فنویک مجموع چند عدد اول یک آرایه، به همراه به‌روزرسانی کردن عناصر آن آرایه را در مرتبه زمانی (O(logn انجام می‌دهد. این درخت برای محاسبهٔ مجموع چند عدد اول یک آرایه به همراه به‌روزرسانی، از جمع پیشوندی استفاده می‌کند. | ## بخش 2: جمع پیشوندی | برای پیاده‌سازی برخی از توابع در یک درخت، مانند ارتفاع و عمق یک گره، از جمع پیشوندی استفاده می‌شود. به عنوان مثال برای محاسبهٔ ارتفاع یک گره، می‌توان با داشتن ارتفاع فرزندهای چپ و راست آن گره و در نظر گرفتن بزرگ‌ترین آنها، ارتفاع آن گره را بدست‌آورد. برای محاسبهٔ عمق یک گره، با داشتن عمق پدر آن گره و جمع آن با یک، می‌توان عمق آن گره را بدست‌آورد. همچنین در پیشوندهای موازی (استفاده از ضرب به عنوان عملیات متداول پایه) می‌تواند برای ساخت الگوریتم‌های سریع برای درون‌یابی چندجمله‌ای موازی استفاده شود. به‌طور خاص، می‌توان از آن برای محاسبهٔ ضرایب تقسیم فرم نیوتن در چندجمله‌ای‌های درون‌یابی استفاده کرد. اسکن توابع مرتبه بالا توابع مرتبه بالا به توابعی گفته می‌شود که یک تابع را به‌عنوان آرگومان می‌گیرند یا خروجی می‌دهند. این توابع درتضاد با توابع مرتبه‌اولی می‌باشند که هیچ تابعی را به‌عنوان آرگومان نمی‌گیرند و تابعی را به‌عنوان خروجی، برنمی‌گردانند. در برنامه‌نویسی تابعی، جمع پیشوندی می‌تواند به عملگرهای دودویی دیگر تعمیم پیدا کند؛ توابع مرتبه بالایی که از این تعمیم حاصل می‌شوند، اسکن نامیده می‌شوند. | ## بخش 3: جمع پیشوندی | منظور از اسکن، دریافت چندین ورودی متوالی و برگرداندن خروجی‌های متوالی حاصل از عملیات دودویی می‌باشد. به عنوان مثال، در جدول زیر، اسکنی از چند عدد طبیعی آورده شده که به‌جای جمع، از تقسیم به عنوان عملگر استفاده شده‌است. +اعداد ورودی۲۵۲۰۵۷۹۸۱تقسیم پیشوندی۲۵۲۰۵۰۴۷۲۸۱۱ جمع پیشوندی موازی مزیتی که جمع پیشوندی موازی نسبت به غیر موازی دارد، حافظه به کارگرفته‌شده می‌باشد. حافظهٔ جمع پیشوندی موازی از مرتبه (O(logn می‌باشد در حالی‌که حافظهٔ به کارگرفته‌شده در حالت غیرموازی از مرتبهٔ (O(n می‌باشد. ساخت جمع پیشوندی موازی ۲ مرحله دارد: مرحله ۱:ساخت یک درخت دودویی در این مرحله، درخت دودویی ساخته می‌شود که هر گرهٔ آن، جمع پیشوندی یک بازه مشخص را در خود نگه می‌دارد. اگر گره‌ای، جمع پیشوندی بازهٔ را در خود نگه دارد، فرزند چپ آن بازهٔ و فرزند راست آن بازهٔ را نگه می‌دارد. همان‌طور که ملاحظه می‌شود برای ساخت این درخت دودویی از الگوریتم تقسیم و حل استفاده می‌شود. فرزند چپ هر گره، مقدار «از چپ» را از پدر خود می‌گیرد، فرزند راست هر گره، مجموعی از مقادیر «از چپ» پدر و جمع پیشوندی بازهٔ ذخیره‌شده در فرزند چپ گره پدر را نگه می‌دارد. | ## جمع‌بندی | در نهایت، خروجی ام آرایهٔ جمع پیشوندی از جمع مقادیر «از چپ» برگ ام با جمع پیشوندی بازهٔ ذخیره‌شده در آن برگ (بازهٔ ) حاصل می‌شود.