آمار

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





زمینه‌های محاسباتی و رایانه‌ای جدیدتری همچون یادگیری ماشینی، و کاوش‌های ماشینی در داده‌ها، در واقع، امتداد و گسترش دانش گسترده و کهن از آمار به عهد محاسبات نو و دوران اعمال شیوه‌های ماشینی در همه‌جا می‌باشد. علم آمار، علم فن فراهم کردن داده‌های کمّی و تحلیل آن‌ها به منظور به دست آورن نتیایجی که اگرچه احتمالی است، اما در خور اعتماد است.


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






علم آمار

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

از جملهٔ مهم‌ترین اهداف آمار، می‌توان تولید «بهترین» اطّلاعات از دادههای موجود و سپس استخراج دانش از آن اطّلاعات را ذکر کرد. به همین سبب است که برخی از منابع، آمار را شاخه‌ای از نظریه تصمیم‌ها به شمار می‌آورند.

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






علم آماری

شامل برنامه‌ریزی و جمع‌بندی و تفسیر مشاهدات غیر قطعی است به‌شکلی که∗:

اعداد نمایندهٔ واقعی مشاهدات بوده، غیر واقعی یا غلط نباشند.
به‌نحو مفیدی تهیه و تنظیم شوند.
به‌نحو صحیح تحلیل شوند.
قابل نتیجه‌گیری صحیح باشند.







روش‌های آماری

مطالعات تجربی و مشاهداتی هدف کلی برای یک پروژه تحقیقی آماری، بررسی حوادث اتفاقی بوده و به ویژه نتیجه گیری روی تأثیر تغییرات در ارزش شاخص‌ها یا متغیرهای غیر وابسته روی یک پاسخ یا متغیر وابسته‌است. دو شیوه اصلی از مطالعات آماری تصادفی وجود دارد: مطالعات تجربی و مطالعات مشاهداتی. در هر دو نوع از این مطالعات، اثر تغییرات در یک متغیر (یا متغیرهای) غیر وابسته روی رفتار متغیرهای وابسته مشاهده می‌شود. اختلاف بین این دو شیوه درچگونگی مطالعه‌ای است که عملاً هدایت می‌شود. یک مطالعه تجربی در بردارنده روش‌های اندازه گیری سیستم تحت مطالعه‌است که سیستم را تغییر می‌دهد و سپس با استفاده از روش مشابه اندازه گیری‌های اضافی انجام می‌دهد تا مشخص سازد که آیا تغییرات انجام شده، مقادیر شاخص‌ها را تغییر می‌دهد یا خیر. در مقابل یک مطالعه نظری، مداخلات تجربی را در بر نمی‌گیرد. در عوض دادهها جمع آوری می‌شوند و روابط بین پیش بینی‌ها و جواب بررسی می‌شوند.

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






احتمالات

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






نرم‌افزارها

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

یکی از مهم‌ترین کاربردهای آمار و احتمال با استفاده از رایانه شبیه سازی است.

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







۱- شبیه سازی فیزیکی و متقابل (شبیه سازی فیزیکی، به شبیه سازی اطلاق می‌شود که در آن اشیای فیزیکی به جای شی واقعی جایگزین می‌شوند و این اجسام فیزیکی اغلب به این خاطر استفاده می‌شوند که کوچک‌تر و ارزان تر از شی یا سیستم حقیقی هستند. شبیه سازی متقابل (تعاملی) که شکل خاصی از شبیه سازی فیزیکی است و غالباً به انسان در شبیه سازی‌های حلقه‌ای اطلاق می‌شود یعنی شبیه سازی‌های فیزیکی که شامل انسان می‌شوند مثل مدل استفاده شده در شبیه ساز پرواز.)







۲- شبیه سازی در آموزش (شبیه سازی اغلب در آموزش پرسنل شهری و نظامی استفاده می‌شود. معمولاً هنگامی رخ می‌دهد که استفاده از تجهیزات در دنیای واقعی از لحاظ هزینه کمرشکن یا بسیار خطرناک است تا بتوان به کارآموزان اجازه استفاده از آن‌ها را داده. در چنین موقعیت‌هایی کارآموزان وقت خود را با آموزش دروس ارزشمند در یک محیط واقعی «ایمن» می‌گذرانند. غالباً این اطمینان وجود دارد تا اجازه خطا را به کارآموزان در طی آموزش داد تا ارزیابی سیستم ایمنی– بحران صورت گیرد.)

