فصل ۸ − Set Types
➡ فهرست
نوعِ Set ساختارِ فشرده و جمع و جوری برای نگهداری از یک مجموعه مقادیر که همگی از یک نوع ordinal یکسان هستند، فراهم میکند. به صورت دقیقتر، یک set type مجموعهای از مقادیر را تعریف میکند که برابر با مجموعهی توانی (powerset) نوع پایهی آن است؛ یعنی مجموعهی همهی زیرمجموعههای ممکن از مقادیر نوع پایه، از جمله مجموعهی تهی. بنابراین یک مقدار از نوع Set، خودش یک set است و عناصر آن set یا مجموعه، مقادیری از نوع پایه هستند.
⚪ یک مجموعه با n عضو 2n زیرمجموعه دارد.
💡 set ها ساختاری با دسترسی تصادفی هستند که تمام عناصر آن از یک نوع پایهاند که آن نوع پایه هم باید ordinal باشد.
سعی کنید مفاهیم گفته شده در بالا را در مثال زیر پیدا کنید:
TYPE
Digit = 0..9;
Digits = SET OF Digit; { Set type with base type Digit }
VAR
D: Digits; { Variablie of type "set" }
{---------------------------------------------------------------
[1, 2, 3] a set value
----------------------------------------------------------------}
سینتکس دیاگرام set type به صورت زیر است:
عملیات صحیح بر روی set value ها عبارتند از انتساب، کارهای رایج روی مجموعهها مثل union یا اجتماع، بررسی برابری دو مجموعه، و انتخاب عناصر بر اساس آزمون عضویت یا membership.
set value ها میتوانند از روی مقادیر مجموعه و با استفاده از set constructor ساخته شوند. پیادهسازیهای پاسکال معمولا بر روی اندازهی مجموعه محدودیت میگذارند که میتواند خیلی کوچک باشد (به عنوان مثال به اندازهی تعداد بیتهای یک کلمهی ماشین) این محدودیت مستقیما بر روی base type نوع مجموعه اعمال میشود.
set constructors
یک set value میتواند توسط یک set constructor که حاوی
توصیف عناصر مجموعه است مشخص شود. این عنصرها با , از هم جدا شده
و بین square bracket ها [] محصور شدهاند. توصیف یک عنصر میتواند
به صورت یک expression باشد که مقدار آن نمایانگر عنصر مجموعه است و یا یک
range به صورت Low..High، که مقادیر expression های Low و High حد پایین و حد بالای
یک اجتماع یا collection از عناصر را مشخص میکنند.
اگر حد پایین از حد بالای range بزرگتر باشد (Low > High) در این صورت
هیچ عنصری از اجتماع یاد شده توصیف نمیشود و چیزی در set قرار نمیگیرد.
تمام expression ها باید از همان نوع ordinal ای باشند که base type مجموعه یا set
از آن نوع است. set constructor به صورت [] بیانگر مجموعهای خالی
از هر نوع set است.
set constructor ها اطلاعات کامل نوع را در خود حمل نمیکنند، مثلا اینکه
ست packed است یا نه.
بنابراین، نوع یک set constructor هم packed است و هم unpacked،
تا بتواند از نظر نوع با باقی set ها در set expression ها سازگار باشد.
⚪ کادر زیر نمایانگر تعدای set constructor صحیح است:
[13]
[i+j, i-j]
['0'..'9']
[red, yellow, blue]
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r',
's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
set operations
⚪
اگر X یک set variable و E هم یک set expression باشد آنگاه
X := E
زمانی مجاز است که همهی اعضای E در base type متغیر X باشند و نوع X و E
یا هر دو packed باشد یا هیچکدام packed نباشند.
⚪ فرض کنید A و B مقادیری از یک نوع set باشند؛ در این صورت عملگرها یا operator های زیر روی تمام آبجکتهای با ساختار set قابل اعمال هستند:
| عملگر | کاربرد | نماد ریاضی | نام | مفهوم |
|---|---|---|---|---|
| + | A + B |
$A\cup{B}$ | union یا اجتماع دو مجموعه | تمام عناصر موجود در مجموعهی A به اضافه تمام عناصر موجود در مجموعهی B |
| * | A * B |
$A\cap{B}$ | intersection یا اشتراک دو مجموعه | تمام عناصر مشترک بین دو مجموعهی A و B |
| - | A - B |
$A\setminus{B}$ | set difference یا set minus یا تفاضل دو مجموعه | تمام عناصر مجموعهی A که در مجموعهی B نیستند. |
⚪ پنج عملگر رابطهای زیر روی عملوندهایی از نوع set قابل اعمالند. فرض کنید A و B دو set expression از یک نوع و e یک ordinal expression از base type است:
| عملگر | کاربرد | توضیح ریاضیاتی | نام و مفهوم |
|---|---|---|---|
| in | e in A |
$e\in{A}$ | set membership یا آزمایش عضویت اگر e عنصری در مجموعهی A باشد، True و اگر نباشد False برمیگرداند. |
| = | A = B |
$\forall{X}(X\in{A}\iff{X}\in{B})$ | set equality برابری مجموعهها |
| <> | A <> B |
$\exists{X}(X\in{A}\setminus\iff{X}\in{B})$ | set inequality نابرابری مجموعهها |
| <= | A <= B |
$A\subseteq{B}$ | set inclusion اگر A زیرمجموعهی proper یا improper مجموعهی B باشد True و در غیر این صورت False برمیگرداند. |
| >= | A >= B |
$B\subseteq{A}$ | set inclusion اگر B زیرمجموعهی proper یا improper A باشد True و در غیر این صورت False برمیگرداند. |
⚪ به چند مثال زیر که در آنها set تعریف کردهایم توجه کنید:
TYPE
Primary = (Red, Yellow, Blue);
Color = SET OF Primary;
VAR
Hue1, Hue2: Color;
Vowels, Constants, Letters: SET OF Char;
Opcode: SET OF 0..7;
Add: Boolean;
Ch: Char;
و حال انتسابهای زیر را ملاحظه کنید:
Hue1 := [Red];
Hue2 := [];
Hue2 := Hue2 + [Succ(Red)];
Letters := ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I',
'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R',
'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];
Vowels := ['A', 'E', 'I', 'O', 'U'];
Constants := Letters - Vowels;
Add := [2, 3] <= Opcode
⚪ عملیات روی مجموعهها با این رویکرد طراحی شدهاند که «سریع» باشند و میتوانند جایگزین آزمایشهای پیچیدهتر شوند. به عنوان مثال به جای:
IF (Ch = 'A') OR (Ch = 'E') OR (Ch = 'I') OR (Ch = 'O') OR (Ch = 'U') THEN
S
میتوان به سادگی نوشت:
IF Ch IN ['A', 'E', 'I', 'O', 'U'] THEN
S
⬅ مثال 8.1
⬅ مثال 8.2
on programming development
برنامهنویسی ـــ در معنای طراحی و فرموله کردن الگوریتمها و دیتا استراکچرها ـــ معمولا پروسهای پیچیده و نیازمند مهارت در جزئیات متعدد و تکنیکهای مشخص است. فقط در موارد استثنایی تنها یک راهحل خوب وجود خواهد داشت. معمولا راهحلهای بسیار زیادی وجود دارد و انتخاب یک برنامهی بهینه، نیازمند تحلیل کامل، نه فقط در مورد الگوریتمها و سیستمهای کامپیوتری موجود، بلکه کاوش در مورد این که برنامه در اکثر موارد به چه صورت مورد استفاده قرار میگیرد، نیز است.
متعاقبا، ساخت یک برنامه از دنبالهای از اندیشه، تحقیق و تصمیمات طراحی تشکیل شده است. در مراحل اولیه بهتر است توجه متمرکز بر موضوعات کلی باشد و اولین پیشنویس راهحل ممکن است اعتنا کمی به جزئیات نماید. هنگامی که فرآیند طراحی برنامه پیشرفت میکند میتوانیم مسالهها را به زیرمسائل کوچکتر تقسیم کنیم و به تدریج به جزئیات مشکلات و مشخصههای ابزارهای موجود توجه بیشتر نشان دهیم. عبارتهای stepwise1 refinement و structured programming به این شیوه اختصاص یافتهاند.
⚪ باقیماندهی این فصل توسعهی برنامهای را نشان میدهد که «پاسکال نویسی» مثالی است که C.A.R. Hoare در کتاب structured programming مطرح کرده است. مساله پیدا کردن اعداد اولی است که در محدودهی 2..n قرار دارند و n >= 2 است. بعد از مقایسهی چندین الگوریتم، نهایتا به خاطر سادگی «غربال اِراتُستِن» را انتخاب میکنیم زیرا این الگوریتم هیچ ضرب و تقسیمی ندارد.
برای شروع، فرموله کردن برنامه را به صورت توصیفی انجام میدهیم:
- تمام اعداد از ۲ تا n را در داخل غربال قرار دهید.
- کوچکترین عددی که در داخل غربال قرار دارد را انتخاب و از غربال حذف کنید.
- عدد انتخاب شده را در لیست اعداد اول قرار دهید.
- در غربال حرکت کنید و تمام مضارب این عدد را حذف کنید.
- اگر غربال خالی نشده است گامهای ۲ تا ۵ را تکرار کنید.
اگرچه initialization متغیرها اولین گام در اجرای برنامه است ولی در فرآیند توسعه معمولا آخرین گام است. درک و فهم کامل الگوریتم پیشنیاز یک initializataion مناسب و بجاست؛ بروزرسانی این initialization ها، بعد از هر اصلاح در برنامه، برای اینکه برنامه همچنان به درستی کار کند لازم است. (متاسفانه همیشه بروزرسانی کافی نیست!)
🔷 Hoare نوع set با اعداد 2..n را برای نمایش غربال و همچنین اعداد اول انتخاب کرد. برنامهی 8.3 نسخهای با تفاوت کم از طرح برنامهای است که او ارائه میکند.
🔷 به عنوان یک تمرین Hoare پیشنهاد میکند که برنامه را طوری بازنویسی کنیم که set ها فقط شامل اعداد فرد باشند. یک راهحل میتواند برنامهی 8.4 باشد. به شباهت بسیار زیاد دو برنامه به هم توجه کنید.
🔷 یک هدفِ طراحی در پیادهسازیهای پاسکال این است که تمام عملیات پایهای روی set ها نسبتا سریع انجام شود. بعضی پیادهسازیها اندازهی ماکزیمم set ها را به طول یک کلمه یا word ماشین محدود میکنند، بنابراین هر عضو مجموعه با یک بیت نشان داده میشود. 0 به معنای عدم وجود عنصر در مجموعه و 1 به معنای حضور آن است. بسیاری از پیادهسازیها یک set با 10,000 عنصر را قبول نمیکنند. این ملاحظات باعث میشود تا تعدیل و اصلاحاتی در نحوهی نمایش data به عمل آوریم؛ به این ترتیب به برنامهی 8.5 میرسیم.
یک set بزرگ میتواند به صورت آرایهای از ستهای کوچکتر بیان شود به طوری که هر set در تعداد کمی کلمه یا word قرار میگیرد (همان گونه که دانستیم این موضوع وابسته به پیادهسازی است.) برنامهی 8.5 از الگوی دوم به عنوان مدل abstract الگوریتم استفاده میکند. Sieve و Primes به عنوان آرایهای از set ها بازتعریف شدهاند؛ Next هم از نوع record تعریف گردیده است.
References
- N. Wirth, "Program Development by Stepwise Refinement," Communications of the ACM, 14, 221-227, April 1971.
- O.J. Dahl, E.W. Dijkstra, C.A.R. Hoare, Structured programming, Academic press Inc., 1972.
قدم به قدم - گام به گام ↩