لغت نامه و جدول درهم سازی

صفحه 1:
لغت نامه و جدول درهم سازي اه ‎Otocortes uid Wok‏ ساختمان داده ها و الگوریتم 

صفحه 2:
‎EE‏ السام درا ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‏مدظل : |مشهدل مشهد گنج‌روز. (اخ) دی از مشهدی‌لو:[م ]لا دی از دهستان اجارود است که در بخش گرمی مشهدلو. (اخ] تیره‌ای از شهرستان اردبیل واقع است و ۱۳۹ تن سکنه دارد. از فرهنگ مشهد مادررسلیمان ‎(gl)‏ جفرافیائی ایران ۴ 5 ‏مشهد مرقاب. (اخ) جععیت ‎ass‏ ‏مشهد میربزرگ ‎le)‏ ‏5 ن. (اخ) دهی از ‎ ‎ ‏مشهدی. (ص نسبی) منسوب به مشهدی.[اخ) تیره‌ای از 2 مشهدى حسيتكلو. إإخا _ ‏مشهدىسرا. إإخ) دهى از مشهدی‌کندی.[اخ) دی از مشهدی‌لو (ا] دی از مشهدی‌مرادسی الا ‎ ‎ ‎ ‎ ‏مشهدىمير زاكتدى. اغا 9 مشهر. (ع صا 3 ۶ مدخل یافت شد: ۳ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‏اه بعدی تلی ب پژوهش خر | یادداشت مقدم ال || بدیدآورندگان 3 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 3:
© مجموعه اي از زوج هاي مرتب به صورت: ‎(hey, elewent) —‏ - کلید زوج هاي مرتب متفاوت است ‎٩‏ عملیات روي لغت نامه: ‎vet(heKey) -‏ ‎ratte, teABlewecd)‏ ‎rewove(heKey) —‏ 

صفحه 4:
‎٩‏ مجموعه دانشجویان این كلاس ‎oP usstyamedt ocd ex supres) = (hey, elewedl) —‏ ۳ - همه کلیدها منحصر بفرد هستند - مثل: * پیدا کردن زوج مرتبي که کلید آن "علي تقي زاده" باشد * بروز رساني ركوردي که کلید آن "ایمان معتمدي" است - بروز رسائي معادل حذف رکورد فعلي و سپس اضافه کردن ركورد با تغييرات جديد است (ماسسلم() - با یت لس تا سب | : ‎R= (x)‏ = ماس < ‎R‏ 000۸) - © 0 - 

صفحه 5:
© لغت نامه ممکن است کلید تكراري داشته باشد - همانند کلمات تكراري یک لغت نامه © روان : روح؛ جان * روان: رونده » جاري * روان: اسم خاص (اسم شیر) * روان: اسم خاص (اسم شخص) مي توان ركوردهاي هم کلید را با يك لیست نشان داد 

صفحه 6:
‎٩‏ مر م2 بط م< موت) < با ‎Buk eis 3 puir (hep, elewent) ©‏ ۰ م4( ‎d,‏ و97 ‎O= (a, b,‏ بصخخصاصتك عدم - وه ‎(Key, WCleweu), b = (bKep, bClewent),‏ = © مي توان از آرایه یا لیست پيوندي استفاده کرد 

صفحه 7:
* get(theKey) " O(size) time * put(theKey, theElement) * (0)5126) براي تشخیص دادن ‎tS‏ تكراري و , (001 براي افزودن کلید به سمت راست آرایه. * remove(theKey) * O(size) time. 

صفحه 8:
ضا بر اساس کلید به صورت صعودي مرتب شده اند ‎get(theKey)‏ * " O(log size) time * put(theKey, theElement) " (5126 00100 براي يافتن كليد تكراري, (©0)512 براي افزودن كليد در مخل مئاسب * remove(theKey) * O(size) time. 

صفحه 9:
firstN: 4 ٠ 8 8 5 5 8 * get(theKey) " O(size) time * put(theKey, theElement) " (0)929 براي تشخيص دادن كليد تكراري و , (0)) براي افزودن کلید به سمت راست آرایه. ‎remove(theKey)‏ * " O(size) time. 

صفحه 10:
۳5 5 8 8 8 )© اعضا بر اساس کلید به صورت صعودي مرتب شده اند. ‎get(theKey)‏ * ‎O(size) time‏ " * put(theKey, theElement) ‏براي تشخیص دادن کلید تكراري و , (0)) براي افزودن کلید‎ )0)959( ۴ به سمت راست آرايه. 

صفحه 11:
firstN , 3 *اعضا بر اساس کلید به صورت صعودي مرتب شده اند ‎remove(theKey)‏ * = O(size) time. *چگونه مي توان در لیست هاي پيوندي هم جستجوي لگاریتمی انجام داد ؟ 

صفحه 12:
© لغت نامه ساختاري براي نگهداري ركوردهاي اطلاعاتي است - در اغلب برنامه ها مانند کامپایلرها و پردازش متن کاربرد زيادي دارد * بنابراین هزینه عملیات اين ساختار دلده بايد تا حد ممكن كم شود ‎٩‏ زمان اجراي عملیات حذف » اضافه کردن و جستجوي لغت نامه ‏از خطي یا لگاريتمي است ‏- پیاده سازي هاي مختلف برخي عملیات را با هزینه كمتري نسبت به دیگر پیاده سازي ها انجام مي دهند © هزینه افزودن به آرلیه نامرتب (0)) است اما همین هزینه براي ليست مرتب ‏(۵)) است ؟ ‏- ايده ال ما این است که هزینه عملیات مختلف حذف روي لغت نامه ها را ‏به (0)6 کاهش دهیم . 

