الگوریتم های خط مبنا (Baseline) در پایتون چیست؟

الگوریتم خط مبنای مرتب (Bubble Sort)

الگوریتم خط مبنای مرتب (Bubble Sort) یک الگوریتم مرتب‌سازی ساده است که برای مرتب‌سازی آرایه‌ها و لیست‌ها استفاده می‌شود. در این الگوریتم، اعضای آرایه به صورت مکرر با هم مقایسه می‌شوند و در صورت نیاز جابجا می‌شوند تا به ترتیب صحیحی برسند. الگوریتم خط مبنای مرتب بتدریج اعضای آرایه را به سمت انتهای آرایه حرکت می‌دهد تا کوچکترین عنصر به موقعیت درست خود برسد. نحوه عملکرد الگوریتم خط مبنای مرتب به این صورت است:

1.  شروع از ابتدای آرایه و مقایسه عنصر اول با عنصر دوم. اگر عنصر دوم از عنصر اول کوچکتر بود، آن‌ها را جابجا می‌کنیم.
2.  ادامه مرحله قبل تا جایی که به انتهای آرایه برسیم. در هر مرحله، عنصر بزرگتر به انتهای آرایه می‌رود.
3.  با اتمام یک مرحله، عنصر بزرگتری در انتهای آرایه قرار می‌گیرد. بنابراین، در هر مرحله، تعداد عناصری که نیاز به مقایسه و جابجایی دارند، کاهش می‌یابد.
4.  تکرار مراحل ۱ تا ۳ تا زمانی که تمام عناصر آرایه به ترتیب درست قرار گیرند.

عملکرد الگوریتم خط مبنای مرتب به طور معمول به صورت زمانی O(n^2) است که n تعداد عناصر آرایه است. این حرف بدان معنا است که در صورتی که تعداد عناصر بسیار زیاد باشد، الگوریتم ممکن است زمان زیادی برای مرتب‌سازی نیاز داشته باشد. بنابراین، در مواردی که آرایه‌ها بزرگ و پیچیده‌تر هستند، بهتر است از الگوریتم‌های مرتب‌سازی با زمان اجرای بهتر استفاده کرد.

الگوریتم خط مبنای جستجوی دودویی (Binary Search)

الگوریتم خط مبنای جستجوی دودویی (Binary Search) یک الگوریتم جستجو است که بر روی آرایه‌ها و لیست‌های مرتب شده استفاده می‌شود. این الگوریتم با استفاده از تقسیم و حل، به صورت بازگشتی یک عنصر مورد نظر را در آرایه پیدا می‌کند. عملکرد الگوریتم خط مبنای جستجوی دودویی به این صورت است:

1.  تعیین محدوده جستجو: ابتدا، محدوده جستجو را برای جستجوی عنصر مورد نظر تعیین می‌کنیم. این محدوده معمولاً از ابتدای آرایه (یا لیست) تا انتها است.
2.  محاسبه میانه: میانه محدوده جستجو را محاسبه می‌کنیم. برای آرایه‌های با اندازه فرد، میانه برابر با عدد وسطی است و برای آرایه‌های با اندازه زوج، میانه برابر با اندیس دومین عدد در وسط است.
3.  مقایسه عنصر میانه با عنصر مورد نظر: عنصر میانه را با عنصر مورد نظر مقایسه می‌کنیم. اگر عنصر میانه برابر با عنصر مورد نظر باشد، جستجو پایان می‌یابد و موقعیت عنصر مورد نظر برگردانده می‌شود.
4.  تغییر محدوده جستجو: در صورتی که عنصر میانه بزرگتر از عنصر مورد نظر باشد، محدوده جستجو را به نیمه کوچکتر از محدوده قبلی تقلیل می‌دهیم و جستجو را در آن بخش تکرار می‌کنیم. در غیر این صورت، اگر عنصر میانه کوچکتر از عنصر مورد نظر باشد، محدوده جستجو را به نیمیه بزرگتر از محدوده قبلی تغییر می‌دهیم و جستجو را در آن بخش تکرار می‌کنیم.
5.  تکرار مراحل ۲ تا ۴ تا زمانی که عنصر مورد نظر پیدا شود یا محدوده جستجو تهی شود. در صورتی که محدوده جستجو تهی شود و عنصر مورد نظر پیدا نشود، نشان می‌دهد که عنصر مورد نظر در آرایه وجود ندارد.

