مجموعه (نوع داده انتزاعی) کیست؟ توضیح بده.
در علوم رایانه، یک مجموعه یک نوع داده انتزاعی است که می تواند مقادیر یکتایی را بدون هیچ ترتیب خاصی ذخیره کند. در واقع این نوع داده، یک پیاده‌سازی برای مفهوم ریاضی مجموعه‌های متناهی به زبان رایانه است. بر خلاف سایر گردآوردها، به جای این که بخواهیم یک عنصر خاص از مجموعه را به دست آوریم، معمولاً، بررسی می‌کنیم که آیا یک مقدار دلخواه در مجموعه وجود دارد یا خیر.برخی از داده‌ساختارهای موجود برای مجموعه، برای مجموعه‌های ایستا یا frozen طراحی شده‌اند که پس از ساخت، تغییر نمی‌کنند. مجموعه‌های ایستا فقط عملیات پرس‌وجو – مانند بررسی وجود یا عدم وجود مقدار داده شده در مجموعه یا برشمردن مقادیر موجود در مجموعه با ترتیب دلخواه – را روی عناصر خود مجاز می‌دانند. نوع دیگر، مجموعه‌های پویا یا mutable نامیده می شوند که امکان افزودن و حذف عناصر از مجموعه را هم دارند.چندمجموعه یک نوع خاص از مجموعه است که در آن یک عنصر می‌تواند چندین بار ظاهر شود.نظریه نوع.در نظریه‌ٔ نوع‌، مجموعه‌ها به طور کلی با تابع مشخصه‌ی خود مشخص می شوند. بنابراین، مجموعه‌ای از مقادیر از نوع formula_1 می‌تواند با formula_2 یا formula_3 نشان داده شود. (می‌توان زیرگروه‌ها و زیرمجموعه‌ها را با مدل سازی کرد و کلاس‌های هم‌ارزی می‌توان با ها جایگزین کرد.) تابع مشخصه‌ی formula_4 مربوط به مجموعه‌ی formula_5 به این شکل تعریف می‌شود:به صورت نظری، می‌توان بسیاری از داده‌ساختارهای انتزاعی دیگر را به شکل مجموعه‌ای دارای عملیات‌های بیشتر و/یا مجموعه‌ای با اصول موضوعه‌ی اضافی اعمال شده بر عملیات‌های استاندارد، در نظر گرفت. مثلاً، می‌توان یک هرم انتزاعی را به شکل یک مجموعه با عملیات codice_1 که عنصر با کوچک‌ترین مقدار را برمی‌گرداند، تعریف کرد.عملیات‌ها.عملیات‌های اصلی مربوط به نظریه‌ی مجموعه‌ها.می‌توان عملیات‌های جبر مجموعه‌ها را تعریف کرد:مجموعه‌های ایستا.عملیات‌های متداولی که توسط یک ساختار مجموعه‌ای ایستای "S" ارائه می‌شود:مجموعه‌های پویا.ساختارهای مجموعه‌ی پویا، عملیات‌های زیر را نیز دارند:برخی از ساختارهای تنظیم شده ممکن است فقط برخی از این عملیات را مجاز باشند. هزینه هر عملیات به اجرا بستگی دارد و احتمالاً به مقادیر خاص ذخیره شده در مجموعه و ترتیب درج آنها نیز بستگی دارد.عملیات اضافی.بسیاری از عملیات دیگر وجود دارد که (در اصل) می تواند با توجه به موارد فوق تعریف شود ، مانند:سایر عملیات را می توان برای مجموعه هایی با عناصر نوع خاصی تعریف کرد:پیاده سازی ها.مجموعه ها را می توان با استفاده از ساختارهای مختلف داده اجرا کرد ، که مبادلات زمانی و مکانی متفاوتی را برای انجام عملیات مختلف فراهم می کند. برخی از پیاده سازی ها برای بهبود کارایی عملیات بسیار تخصصی مانند codice_45 یا codice_46 . پیاده سازی هایی که به عنوان "استفاده عمومی" توصیف می شوند ، معمولاً تلاش می کنند تا codice_47 ، codice_48 و codice_49 عملیات را بهینه کنند. یک پیاده سازی ساده استفاده از یک لیست ، نادیده گرفتن ترتیب عناصر و مراقبت برای جلوگیری از تکرار مقادیر است. این ساده اما ناکارآمد است ، زیرا عملیاتی مانند عضویت در مجموعه یا حذف عنصر "O" ( "n" ) هستند ، زیرا به اسکن کل لیست نیاز دارند. مجموعه ها اغلب با استفاده از ساختار داده های کارآمد تر ، به ویژه طعم های مختلف درختان ، جدول ها یا جداول هش ، پیاده سازی می شوند.از آنجا که مجموعه ها می توانند به عنوان نوعی نقشه تفسیر شوند (توسط تابع نشانگر) ، مجموعه ها معمولاً به همان روشی که نقشه های (جزئی) ( آرایه های انجمنی ) اجرا می کنند - در این حالت که مقدار هر جفت کلید-مقدار دارای نوع واحد یا مقدار نگهبان (مانند 1) - یعنی یک درخت جستجوی دودویی خود متعادل برای مجموعه های مرتب شده (که برای بیشتر عملیات O (log n) دارد) ، یا یک جدول هش برای مجموعه های مرتب نشده (که دارای O (1) متوسط ، اما O (n) بدترین حالت ، برای اکثر عملیات). یک جدول هش خطی مرتب شده ممکن است برای تهیه مجموعه های مرتب شده قطعی استفاده شود.بعلاوه ، در زبانهایی که از نقشه پشتیبانی می کنند اما مجموعه نیستند ، می توان مجموعه ها را از نظر نقشه پیاده سازی کرد. به عنوان مثال ، اصطلاح رایج برنامه نویسی در Perl که آرایه ای را به هش تبدیل می کند که مقادیر آن مقدار نگهبان 1 است ، برای استفاده به عنوان یک مجموعه ، این است:my %elements = map { $_ =&gt; 1 } @elements;از دیگر روشهای معروف می توان به آرایه ها اشاره کرد . به طور خاص می توان زیرمجموعه ای از عددهای صحیح 1 .. "n" را به عنوان یک آرایه بیتی "n-" bit به طور کارآمد پیاده سازی کرد ، که همچنین از عملکردهای بسیار کارآمد اتحاد و تقاطع پشتیبانی می کند. نقشه بلوم با استفاده از یک نمایش بسیار فشرده اما با احتمال کمی احتمال مثبت کاذب در نمایش داده ها ، یک مجموعه را به صورت احتمالاتی پیاده سازی می کند.عملیات مجموعه بولی را می توان از نظر عملیات ابتدایی تر ( codice_21 ، codice_51 codice_48 و افزودن) پیاده سازی کرد ، اما الگوریتم های تخصصی ممکن است محدوده های زمانی مجانبی کمتری داشته باشند. اگر مجموعه ها به عنوان لیست مرتب شده اجرا شوند ، به عنوان مثال الگوریتم ساده لوح برای codice_53 متناسب با طول "m" "S" "برابر طول n" از "T" طول می کشد. در حالی که یک نوع الگوریتم ادغام لیست کار را در زمان متناسب با "m" + "n انجام می دهد" . علاوه بر این ، ساختارهای داده ای مجموعه ای تخصصی (مانند ساختار داده اتحادیه-پیدا کردن ) وجود دارد که برای یک یا چند مورد از این عملیات و با هزینه دیگران بهینه شده اند.پشتیبانی از زبان.یکی از اولین زبانهایی که از مجموعه پشتیبانی می کند ، زبان پاسکال بود. اکنون بسیاری از زبانها آن را شامل می شوند ، چه در زبان اصلی و چه در یک کتابخانه استاندارد .همانطور که در بخش قبلی اشاره شد ، در زبانهایی که به طور مستقیم از مجموعه پشتیبانی نمی‌کنند اما از آرایه های انجمنی پشتیبانی می کنند ، می توان مجموعه ها را با استفاده از آرایه های تداعی ، با استفاده از عناصر به عنوان کلید و با استفاده از یک مقدار ساختگی به عنوان مقادیر ، که از آنها چشم پوشی می شود ، تقلید کرد.چند مجموعه.چندمجوعه یا خورجین یک تعمیم مفهوم مجموعه است. تفاوت آن با مجموعه این است که اجازه می دهد تا مقادیر مساوی و تکراری داشته باشیم. این است که در دو معنای متمایز استفاده می شود: ارزش هم برابر هستند "یکسان" در نظر "گرفته،" و به سادگی شمارش، و یا مقادیر برابر باشند "معادل" در نظر "گرفته،" و به عنوان کالای مجزا ذخیره می شود. به عنوان مثال ، با توجه به لیستی از افراد (با نام) و سن (در سال) ، می توان چندین گروه از سنین را ایجاد کرد که به سادگی تعداد افراد در یک سن مشخص را محاسبه می کند. متناوباً ، می توان افراد زیادی را ساخت ، جایی که دو نفر در صورتی که سن آنها یکسان باشد معادل در نظر گرفته می شوند (اما ممکن است افراد مختلف باشند و نام های مختلفی داشته باشند) ، در این صورت هر جفت (نام ، سن) باید ذخیره شود و انتخاب در یک سن معین به همه افراد در یک سن داده می شود.به طور رسمی ، این امکان وجود دارد که اشیا in در علوم کامپیوتر تحت برخی معادلات هم ارزی "برابر" قلمداد شوند اما در رابطه دیگری هنوز مشخص باشند. برخی از انواع پیاده سازی چند مجموعه ، اشیا equal مساوی مجزا را به عنوان موارد جداگانه در ساختار داده ذخیره می کنند. در حالی که دیگران آن را به یک نسخه تقسیم می کنند (نسخه اول با آن مواجه می شوند) و تعداد عددی مثبت را از کثرت عنصر حفظ می کنند.همانند مجموعه ها ، چند مجموعه به طور طبیعی می توانند با استفاده از جدول هش یا درختان ، که دارای عملکردهای مختلف هستند ، اجرا شوند.مجموعه همه کیسه ها در بالای نوع T با عبارت T ارائه می شود. اگر توسط چند مجموعه یکی موارد مساوی را یکسان در نظر گرفته و به سادگی آنها را بشمارد ، پس می توان چند مجموعه را به عنوان تابعی از دامنه ورودی به اعداد صحیح غیر منفی تفسیر کرد ( طبیعی اعداد ) ، شناسایی یک مجموعه با عملکرد نشانگر آن را تعمیم می دهد. در بعضی موارد ، یک مجموعه چندگانه به این معنی شمارش ممکن است تعمیم داده شود تا مقادیر منفی مانند پایتون مجاز باشد.در مواردی که ساختار داده ای چند مجموعه ای در دسترس نباشد ، استفاده از یک مجموعه منظم برای رفع اشکال است ، اما عدد مساوی موارد آن را نادیده بگیرید تا همیشه "مساوی" بر روی اشیا objects مجزا برگردد (با این حال ، چنین مواردی هنوز قادر به ذخیره چندین مورد نیستند از همان شی object استفاده کنید) یا از یک آرایه انجمنی استفاده کنید که مقادیر را بر ضرب های عدد صحیح آنها ترسیم کند (این به هیچ وجه نمی‌تواند بین عناصر مساوی تفاوت قائل شود).عملیات معمول روی کیسه ها: