موضوع مقاله: الگوریتم دم | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم دم | مقدمه: در تشخیص خطا، الگوریتم دم یک الگوریتم چک کردن رقمی (الگوریتم چکسام) است که تمام خطاهای تک رقمی و تمامی خطاهایی که در انتقال از مجاورت ایجاد می‌شوند را شناسایی و پیدا می‌نماید. | ## بخش 1: الگوریتم دم | نقاط قوت و نقاط ضعف الگوریتم دم نقاط قوت الگوریتم دم شبیه الگوریتم ورهوف است، همچنین تمامی خطاهای رونویسی شامل تغییر یک رقم و جابه جایی دو رقم مجاور را (انتقال عدد چک و اعداد قبل) را شناسایی می‌کند. برتری الگوریتم دم نسبت به الگوریتم ورهوف این است که الگوریتم دم بدون جایگشت‌های اختصاص داده شده عمل می‌کند. علاوه بر این، معکوس جدول را می‌توان با صفر کردن تمام ورودی اصلی مورب جدول ایجاد کرد. الگوریتم دم در اعداد بزرگتر از ۱۰ هم به درستی کار می‌کند و مشکلی ایجاد نمی‌کند ولی در عوض نیازمند یه کارکتر غیر عددی مانند X است (مثل طرح چک کردن رقم در الگوریتم ISBN 10-digit) پیش‌بینی صفرهای پیشین روی رقم چک (چکسام) تأثیر نمی‌گذارد. به‌طور کلی در شبه گروه‌های غیر متقارن تمام خطاهای آوایی مرتبط با زبان انگلیسی (۱۳ , ۳۰) , (۱۴ , ۴۰) , (۱۹ , ۹۰) تشخیص داده می‌شوند، جدول استفاده شده در مثال تصویری نمونه ای از این نوع است. نقاط ضعف با وجود خواص مطلوب الگوریتم دم در زمینه‌های متداول، در بیشتر موارد از الگوریتم‌های مشابه استفاده می‌کنند زیرا الگوریتم دم عمدتاً ناشناخته است و به ندرت در عمل کاربرد دارد. از آنجایی که صفرهای پیشین بر روی رقم چک تأثیر نمی‌گذارند، طول کدها نباید با یکدیگر ادغام گردند. | ## بخش 2: الگوریتم دم | طرح الگوریتم دم بخش ضروری این الگوریتم داشتن یک جدول مربعی ۱۰ در ۱۰ با ویژگی خاص غیر متقارن بودن ( کاملاً غیر متقارن ضعیف) به عنوان بدنهٔ اصلی عملیات است، آقای دم چندین روش را برای ایجاد جدول‌های کاملاً غیر متقارن در پایان‌نامه دکترای خود ارایه کرد همچنین با این کار خود تمام فرضیات قبلی مبنی بر اینکه جدول‌های کاملاً غیر متقارن از مرتبهٔ ۱۰ وجود ندارند را رد نمود. یک شبه گروه (Q, ∗) به‌طور کامل غیر متقارن نامیده می‌شود اگر برای هر x , y که متعلق به Q باشند داشته باشیم: c ∗ x) ∗ y = (c ∗ y) ∗ x ⇒ x = y) x ∗ y = y ∗ x ⇒ x = y اگر فقط جدول از عمل اولی که در بالا ذکر شد پیروی کند غیر متقارن ضعیف نامیده می‌شود. آقای دم ثابت کرد که وجود یک شبه گروه کامل غیر متقارن از مرتبهٔ n با وجود یک شبه گروه کامل غیر متقارن ضعیف از مرتبهٔ n برابر است. برای الگوریتم دم با معادله چک یک شبه گروه کاملاً غیر متقارن ضعیف با ویژگی x ∗ x = ۰ نیاز است. بدین ترتیب یک شبه گروه را می‌توان از هر شبه گروه کاملاً غیر متقارن بوسیله مرتب‌سازی ستون‌ها به طوری که همه صفرها بر قطر قرار گیرند ساخت و همچنین از سوی دیگر از هر کاملاً غیر متقارن ضعیف می‌توان یک کاملاً غیر متقارن ساخت بدین صورت که ستون‌ها را باید طوری مرتب‌سازی کنیم که سطر اول در نظم طبیعی قرار گیرد. الگوریتم اعتبار یک توالی ارقام حاوی یک رقم چک بر یک شبه گروه (جدول ۱۰ * ۱۰) تعریف شده‌است. معتبر کردن یک عدد با شامل شدن رقم چک یک رقم موقت در نظر می‌گیریم و آن را با صفر مقداردهی می‌کنیم. | ## بخش 3: الگوریتم دم | عدد را رقم به رقم پردازش می‌کنیم: رقم عدد را با ستون و رقم موقت را با سطر مطابقت می‌دهیم و عدد مورد نظر را از جدول استخراج می‌کنیم. مثال از جدول زیر برای مثال استفاده می‌کنیم که یک شبه گروه کاملاً غیر متقارن است. +جدول۹۸۷۶۵۴۳۲۱۰۲۴۶۸۹۵۷۱۳۰۰۳۶۸۴۵۱۲۹۰۷۱۹۵۳۱۷۸۶۰۲۴۲۶۲۴۳۸۹۰۵۷۱۳۸۷۹۵۴۰۳۲۱۶۴۱۸۵۹۰۲۴۷۶۳۵۴۳۱۰۲۷۹۶۸۵۶۷۱۰۲۶۳۵۴۹۸۷۵۰۲۷۱۶۸۳۴۹۸۰۹۷۶۳۴۱۸۵۲۹ از ویژگی‌های جدول این است که تمامی عناصر روی قطر اصلی صفر هستند. +محاسبه رقم چک۲۷۵رقم مورد پردازش قرار گرفته - اندیس ستون۷۹۰رقم موقت قبلی - اندیس سطر۴۷۹عنصر بدست آمده از جدول - رقم موقت جدید آخرین رقم بدست آمده ۴ است پس باید به عدد مورد نظر رقم ۴ را اضافه کنیم تا عدد معتبری بدست آید. +معتبر سازی عدد با حساب رقم چک۴۲۷۵رقم مورد پردازش قرار گرفته - اندیس ستون۴۷۹۰رقم موقت قبلی - اندیس سطر۰۴۷۹عنصر بدست آمده از جدول - رقم موقت جدید در این حالت نتیجه بدست آمده برابر با صفر می‌باشد پس نتیجه می‌گیریم که عدد ما معتبر شده‌است. | ## جمع‌بندی | توضیح شکل با استفاده از تصویر وسط|516x516پیکسل در هر مرحله با استفاده از سطر و ستون رقم موقت بعدی را بدست می‌آوریم.