عملکرد الگوریتم خط مبنای جستجوی دودویی به صورت معمول به صورت زمانی O(log n) است که n تعداد عناصر آرایه (یا لیست) است. این الگوریتم به دلیل استفاده از تقسیم و حل، به صورت کلی به سرعت عمل می‌کند و برای جستجوی عناصر در آرایه‌ها و لیست‌های بزرگ بسیار مفید است. اما برای استفاده از الگوریتم خط مبنای جستجوی دودویی، آرایه (یا لیست) باید قبل از اجرای الگوریتم به صورت مرتب شده باشد، زیرا این الگوریتم بر اساس میانه‌گیری و مقایسه عناصر استوار است.

الگوریتم خط مبنای رمزنگاری سزار (Caesar Cipher)

الگوریتم خط مبنای رمزنگاری سزار (Caesar Cipher) یکی از ساده‌ترین و محبوب‌ترین روش‌های رمزنگاری تاریخچه است. در این الگوریتم، هر حرف در متن ورودی با یک حرف معین جابه‌جا می‌شود تا متن رمزگذاری شود. نام این الگوریتم برگرفته از نام ژولیوس سزار، فرمانده نظامی رم باستان است که از این روش برای ارتباطات خود استفاده می‌کرد. عملکرد الگوریتم خط مبنای رمزنگاری سزار به این صورت است:

1.  تعیین میزان جابه‌جایی: ابتدا باید تعیین کنید چه تعداد حروف می‌خواهید متن را به سمت راست جابه‌جا کنید. این مقدار را به عنوان کلید (key) الگوریتم می‌توانید انتخاب کنید.
2.  تبدیل حروف: سپس به ترتیب هر حرف موجود در متن ورودی را به تعداد مشخص شده در کلید جابه‌جا کنید. برای مثال، اگر کلید برابر با ۳ باشد، هر حرف در متن ورودی به سه موقعیت به سمت راست منتقل می‌شود. اگر حرف به انتهای الفبا برسد، به ابتدای الفبا منتقل می‌شود تا در حالت دوری الفبا قرار گیرد.
3.  حفظ حروف بزرگ و کوچک: حروف بزرگ و کوچک در الگوریتم خط مبنای رمزنگاری سزار با هم تفاوتی ندارند و به یکدیگر تبدیل می‌شوند. بنابراین، برای رمزگشایی نیز باید همان مقدار جابه‌جایی را به صورت منفی استفاده کنید تا به حالت اولیه برگردید.

برای درک بهتر موضوع به مثال زیر دقت کنید.

فرض کنید می‌خواهید متن "HELLO" را با استفاده از الگوریتم خط مبنای رمزنگاری سزار و با کلید ۳ رمزگذاری کنید. در این صورت، هر حرف به سه موقعیت به سمت راست جابه‌جا می‌شود. بنابراین، "H" به "K" تبدیل می‌شود، "E" به "H"، "L" به "O" و "O" به "R". پس متن رمزگذاری شده برابر با "KHOOR" خواهد بود. الگوریتم خط مبنای رمزنگاری سزار به دلیل سادگی و قابلیت استفاده آسان، برای مواقعی که نیاز به رمزنگاری ساده و سریع دارید، مناسب است. اما این الگوریتم آسیب‌پذیری‌های امنیتی دارد و به راحتی قابل شکستن است. به عنوان مثال، با تلاش و تست تمامی حروف ممکن، می‌توان رمزگشایی را انجام داد. در نتیجه، رمزنگاری سزار به تنهایی برای مواقعی که امنیت بالا الزامی است، مناسب نیست و بهتر است از الگوریتم‌های رمزنگاری قوی‌تر و پیچیده‌تری مانند AES (Advanced Encryption Standard) استفاده کنید.