شبیه سازی‌های آموزشی به طور خاص در یکی از چهار گروه زیر قرار می‌گیرند:

الف - شبیه سازی زنده (جایی که افراد واقعی از تجهیزات شبیه سازی شده (یا آدمک) در دنیای واقعی استفاده می‌کنند.)

ب - شبیه سازی مجازی (جایی که افراد واقعی از تجهیزات شبیه سازی شده در دنیای شبیه سازی شده (یا محیط واقعی) استفاده می‌کنند.) یا

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

د - شبیه سازی ایفای نقش (جایی که افراد واقعی نقش یک کار واقعی را بازی می‌کنند.)







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







۴ - شبیه سازهای پرواز (یک شبیه ساز پرواز برای آموزش خلبانان روی زمین مورد استفاده قرار می‌گیرد. به خلبان اجازه داده می‌شود تا به هواپیمای شبیه سازی شده اش آسیب برساند بدون آن که خود دچار آسیب شود. شبیه سازهای پرواز اغلب برای آموزش خلبانان استفاه می‌شوند تا هواپیما را در موقعیت‌های بسیار خطرناک مثل زمین نشستن بدون داشتن موتور یا نقص کامل الکتریکی یا هیدرولیکی هدایت کنند. پیشرفته‌ترین شبیه سازها دارای سیستم بصری با کیفیت بالا و سیستم حرکت هیدرولیک هستند. کار با شبیه ساز به طور معمول نسبت به هواپیمای واقعی ارزان تر است.)







۵ - شبیه سازی و بازیها (هم چنین بسیاری از بازی‌های ویدئویی شبیه ساز هستند که به طور ارزان تر آماده سازی شده‌اند. بعضی اوقات از این‌ها به عنوان بازیهای شبیه سازی (sim) نامبرده می‌شود. چنین بازیهایی جنبه‌های گوناگون واقعی را شبیه سازی می‌کنند از اقتصاد گرفته تا وسایل هوانوردی مثل شبیه سازهای پرواز.)







۶ - شبیه سازی مهندسی (شبیه سازی یک مشخصه مهم در سیستم‌های مهندسی است. برای مثال در مهندسی برق، از خطوط تأخیری استفاده می‌شود تا تأخیر تشدید شده و شیفت فاز ناشی از خط انتقال واقعی را شبیه سازی کنند. مشابهاً، از بارهای ظاهری می‌توان برای شبیه سازی مقاومت بدون شبیه سازی تشدید استفاده کرد و از این حالت در مواقعی استفاده می‌شود که تشدید ناخواسته باشد. یک شبیه ساز ممکن است تنها چند تا از کارکردهای واحد را شبیه سازی کند که در مقابل با عملی است که تقلید نامیده می‌شود.






۷ - اغلب شبیه سازی‌های مهندسی مستلزم مدل سازی ریاضی و بررسی‌های کامپیوتری هستند. به هر حال موارد زیادی وجود دارد که مدل سازی ریاضی قابل اعتماد نیست. شبیه سازی مشکلات مکانیک سیالات اغلب مستلزم شبیه سازی‌های ریاضی و فیزیکی است. در این موارد، مدل‌های فیزیکی نیاز به شبیه سازی دینامیک دارند.)







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

به طور رو به افزونی معمول شده‌است که نام انواع مختلفی از شبیه سازی شنیده می‌شود که به عنوان «محیط‌های صناعی» اطلاق می‌شوند. این عنوان اتخاذ شده‌است تا تعریف شبیه سازی عملاً به تمام دستاوردهای حاصل از رایانه تعمیم داده شود.







۹ - شبیه سازی در علم رایانه (در برنامه نویسی کامپیوتری، یک شبیه ساز اغلب برای اجرای برنامه‌ای مورد استفاده قرار می‌گیرد که انجام آن برای رایانه با مقداری دشواری همراه است. برای مثال، شبیه سازها معمولاً برای رفع عیب یک ریزبرنامه استفاده می‌شوند. از آن جایی که کار کامپیوتر شبیه سازی شده‌است، تمام اطلاعات در مورد کار رایانه مستقیماً در دسترس برنامه دهنده‌است و سرعت و اجرای شبیه سازی را می‌توان تغییر داد. همچنین شبیه سازها برای تفسیر درخت‌های عیب یا تست کردن طراحی‌های منطقی VLSI قبل از ساخت مورد استفاده قرار می‌گیرند. در علم رایانه نظریه، عبارت شبیه سازی نشان دهنده یک رابطه بین سیستم‌های انتقال وضعیت است که این در مطالعه مفاهیم اجرایی سودمند است.)