صفحه 13:
# برنامه نویسان مي توانند طبق قواعد زبان» متغیرها را به دلخواه نامگذاري کنند ‎٩‏ کامپایلر براي اختصاص حافظه و مدیریت متغیرهاء آنها را در جدولي به نام میاه" اسراب,9) نگهداري مي کند - این جدول نمونه اي از ساختار داده ررسجسوت() است. ‏# دستزسی بة این جذول از مرتیه (9)07 است. براي دسترسي (0)0 لازم است آرایه هاي خيلي بزرگ تعریف کنیم - اعداد صحیح: 6666 - رشته ها: بیشتر از اين مقدار 

صفحه 14:
کامپایلر از این جدول براي نگهداري و مدیریت متغیرها و علایم تعریف شده در برنامه ها استفاده مي کند Gyxvbol Dable BOT Chose GpobolPable{ Revords[0..0] //)0 ‏:صدصا سوم‎ daser(XRevord) Oetete(X(Revord) Geavk((Chev) ‎Dobe 8‏ اساس۵) شامل مجموعه اي از رکوردها مثل بر است ‎Record ‎21 ‎ ‎ ‎ ‏لاس سول ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 15:
© ب«وادراك روشيير لودسترسيبه اعضاهار ليه هييمتلجا-11/ اجام 8) لستكه از مرتبه (6)0© لست ‎“ender‏ جرت | 00000 ‎9900 | ‎99 ‎Dee —___, | Intex Beveruir | 1900‏ لبون و ‎6 ‎S ‎ ‎ ‎(Gren) (heck Puccta) | ‏سا‎ Oe SOO 00 ‏تابع رورا تابعي معين (جاده جه (1)) است!‎ * ‎ ‎ ‎6 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 16:
© فرض كنيد كليد ركوردها اعدادي در بازه 2-0..0 باشند ‎٩‏ آرایه اي مب عضوي[-..۳]0/ را مي توان ساخت: * 2۰ ]۱ :@ سب لب < ‎Tk‏ ‎Corvpleniy: © )0( ©‏ © مساله: اكر دامنه كليدها بزرك باشد ...؟ - مثلا اعداد صحيح ! 

صفحه 17:
© تعريف تابع لمیر" که مجموعه کلیدها را به مجموعه اندیسها ترجمه مي کند: 7 0 1 ۵ Ik) = (ks) ‏انا‎ m-| ‎٩‏ مساله جدید: اگر دو کلید به يك مکان ترجمه شوند؛ برخورد اتفاق مي ‎Collision)‏ 

صفحه 18:
(49) = h(86) = h(52) =i بدترین حالت همه کلیدها به يك محل نگاشت شوند: دسترسي: (0)© 

صفحه 19:
9 اگر ب کلید داشته باشیم و آرایه مب عضوي باشد و تابع نگاشت یکنواخت باشد: کلید به ازلي‌هر خانه آرلیه << ۱ اهزینه جستجوین اموفق: ( ۰ + 00 ۰ يافتنمحلكليد : (0)© - يافتنركورد در لیست: (6)0 - هزینه جستجوین اموفق< ‎Pa =O) > O(()‏ © © هزینه جستجوي موفق هم در نهایت» همین اندازه است: (+6)4 

صفحه 20:
‎٩‏ نگاشت یکنواخت کلیدها به خانه هاي آرایه ‎٩‏ عدم حساسیت به ترکیب خاص رکوردهاي ورودي - ون را به خاطر بیاوریدا 9 روش نقسیم:س لوب ۲ < ()۲ - نگاشت کليدهاي :| به ‎WALD‏ ‏- نگاشت یکنواخت .۲.۰ 9 اگر سر ‎atl‏ تابع سیر » به «بیت کم ارزش بستگي دارد! ‎1] - 1 , and r= 6, then 700-01101022 6 

صفحه 21:
© را طوریانتخاب‌کنید که عددياولب‌اشد - مج را عددينزديكتولني‌از 8 یا 40 لنتخابفکنید! - گرچه الگوريتمهاي تقسیم و حل با آرایه هايي که طول آنها عدد اول باشد خوب کار نمي کنند؛ در اینجا چنین انتخايي لازم است »روش ضرب 0 > © > © , ۱۰ ([©م] - ©6) ه ] ع وم - © بياده سازي سريع روش ضرب - با استفاده از عملگرهاي شيفت» اين تابع بياذه سازي سريعي دارد 