خط مبنا (Baseline) در یادگیری ماشین

در حوزه یادگیری ماشین، الگوریتم‌های خط مبنا (Baseline Algorithms) نقش مهمی در مقایسه و ارزیابی الگوریتم‌های پیشنهادی و روش‌های جدید دارند. الگوریتم خط مبنا به عنوان یک مدل ساده و پایه برای مقایسه با سایر الگوریتم‌ها و روش‌ها استفاده می‌شود.  استفاده از الگوریتم خط مبنا در یادگیری ماشین دارای مزایا و کاربردهای متعددی به شرح زیر است:

• ارزیابی الگوریتم‌های جدید: الگوریتم خط مبنا می‌تواند به عنوان یک مقیاس مرجع برای ارزیابی الگوریتم‌های جدید و پیشنهادی استفاده شود. با مقایسه عملکرد الگوریتم جدید با الگوریتم خط مبنا، می‌توان نتایج و کارایی الگوریتم جدید را ارزیابی کرد و بهبودهای ممکن را شناسایی کرد.
• مقایسه عملکرد الگوریتم‌ها: با استفاده از الگوریتم خط مبنا، می‌توان عملکرد چندین الگوریتم را با یکدیگر مقایسه کرد. این مقایسه می‌تواند بر اساس معیارهایی مانند دقت، زمان اجرا، مصرف منابع و سایر معیارهای ارزیابی صورت گیرد.
• بررسی کارایی سیستم‌های جدید: در مواردی که یک سیستم یا مدل جدید برای حل یک مسئله خاص پیشنهاد می‌شود، الگوریتم خط مبنا می‌تواند به عنوان یک مدل ساده و سریع برای بررسی کارایی و عملکرد اولیه سیستم جدید استفاده شود.
• تعیین حد پایین (Lower Bound): الگوریتم خط مبنا می‌تواند به عنوان یک حد پایین برای کارایی سایر الگوریتم‌ها استفاده شود. در صورتی که الگوریتم پیشنهادی نتواند کارایی بهتری نسبت به الگوریتم خط مبنا ارائه دهد، نشان می‌دهد که الگوریتم پیشنهادی بهبود کافی نداشته است.

مثال‌هایی از الگوریتم‌های خط مبنا در یادگیری ماشین شامل الگوریتم‌های ساده مانند رگرسیون خطی (Linear Regression)، دسته‌بندی‌کننده نزدیک‌ترین همسایه (K-Nearest Neighbors) و ماشین بردار پشتیبان (Support Vector Machine) هستند. این الگوریتم‌ها به عنوان الگوریتم‌های خط مبنا (Baseline Algorithms) در یادگیری ماشین به عنوان الگوریتم‌های پایه و معیار مقایسه استفاده می‌شوند. آن‌ها معمولا الگوریتم‌های ساده و ابتدایی هستند که برای مقایسه‌ و ارزیابی الگوریتم‌های پیشنهادی و پیچیده‌تر استفاده می‌شوند.

پیاده‌سازی الگوریتم‌های مبنا از پایه با پایتون

الگوریتم‌های مبنا را می‌توان به شکل ساده‌ای در پایتون پیاده‌سازی کرد. در ادامه، نحوه انجام این کار را برای دو الگوریتم مبنای رمزنگاری ساده، یعنی رمز سزار و رمز Vigenere، نشان می‌دهیم.

1. الگوریتم رمز سزار (Caesar Cipher)

def caesar_cipher_encrypt(text, key):

    encrypted_text = ""

    for char in text:

        if char.isalpha():

            if char.isupper():

                encrypted_text += chr((ord(char) - 65 + key) % 26 + 65)

            else:

                encrypted_text += chr((ord(char) - 97 + key) % 26 + 97)

        else:

            encrypted_text += char

    return encrypted_text