۱۰ - شبیه سازی در تعلیم و تربیت (شبیه سازی‌ها در تعلیم و تربیت گاهی مثل شبیه سازی‌های آموزشی هستند. آن‌ها روی وظایف خاص متمرکز می‌شوند. در گذشته از ویدئو برای معلمین و دانش آموزان استفاده می‌شود تا مشاهده کنند، مسائل را حل کنند و نقش بازی کنند؛ هرچند، یک استفاده جدید تر از شبیه سازی‌ها در تعلیم و تربیت شامل فیلم‌های انیمیشن است (ANV.(ANVها نوعی فیلم ویدئویی کارتون مانند با داستان‌های تخیلی یا واقعی هستند که برای آموزش و یادگیری کلاس استفاده می‌شوند.ANVها برای ارزیابی آگاهی، مهارت‌های حل مسئله و نظم بچه‌ها و معلمین قبل و حین اشتغال کارایی دارند.)

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







واژگانی که درک مفهوم آن‌ها در علم آمار مهم است عبارت‌اند از∗:

جمعیت
نمونه
متغیّر
مقیاس‌های اندازه‌گیری:
مقیاس اسمی (به انگلیسی: Nominal Scale)
مقیاس ترتیبی (به انگلیسی: Ordinal Scale)
مقیاس فاصله‌ای (به انگلیسی: Interval Scales)
مقیاس نسبی (به انگلیسی: Ratio Scales)

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

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

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

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







مراحل پایه برای انجام یک تجربه عبارت‌اند از:

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






سطوح اندازه گیری

چهار نوع اندازه گیری یا مقیاس اندازه گیری در آمار استفاده می‌شود. چهار نوع یا سطح اندازه گیری (ترتیبی، اسمی، بازه‌ای و نسبی) دارای درجات متفاوتی از سودمندی در بررسی‌های آماری دارند. اندازه گیری نسبی در حالی که هم یک مقدار صفر و فاصله بین اندازه‌های متفاوت تعریف می‌شود بیشترین انعطاف پذیری را در بین روش‌های آماری دارد که می‌تواند برای تحلیل داده‌ها استفاده شود. مقیاس تناوبی با داشتن فواصل معنی دار بین اندازه‌ها اما بدون داشتن میزان صفر معنی دار (مثل اندازه‌گیری بهره هوشی یا اندازه‌گیری دما در مقیاس سلسیوس) در تحقیقات آماری استفاده می‌شود. صفت آماری - هر ویژگی مربوط به هر واحد جامعه را یک صفت آماری یا به اختصار یک صفت برای آن واحد آماری است. اگر یک واحد آماری یک انسان باشد، گروه خون، وزن، میزان سواد، میزان درآمد، درجه حرارت بدن و تعدادخانوار هر کدام یک صفت آماری برای آن واحد است. صفتهای آماری دو دسته کلی هستند. ۱- صفت مشخصه ۲ صفت متغیر





میانه‌ها و شاخص‌های آماری
میانه‌ها وشاخص‌های آماری ترتیبی

iامین شاخص آمار ترتیبی یک مجموعه n عضوی، iامین عضو کوچک است. به عنوان مثال، مینیمم یک مجموعه از اعضا، اولین شاخص آمار ترتیبی (i=۱)است و ماکزیمم، nامین شاخص آمار ترتیبی (i=n)است. میانه، به طور غیر رسمی، نقطهٔ میانی مجموعه‌است. هنگامی که n فرد است، میانه منحصر به فرد است که در i=(n+۱)/۲ رخ می‌دهد. وقتی n زوج است، دو میانه وجود دارند که در i=n/۲ و i=n/۲+۱ رخ می‌دهند. انتخاب iامین شاخص آمار ترتیبی از یک مجموعه با n عضو مجزا را بیان می‌کند. مسئله انتخاب می‌تواند به طور رسمی به شکل زیر تعیین شود: ورودی: مجموعه A با n عدد(مجزا) و عدد i، که i بزرگتر یا مساوی ۱ و کوچکتر یا مساوی با n است. خروجی: عضو x در A که بزرگتر از دقیقا i-۱ عضو دیگر A می‌باشد. مسئله انتخاب می‌تواند در زمان (O(nlgn حل شود، چون می‌توانیم اعداد را با استفاده از مرتب سازی دودویی (heap sort) یا مرتب سازی ادغام مرتب کنیم و سپس به سادگی iامین عنصر در آرایه خروجی را مشخص کنیم اما الگوریتم‌های سریع تری وجود دارند. ابتدا مسئله انتخاب مینمم و ماکزیمم یک مجموعه از اعضا را بررسی می‌کنیم. مسئله جالب تر، مسئله انتخاب کلی است، که دردوقسمت بررسی می‌شود.قسمت اول یک الگوریتم عملی را تحلیل می‌کند که در حالت میانگین به زمان اجرای (O(n می‌رسد. قسمت بعد یک الگوریتم است که جنبه‌های نظری بیشتری داشته و در بدترین حالت به زمان اجرای (O(n می‌رسد.






مینیمم و ماکزیمم

چه تعداد مقایسه برای تعیین یک مجموعه n عضوی لازم است؟ می‌توانیم به سادگی به حد بالای n-۱ برای مقایسه‌ها برسیم: هر عضو مجموعه را به ترتیب بررسی کرده و کوچکترین عضوی که تا کنون دیده شده‌است را نگه می‌داریم. در روال زیر، فرض می‌کنیم مجموعه در آرایه A قرار دارد، که طول آرایه n است. قطعا یافتن ماکزیمم می‌تواند با n-۱ مقایسه نیز انجام شود. آیا این بهترین کاری است که می‌توانیم انجام دهیم؟ بله، چون می‌توانیم به حد پایین n-۱ برا مقایسه‌ها برای مینممم برسیم. الگوریتم را در نظر بگیرید که مینیمم را به صورت مسابقه‌ای بین عناصر تعیین می‌کند. هر مقایسه یک بازی در مسابقه‌است که در آن عنصر کوچکتر از میان دو عنصر، برنده می‌شود. نگرش اصلی این است که هر عنصر به جز برنده باید حداقل یک بازی را ببازد. از این رو n-۱ مقایسه برای تعیین مینیمم لازم است.






مینیمم و ماکزیمم هم زمان

در برخی کاربردها، باید هم مینیمم و هم ماکزیمم یک مجموعه از n عضو را پیدا کنیم. ارائه الگوریتمی که بتواند هم مینیمم و هم ماکزیمم n عضو را با استفاده از (θ(nمقایسه، که به طور مجانبی بهینه‌است، پیدا کند سخت نیست. به سادگی مینیمم و ماکزیمم را به طور مستقل، با استفاده از n-۱ مقایسه برای هر یک پیدا می‌کند، که در کل ۲n-۲ مقایسه انجام می‌دهد. در حقیقت، حداکثر ۳n/۲ مقایسه برای پیدا کردن مینیمم و ماکزیمم کافی است. استراتژی این است که اعضای مینیمم و ماکزیمم را که تا این جا دیده شده‌اند نگه داریم. به جای این که هر عضو ورودی را با مقایسه با مینیمم و ماکزیمم فعلی پردازش کنیم، که هزینه ۲ مقایسه برای هر عضو را صرف می‌کند، اعضا را جفت به جفت مقایسه می‌کنیم. ابتدا جفت عضوها را از ورودی با یکدیگر مقایسه می‌کنیم و سپس عضو کوچکتر را با مینیمم جاری و عضو بزرگتر را با ماکزیمم جاری مقایسه می‌کنیم که هزینه ۳ مقایسه برای هر دو عضو را موجب می‌شود.






انتخاب در زمان خطی مورد انتظار

مسئله انتخاب کلی نسبت به مسئله پیدا کردن یک مینیمم سخت تر به نظر می‌آیدو هم چنان که به صورت شگفت آوری زمان اجرای مجانبی هر دو مسئله یکی است: (θ(n.در این بخش یک الگوریتم تقسیم و حل را برای مسئله انتخاب ارائه می دهیم. الگوریتم Randomized-Select بعد از الگوریتم مرتب سازی سریع مدل می‌شود. همانند مرتب سازی سریع ایده آن است که آرایه ورودی را به طور بازگشتی تقسیم کنیم. ولی برخلاف مرتب سازی سریع که هر دو طرف تقسیم بندی را به صورت بازگشتی پردازش می‌کند، Randomized-Select فقط روی یک طرف تقسیم بندی عمل می‌کند. این تفاوت در تحلیل آشکار می‌شود. در حالی که زمان اجرای مورد انتظار مرتب سازی سریع (θ(nlgn است، زمان مورد انتظار این الگوریتم (θ(nاست. Randomized-Select از روال Randomized-Partition که در بخش مرتب سازی سریع معرفی شد استفاده می‌کند.

این الگوریتم iامین عنصر کوچک آرایه Ap..r را برمی گرداند. بعد از این که Randomized-Partition در خط 3 الگوریتم اجرا می‌شود، آرایهAp..r به دو زیر آرایه (شاید خالی)Ap..q-1و Aq+1..rتقسیم می‌شود. به طوری که هر عنصرAp..q-1 کوچک تر یا مساوی با Aqاست که Aqنیز به نوبهٔ خود کوچک تر از هر عنصری ازAq+1..r می‌باشد. همانند مرتب سازی سریع، به Aq به عنوان عنصر محوری(pivot)اشاره می کنیم. خط 4 از Randomized-Select تعداد k عناصر در زیر آرایه Ap..q-1را محاسبه می‌کند، به عبارت دیگر تعداد عناصر در طرف کم تر تقسیم بندی، به علاوه 1 برای عنصر محوری. سپس خط 5 چک می‌کندکه آیi Aq امین عنصر کوچک هست یا نه.اگر باشد آن گاهAq برگردانده می‌شود. در غیر این صورت، الگوریتم تعیین می‌کند که iامین عنصر کوچک در کدام یک از دو زیر آریه قرار دارد. زمان اجرای Randomized-Select در بدترین حالت (θ(n^2است. اگر چه الگوریتم به خوبی در حالت میانگین کار می‌کند و چون تصادفی است، هیچ ورودی خاصی باعث رفتار بدترین حالت نمی‌شود.






انتخاب در بدترین حالت زمان خطی

اکنون الگوریتمی را بررسی می کنیم که زمان اجرای آن در بدترین حالت (O(nاست. مانند Randomized-Select، الگوریتم Select عنصر مورد نظر را با تقسیم بندی بازگشتی آرایه ورودی پیدا می‌کند. اما ایده‌ای که پشت این الگوریتم وجود دارد، این است که یک قسمت خوب را در هنگامی که آرایه تقسیم می‌شود تضمین می‌کند. Select از الگوریتم تقسیم بندی قطعی Partition مربوط به مرتب سازی سریع استفاده می‌کند که طوری تغییر یافته است که عنصری که تقسیم بندی حول آن انجام می‌شود را به عنوان پارامتر ورودی بگیرد. این الگوریتم iامین عنصر کوچک از آرایه ورودی با n>1 عنصر را با اجرای مراحل زیر تعیین می‌کند.(اگر n=1باشد آن گاه Select به طور مطلق، تنها ورودیش را به عنوان iامین عنصر کوچک برمی گرداند.)

n عنصرآرایه ورودی را بهn/5 گروه 5 عنصری تقسیم کنید و حداکثر یک گروه از n mod 5 عنصر باقیمانده ساخته می‌شود.
میانه هر یک از n/5گروه را ابتدا با مرتب ساز درجی عناصر هر گروه (که حداکثر 5 عنصر در هر یک وجود دارد)و سپس انتخاب میانه از لیست مرتب شده عناصر گروه پیدا کنید.
از Select به صورت بازگشتی برای پیدا کردن میانه x از n/5میانه‌ای که در مرحله 2 پیدا شدند استفاده کنید.
آرایه ورودی را حول میانهٔ میانه‌ها (یعنی x)با استفاده از نسخه تغییر یافته Partition تقسیم کنید. فرض کنید k یک واحد بیشتر از تعداد عناصر در طرف کم تر تقسیم بندی باشد، بنابراین k، x امین عنصر کوچک است و n-k عنصر در طرف بیشتر تقسیم بندی موجود است.
اگر i=k باشد، x را برگردانید در غیر این صورت اگر i<k باشد از Select به صورت بازگشتی برای پیدا کردن iامین عنصر کوچک در طرف کم تر استفاده کرده یا اگر i>k باشد، از آن برای پیدا کردن (i-k)امین عنصر کوچک در طرف بیشتر استفاده کنید.

برای تحلیل زمان اجرای Select، ابتدا یک حد پایین روی تعداد عناصر بزرگتر از عنصر تقسیم کنندهٔ x تعیین می کنیم. حداقل نصفی از میانه‌های پیدا شده در مرحله 2 بزرگتر از x یعنی میانهٔ میانه‌ها هستند. بنابراین در حداقل نصف n/5گروه، 3 عنصر وجود دارند که از x بزرگترند، به جز برای گروهی که اگر5 به n قابل قسمت نباشد، کم تر از 5 عنصر دارد و گروهی که خود شامل x است. با منظور نکردن این دو گروه ثابت می‌شود که تعداد عناصر بزرگتر از x حداقل برابر است با

3(2-1/2n/5)

که این عبارت بزرگتر یا مساوی با 3n/10-6 است. به طور مشابه عناصری که کوچک تر از x هستند حداقل 3n/10-6 است. بنابراین در بدترین حالت، Select برای حداکثر 7n/10+6 عنصر در مرحلهٔ 5 به طور بازگشتی فراخوانی می‌شود.






آزمون فرض آماری

آزمون فرض آماری (به انگلیسی: Statistical hypothesis testing) در علم آمار روشی است برای بررسی ادعاها یا فرض‌ها دربارهٔ پارامترهای توزیع در جوامع آماری. در این روش فرض صفر (به انگلیسی: Null-hypothesis) یا فرض اولیه مورد بررسی ست که متناسب با موضوع مطالعه فرضی به عنوان فرض بدیل یا فرض مقابل (به انگلیسی: Alternative-hypothesis) انتخاب می‌شود تا درستی هر کدام نسبت به هم مورد آزمون قرار گیرد.






آمار پارامتری

آمار پارامتری به مجموعه روش‌های آماری‌ای گفته می‌شود که مدل‌ای پارامتری برای پدیدهٔ احتمالی مورد مطالعه فرض می‌شود و همهٔ استنتاج‌های آماری از آن پس بر اساس آن مدل انجام می‌شود.

به عنوان مثال فرض می‌شود که توزیع نمره‌های یک امتحان از توزیع نرمال پیروی می‌کند. در نتیجه برای مشخص‌شدن توزیع احتمال، کافی است میانگین و واریانس توزیع را از روی داده‌های تجربی (نمره‌های دانش‌آموزان) به دست بیاوریم. حال برای پاسخ‌گفتن به سوال‌هایی چون «درصد دانش‌آموزانی که نمره‌ای بین ۱۰ تا ۱۵ آورده‌اند» از تابع توزیع به دست آمده استفاده می‌کنیم (البته بدیهی است که روش‌های ساده‌تری نیز برای چنین کاری وجود دارد).

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






آماره

آماره در آمار به عددی گویند که یک توزیع نمونه‌برداری را خلاصه‌سازی یا توصیف می‌کند.

تابع U=g(X۱, X۲, …, Xn)‎ از نمونهٔ تصادفی X۱, X۲, …, Xn را که در آن پارامتر مجهولی وجود نداشته باشد یک آماره می‌گویند. در این تعریف U یک متغیر تصادفی است که توزیع آن ممکن است به پارامتر بستگی نداشته باشد؛ اما تنها آماره‌هایی برای برآورد کردن مفید هستند که توزیعشان به پارامتر مجهول بستگی داشته باشد و اطلاعاتی در مورد این پارامتر به ما بدهند.






آنتروپی آماری
انتروپی آماری یک کمیت ترمودینامیکی است که در شیمی‌فیزیک کاربردهای فراوان دارد.






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





چولگی

در آمار و نظریه احتمالات چولگی نشان دهنده میزان عدم تقارن توزیع احتمالی است. اگر داده‌ها نسبت به میانگین متقارن باشند، چولگی برابر صفر خواهد بود.






تعریف

چولگی برابر با گشتاور سوم نرمال شده است. چولگی در حقیقت معیاری از وجود یا عدم تقارن تابع توزیع می باشد. برای یک توزیع کاملاً متقارن چولگی صفر و برای یک توزیع نامتقارن با کشیدگی به سمت مقادیر بالاتر چولگی مثبت و برای توزیع نامتقارن با کشیدگی به سمت مقادیر کوچکتر مقدار چولگی منفی است.






داده

به طور کلی، می‌توان همهٔ دانسته‌ها، آگاهی‌ها، داشته‌ها، آمارها، شناسه‌ها، پیشینه‌ها و پنداشته‌ها را داده یا دیتا (به انگلیسی: Data) نامید. انسان برای ثبت و درک مشترک هر واقعیت و پدیده از نشانه‌های ویژهٔ آن بهره گرفته‌است.

انسان برای نمایاندن داده‌ها نخست از نگاره و در ادامهٔ سیر تکاملی آن از حروف، شماره‌ها و نشانه‌ها کمک گرفت. برای بازنمودن داده‌ها از این موارد کمکی یا ترکیبی از آن‌ها استفاده می‌شود






در رایانه

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

داده‌ها مجموعه‌ای از نمادها (برای انسان حروف، اعداد، علائم و برای رایانه رمزهای صفر و یک) هستند که حقایق را نشان می‌دهند و برای انسان از طریق رسانه‌های وی (بینایی، شنوایی، چشایی، بویایی، بساوایی) و برای رایانه از طریق لوازم ویژه (صفحه کلید موس و غیره) به دست می‌آیند.

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






انواع داده‌ها از نظر ساخت‌یافتگی

داده‌های ساخت‌یافته
داده‌های نیمه‌ساخت‌یافته







داده‌های زمانی
در بسیاری از کاربردهای مبتنی بر داده‌ها و اطلاعات ذخیره‌سازی و بازیافت حالا ت و وضعیت‌های سیستم در طی زمان اهمیت می‌یابد.





داده‌های مکانی
داده‌های مکانی (geospatial data ) به مجموعه‌ای از داده‌ها گفته می‌شود که بیان کننده موقعیت جغرافیایی یک عارضه(طبیعی یا مصنوعی) بر روی زمین باشند. داده‌های مکانی معمولاً به صورت موقعیت و یا روابط هندسی ذخیره شده و قابل نمایش در نقشه‌ها می‌باشند. داده‌ها مکانی بیشتر در سامانه‌های اطلاعات مکانی نگهداری شده، قابل دسترسی و پردازش می‌باشند.





پردازش رایانه‌ای داده‌ها

پردازش رایانه‌ای داده‌ها هر فرایندی است که از برنامه‌ای رایانه‌ای برای واردسازی داده‌ها، خلاصه‌بندی، تحلیل و در غیر اینصورت تبدیل‌داده به اطلاعات قابل استفاده استفاده می‌کند.

علوم و فناوری پردازش داده‌ها دارای وسعت، گوناگونی، و پیچیدگی فراوانی بوده، و این زمینه از دانش به شاخه‌ها و زیر شاخه‌های متعددی تقسیم می‌شود، که برخی از آن‌ها عبارت است از:






پردازش علائم

پردازش علائم (سیگنال‌ها) را باید یکی از شاخه‌های وسیع و پر کاربرد در پردازش داده‌ها به حساب آورد.
8:50 am
کاربرد الگوریتم‌ها

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






- پزشکی و ژنتیک:

یکی از کاربردهای مهم الگوریتم‌ها در ژنتیک و در پروژه ژن‌های انسانی است. هدف پروژه ژن انسان، شناسایی تمام ۱۰۰۰۰۰ ژن در DNA انسان، تعیین دنباله‌ای از ۳ بیلیون جفت پایه شیمیایی DNA انسان، ذخیره این اطلاعات در پایگاه داده‌ها و تولید ابزارهایی برای تحلیل داده‌ها است که هر یک از این مراحل نیازمند الگوریتم‌هایی حرفه‌ای است و این خود تصدیقی بر اهمیت الگوریتم‌ها در پیشرفتهای پزشکی و ژنتیکی است. -

-اینترنت:

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

- تجارت الکترونیک:

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

- صنعت:

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

- مسیر یابی:

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

- مرتب سازی:

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

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





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




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



الگوریتم‌های کمینه/بیشینه خطی
الگوریتم‌های خطی، از لحاظ زمانی، برای پیدا کردن کمینه‌ها یا بیشینه‌ها این گونه کار می‌کنند که روی لیست تکرار می‌کنند و رد کمینه یا بیشینه تا هر بار نگه می‌دارند.



الگوریتم کلی انتخاب غیر خطی
با کمک ایده‌های مورد استفاده در الگوریتم‌های کمینه/بیشینه، ما می‌توانیم یک الگوریتم کلی ساده، ولی ناکارامد برای پیدا کردن کوچک‌ترین kامین یا بزرگ‌ترین k عنصر در یک لیست بدهیم، که نیاز به زمان O(k) دارد، که وقتی k کوچک باشد مؤثر است. برای انجام دادن آن، ما به سادگی کوچک‌ترین/بزرگ‌ترین مقدار را می‌یابیم و آن را به ابتدای بازه حرکت می‌دهیم تا به اندیس دلخواه برسیم. این کار را می‌توانیم به عنوان یک مرتب سازی انتخابی ناتمام ببینیم.





الگوریتم کلی انتخاب به صورت خطی - الگوریتم میانه‌ی میانه‌ها

یک الگوریتم با بدترین زمان اجرای خطی برای حالت کلی انتخاب kامین بزرگ‌ترین عنصر توسط بلوم، فلوید، پرت، ریوست و ترجان در مقاله سال ۱۹۳۷ با نام «حدود زمانی برای انتخاب» منتشر شد. گاهی از این الگوریتم با نام BFPRT، که حروف اول نام خانوادگی نویسندگان آن است، یاد می‌شود. این الگوریتم بر اساس الگوریتم انتخاب سریع کار می‌کند و هم‌چنین به نام الگوریتم میانه‌ی میانه‌ها شناخته می‌شود.

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

الگوریتم انتخاب لیست را به گروه‌هایی شامل پنج عنصر تقسیم می‌کند.(فعلاً با عناصر باقی‌مانده کاری نداریم). سپس، برای هر گروه پنج‌تایی، میانه محاسبه می‌شود (اگر آن پنج مقدار داخل ثبّات‌ها بارگذاری شوند و مقایسه شوند، عملیات به طور بالقوه بسیار سریع انجام می‌شود). (اگر مرتب‌سازی به صورت درجا صورت گیرد، این میانه‌ها به یک بلوک پیوسته در لیست منتقل می‌شوند.) انتخاب به صورت بازگشتی در این زیرلیست‌های n/5 عنصری فراخوانده می‌شود تا مقدار واقعی میانه یافت شود. سرانجام، میانه‌ی میانه‌ها به عنوان محور انتخاب می‌شود.





ویژگی‌های محور
محور انتخاب شده، از نیمی از عناصر لیست میانه‌ها بزرگ‌تر و از نیمه‌ی دیگر کوچک‌تر است، به طوری که در هر نیمه n/10 عنصر (1/2 * (n/5)) قرار دارند. هر کدام از این عناصر، میانه‌ی ۵ عنصر است و از ۲ عنصر کوچک‌تر و از ۲ عنصر در خارج از بلوک بزرگ‌تر است. پس، محور کوچک‌تر از 3(n/10) عناصر خارج از بلوک است، و از 3(n/10) عنصر دیگر خارج از بلوک بزرگ‌تر است. بنا بر این، میانه‌ی انتخاب شده، عناصر را به مکانی بین 30%/70% و 70%/30% تقسیم می‌کند. این کار به ما اطمینان می‌دهد که رفتار الگوریتم در بدترین حالت خطی است.



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




تحلیل الگوریتم‌ها

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

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

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

اغلب مهم است که بدانید برای چه مقدار از یک منبع خاص (مثل زمان یا حافظه) تئوری مورد نیاز برای یک الگوریتم داده شده. روش‌ها برای تجزیه و تحلیل الگوریتم‌های توسعه یافته برای به دست آوردن مقادیر کمی (تخمین)؛به عنوان مثال، الگوریتم مرتب سازی در بالای یک زمان مورد نیاز از (O(N، با استفاده از نماد گذاری O بزرگ با n به عنوان طول لیست در تمام زمانها در الگوریتم باید دو مقدار را به خاطر داشته باشید: بیشترین تعداد تا کنون و موقعیت فعلی در لیست ورودی. لذا گفته شده است که فضای مورد نیاز از (۱)O است در صورتی که برای ذخیره، شماره‌های ورودی شمارش نمی‌شود یا (O(n آن شمارش شده.
ساعت : 8:50 am | نویسنده : admin | مطلب قبلی | مطلب بعدی
الگوریتم | next page | next page