صفحه 22:
(ه)ساء ى 000000000 - 0 << 000000000 - - (ووملاء 00000000004 - 0 >> 0000000000 - 

صفحه 23:
- و ايك عدد () بيتي و عدد w bits ro ————"_ extract p bits (ky - اگر اعداد صحیح مورد استفاده در کامپیوتر ررر بيتي و 20 مب باشد. اعشاري 9) به شکل 20/00 ظ) باشد که در آن 8) يك عدد ()بيتي است #به زبان ساده » (عددي به فرم 0/6, 6/6, ۵/6, ۳/۵ باشد ۰ ])0 =[KO/O®] = (KO >> © © P= KD — [KO] = (KG << w) — [KG >> w] = Pronto white 0ج - ام سا و عدم د وو *م دي خم ‎٠‏ 

صفحه 24:
‎٩‏ آدرس دهي باز: به جاي استفاده از لیست پيوندي» از خود آرایه براي نگهداري ركوردهاي برخوردي استفاده مي شود ‏© براي افزودن ركوردي جدید؛ ابتدا محلي خالي در آرايه بيدا مي شود و ركورد جديد در اين محل جاي مي كيرد ‏۶ تابع افزودن رکورد جدید » علاوه بر كليد يك بارامتر ديكر به نام ‎Agha ae Probe Duccber:‏ ‎© OOO, 1, yar} DO, 4) ‏ری‎ ‏* مجموعه [(کسرم ,... , (,۳ ,(0,] باید تركيبي از مجموعه (()..)سرب) باشد - به زبان رياضي: تابع ,|" روي مجموعه (()..0-()) بسته باشد 

صفحه 25:
Insert key k = 4906: 0. Probe /(496,0) 

صفحه 26:
Insert key k = 496: 0 0. Probe h(496,0) 1. Probe /(496,1) collision m-1 

صفحه 27:
insertion m1 Insert key k= 496: 0. Probe /(496,0) 1. Probe /(496,1) 2. Probe /(496,2) 

صفحه 28:
Search for key k = 496: 0. Probe /(496,0) 1. Probe /(496,1) بقل )496,2(/ ‎Probe‏ .2 عمل جستجو از همین روش تابع افزودن» براي پیدا کردن رکورد مورد نظر استفاده مي کند 

صفحه 29:
‎cod‏ ( ۱+( ع ( را مرا و ‎Priory Clhosteriagy Problew‏ — افزایش زمان متوسط جستجوي رکوردها 9 ‎seq.‏ سم ندب - ‎wod we‏ (2 ابص + نيك + ‎Quadratic:k(h,)= (hi(k)‏ © ‎Geooadary Chestertacy‏ — ‎ww dstiot probe seq.‏ — لصب (لطايكة + ‎Double WashieryA(h, ( < ) ١)‏ © عوهحاك 9) مومه )وم 8) - ‎distant probe seq.‏ کین - 

صفحه 30:
© a = ‏ان(‎ oP reverds to be stored Swot ler (scot sera) ‏اما < وله تن‎ © @xpevied cxeober oP probes ٩۱ -۰( ٠ ‏دمع‎ 0.6 > O(probes) =O ‎D C(prbes) = dO‏ 0 - وه 

صفحه 31:
6 همانند بو جاوی) لسن وتاب لمیر | ازبین مجموعه اي از توابع معین به صورت تصادفي انتخاب کنید - افزايش كارايي متوسط الگوریتم - ورودي خاصي از ركوردها در اغلب موارد منجر به بدترين حالت نمي شود 

صفحه 32:
| Records Weck => Ovuble q 7 Ged اگر جدول درهم سازي ؛ پر شود؛ جدول بزرگتري ساخته مي شود. سپس با استفاده از تابع جدید درهم سازي ركوردهاي موجود در حافظه قبلي و همچنین ركوردهاي جدید به اين جدول منتقل مي شوند درهم سازي مجدد عمل هزینه بري است؛ ازهمان ابتدا حافظه بزرگتري استفاده کنید سعي کنید همیشه هسب" لجسا کمتر از 000 درصد 

صفحه 33:
شبکه هاي عصبي - تخمین توابع ‎٩‏ نگاشت فضاهاي برداري ‏© توليد تابع ترا با روشهاي تكاملي ا 

صفحه 34:
‎٩‏ یک 9001) براي نكهداري ركوردهايي تعريف كنيد كه كليد ركوردهاء رشته حرفي باشد؛ چه تابع بجنطو,1 پیشنهاد مي كنيد ؟ ‏9 با استفاده از روش نله موومن ؛ الگوريتمهاي حذف» اضافه و جستجو کردن در جدول رکوردها را بنوپسید. ‏۱ ‏۵ سس - ‎r) ;‏ )سس اس - ; ( )سا ام - ‎°}