def caesar_cipher_decrypt(ciphertext, key):

    decrypted_text = ""

    for char in ciphertext:

        if char.isalpha():

            if char.isupper():

                decrypted_text += chr((ord(char) - 65 - key) % 26 + 65)

            else:

                decrypted_text += chr((ord(char) - 97 - key) % 26 + 97)

        else:

            decrypted_text += char

    return decrypted_text

# مثال استفاده:

plaintext = "HELLO"

key = 3

encrypted_text = caesar_cipher_encrypt(plaintext, key)

print("رمزگذاری شده:", encrypted_text)

decrypted_text = caesar_cipher_decrypt(encrypted_text, key)

print("رمزگشایی شده:", decrypted_text)

2. الگوریتم رمز Vigenere:

def vigenere_cipher_encrypt(plaintext, key):

    encrypted_text = ""

    key_length = len(key)

    for i, char in enumerate(plaintext):

        if char.isalpha():

            if char.isupper():

                key_shift = ord(key[i % key_length].upper()) - 65

                encrypted_text += chr((ord(char) - 65 + key_shift) % 26 + 65)

            else:

                key_shift = ord(key[i % key_length].lower()) - 97

                encrypted_text += chr((ord(char) - 97 + key_shift) % 26 + 97)

        else:

            encrypted_text += char

    return encrypted_text

def vigenere_cipher_decrypt(ciphertext, key):

    decrypted_text = ""

    key_length = len(key)

    for i, char in enumerate(ciphertext):

        if char.isalpha():

            if char.isupper():

                key_shift = ord(key[i % key_length].upper()) - 65

                decrypted_text += chr((ord(char) - 65 - key_shift) % 26 + 65)

            else:

                key_shift = ord(key[i % key_length].lower()) - 97

                decrypted_text += chr((ord(char) - 97 - key_shift) % 26 + 97)

        else:

            decrypted_text += char

    return decrypted_text

# مثال استفاده:

plaintext = "HELLO"

key = "KEY"

encrypted_text = vigenere_cipher_encrypt(plaintext, key)

print("رمزگذاری شده:", encrypted_text)

decrypted_text = vigenere_cipher_decrypt(encrypted_text, key)

print("رمزگشایی شده:", decrypted_text)

در هر دو الگوریتم، تابع caesar_cipher_encrypt و vigenere_cipher_encrypt برای رمزگذاری متن و تابع caesar_cipher_decrypt و vigenere_cipher_decrypt برای رمزگشایی متن استفاده می‌شود. با اجرای کد و استفاده از مقادیر نمونه، می‌توانید رمزگذاری و رمزگشایی را بررسی کنید.

الگوریتم قاعده صفر

الگوریتم قاعده صفر (Zero Rule Algorithm) یک الگوریتم ساده در حوزه یادگیری ماشین است که برای مسائل طبقه‌بندی استفاده می‌شود. این الگوریتم بر اساس تعداد اکثریت برچسب‌ها در داده‌های آموزشی، یک قاعده ساده و قاطع برای پیش‌بینی برچسب نمونه‌های جدید ایجاد می‌کند. عملکرد الگوریتم قاعده صفر به شرح زیر است:

1.  محاسبه تعداد برچسب‌ها: در این مرحله، تعداد نمونه‌های هر برچسب در داده‌های آموزشی را محاسبه می‌کنیم.
2.  انتخاب برچسب اکثریت: برچسبی که در داده‌های آموزشی بیشترین تعداد نمونه را دارد را به عنوان برچسب پیش‌بینی برای تمام نمونه‌های جدید انتخاب می‌کنیم.
3.  پیش‌بینی برچسب: با استفاده از برچسب اکثریتی که در مرحله قبل انتخاب شده است، برچسب نمونه‌های جدید را پیش‌بینی می‌کنیم.

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