تلفن همراه

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





این وسیله اولین بار توسط شرکت امریکایی موتورولا در تاریخ ۳ آوریل ۱۹۷۳ با وزنی نزدیک به یک کیلوگرم تولید شد. موبایل نسل‌های گوناگونی دارد و توسط شرکت‌های سازنده گوناگونی تولید می‌شود و به فروش می‌رسد. برخی از شرکت‌های بزرگ تولیدکننده گوشی همراه در دنیا شامل نوکیا، سامسونگ الکترونیکس، ال‌جی الکترونیکس، موتورولا، سونی اریکسون، اپل و اچ‌تی‌سی هستند.

در تلفن‌های همراه به صورت معمول یک مجموعه نرم‌افزار یا سیستم‌عامل برای کنترل سخت‌افزار به کار می‌رود و برنامه‌های جانبی توسط سیستم‌عامل اجرا می‌شوند. از سیستم‌عامل‌های معروف برای تلفن همراه، می‌توان به سیستم‌عامل اندروید (android) و سیمبیان اشاره کرد. حذف شود.






بررسی بلوک‌های داخلی تلفن همراه
بلوک RF

این بلوک متشکل از قطعاتی است که وظیفه آن‌ها ارتباط دادن گوشی به BTS است؛ در حقیقت بلوک RF فرکانس GSM را از BTS دریافت کرده، سپس اطلاعات روی آن را جدا نموده و به واحدهای دیگر موبایل می‌دهد. به زبان دیگر بلوک RF وظیفهٔ تبدیل فرکانس بالای GSM را به فرکانس کمتری به نام IF بر عهده دارد.

امواج موجود در فضا توسط آنتن موبایل دریافت شده و وارد قطعه‌ای به نام آنتن سوییچ می‌شوند. آنتن سوییچ وظیفه تعیین حالت فرستندگی یا گیرندگی آنتن را به عهده دارد. بسته به این که موبایل سازگار با چند باند GSM باشد، تعداد پایه‌های آنتن سوییچ متفاوت خواهد بود. آنتن سوییچ برای هر باند GSM، آنتن را به یک خروجی به نام RX و یک ورودی به نام TX وصل می‌کند. در حقیقت آنتن سوییچ مانند یک کلید است که با فرمان‌هایی آنتن را مرتباً به خط RX یا به TX متصل می‌کند. در بلوکی که مشاهده کردید، موبایل قابلیت کار با دو باند GSM900 و GSM1800 را دارد. بنابراین آنتن سوییچ دو خروجی RX و دو ورودی TX خواهند داشت که در شبکه‌های تلفن ایران از آن جایی که GSM 900 است خط RX و TX باند ۱۸۰۰ بدون استفاده خواهد بود. آنتن سوییچ یکی از قطعات حساس برد موبایل است و خرابی در آن باعث به وجود آمدن عیوبی از قبیل پرش آنتن یا نداشتن دریافت یا ارسال خواهد شد. در مورد سلف و خازن قبل از اتصال آنتن به آنتن سوییچ نیز از آن جایی که امپدانس خروجی آنتن بسیار کم است و از طرفی امپدانس ورودی آنتن زیاد است، باید قبل از اتصال این دو، عمل تطبیق امپدانس توسط قطعه‌ای انجام شود. معمولاً در مدارات، قسمت آنتن موبایل از یک سلف که به صورت موازی بین آنتن و زمین بسته می‌شود استفاده تشکیل می‌شود. این سلف می‌تواند باعث عمل تطبیق امپدانس بین آنتن و آنتن سوییچ شده و مانع از هدایت جریان DC بین این دو واحد گردد تا این دو واحد اثر منفی در عملکرد یکدیگر نداشته باشند. وظیفه فیلتر SAW حذف فرکانس‌های کانال همسایه و فرکانس‌های مزاحم است. خط خروجی RX از آنتن سوئیچ وارد SAW شده و بعد از آن فرکانس‌های مزاحم حذف می‌شود و فقط فرکانس‌های باند GSM در خروجی آن دیده می‌شود. SAW همان‌گونه که فرکانس‌های مزاحم را حذف می‌کند، فرکانس‌های اصلی GSM را هم خیلی ضعیف می‌کند. برای تقویت سیگنال‌های دریافتی GSM بعد از SAW از یک تقویت کننده به نام LNA استفاده می‌شود.

آی‌سی RF: به این آی‌سی HAGAR هم گفته می‌شود که اصلی‌ترین قطعه بلوک RF است و وظیفه آن عمل مدولاسیون و دمودلاسیون است. مدولاسیون به سوار کردن اطلاعات روی یک موج گفته می‌شود، در این صورت با توجه به این که موج می‌تواند در فضا منتشر شود اطلاعات ما نیز همراه موج جابجا می‌شود. به موجی که اطلاعات روی آن سوار می‌شود، موج حامل گویند، یکی از وظایف آی سی HAGER انجام این عمل است. عمل مدولاسیون برای اطلاعاتی که از موبایل به BTS ارسال می‌شود انجام می‌گردد. دمودولاسیون به عمل جداسازی اطلاعات از روی فرکانس حامل می‌گویند. این عمل نیز توسط آی سی HAGER انجام شده و روی سیگنال‌های دریافتی از BTS انجام می‌شود.

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

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

آی سی VCO: یک گوشی موبایل بایستی بتواند روی فرکانس‌های مختلفی که BTS هر منطقه روی آن تنظیم شده قرار گیرد تا با آن ارتباط پیدا کند. به بیان دیگر آی سی HAGER روی فرکانس‌های مختلفی باید بتواند مدولاسین و دمودلاسین انجام دهد. این عمل مستلزم این است که بتوان فرکانس حامل HAGER را با دقت زیاد تغییر داد، این عمل در موبایل توسط قطعه‌ای به نام VCO انجام می‌شود.






بلوک AF

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

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






بلوک MCU

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






بلوک UI

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






بلوک منبع تغذیه و شارژینگ

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






COBBA

در بلوک AF از یک آی‌سی به نام COBBA استفاده می‌شود. این آی‌سی مبدل سیگنال‌های آنالوگ به دیجیتال و برعکس است. امواج دریافتی آنتن بعد از این که توسط آی‌سی RF دمودولاسیون شدند با خطوط RX وارد آی‌سی COBBA در واحد AF می‌شوند. این آی‌سی ابتدا سیگنال‌های دریافتی از RF را توسط خطوط ارتباطی PCM به بلوک MCU می‌دهد. در این بلوک اطلاعات از طریق آی‌سی CPU روی حافظه موقت گوشی ریخته می‌شود. سپس آی‌سی COBBA دوباره از طریق همان خطوط ارتباطی، اطلاعات را از روی حافظه موقت خوانده و به سیگنال آنالوگ تبدیل می‌کند که از طریق بلندگو قابل استفاده خواهد شد. به همین طریق برای اطلاعاتی که بایستی از موبایل خارج شود، صدایی که توسط میکروفون دریافت می‌شود، به صورت سیگنال آنالوگ است. این سیگنال بعد از ورود به آی‌سی COBBA، تبدیل به صدای دیجیتال دیجیتال می‌شود. این صدا از طریق خطوط PCM به واحد MCU منتقل می‌شود تا در حافظه موقت نگهداری شود و به محض کانال‌دار شدن موبایل تمامی اطلاعات قسمت میکروفون از طریق واحد RF به BTS ارسال می‌شود.






PCM

PCM یکی از روش‌های انتقال اطلاعات بین دو واحد است. این واحد خطوط ارتباطی بین آی‌سی COBBA و CPU بوده و در نقشه‌ها از آن به عنوان خطوط PCM نام برده می‌شود. این انتقال به صورت کد شده انجام می‌شود که انواع آن RX و TX است.

۱- خطوط PCM TX مربوط به مسیر جابجایی اطلاعات دیجیتال میکروفون به حافظه؛

۲- خطوط PCM RX مربوط به مسیر انتقال اطلاعات دیجیتال دریافتی به حافظه.

خطوط PCM TX و PCM RX در نقشه‌های گوشی‌ها بین آی سی COBBA و آی‌سی CPU مشخص می‌باشد.






آنالوگ و دیجیتال

سیگنال آنالوگ به آن دسته از سیگنال‌هایی اطلاق می‌شود که مقدار ولتاژ آن در لحظات مختلف در حال تغییر باشد؛ به این صورت که در یک لحظه ۲ ولت، لحظه‌ای دیگر ۳ ولت و به همین صورت در حال تغییر باشد. این سیگنال می‌تواند توسط یک میکروفون ساخته شود. ماهیت تغییرات سیگنال آنالوگ، به عنوان مثال صدا، به مولد آن، که می‌تواند صدای یک انسان باشد، بستگی دارد. سیگنال‌های آنالوگ را در آی‌سی‌های حافظه نمی‌توان ذخیره کرد. همچنین در انتقال آن نیز امکان نویز پذیری بالا است. در مدارات منطقی و کنترلرها اگر بخواهیم یک سیگنال آنالوگ را وارد کنیم باید آن را به دیجیتال تبدیل کنیم. دیجیتال یعنی صفر و یک، در حقیقت در سیستم دیجیتال تغییرات در لحظات مختلف وجود دارد، ولی همیشه این تغییرات به صورت صفر و یک است. منظور از صفر و یک، دو سطح منطقی است. ما می‌توانیم صفر منطقی را به سطح ولتاژ صفر ولت و یک منطقی را به سطح ولتاژ پنج ولت تعریف کنیم. در این صورت سطوح ولتاژ دیگری به غیر صفر و پنج ولت نخواهیم داشت. مزیت دیجیتال در ذخیره‌سازی آن توسط آی‌سی حافظه و همچنین انتقال راحت آن با کیفیت خوب است. برای تبدیل سیگنال آنالوگ به دیجیتال روش‌های مختلفی وجود دارد. اصول تبدیل آن به این صورت است که ابتدا از آنالوگ در لحظات مشخص نمونه‌برداری می‌کنیم، سپس نمونه‌ها توسط یک مبدل به دیجیتال تبدیل می‌شود. هر چه تعداد نمونه گیری‌ها از سیگنال آنالوگ بیشتر باشد، ما توانسته‌ایم آنالوگ را با کیفیت بهتری به دیجیتال تبدیل کنیم. فقط بایستی این مطلب را در نظر بگیریم که افزایش تعداد نمونه برداری‌ها باعث افزایش حجم تبدیل خواهد شد. طریقه تبدیل آنالوگ به دیجیتال لازم است در تبدیل مجموع ارزش بیت‌هایی که یک هستند، برابر با مقدار ولتاژ آنالوگ شود. بیت‌های به دست آمده را می‌توان توسط سلول‌های حافظهٔ موقت یا دائم ذخیره کرد تا در زمان‌های لازم از آن استفاده کنیم. این عمل در موبایل انجام می‌شود و صدای میکروفون ابتدا به دیجیتال تبدیل شده، سپس در حافظه موقت موبایل قرار می‌گیرد تا در لحظه داشتن کانال ترافیکی یک جا بیت‌ها را ارسال کنیم. این باعث می‌شود که در لحظاتی که BTS کانالی را از موبایل می‌گیرد، صدای مشترک در موبایل ذخیره شده و به صورت منقطع به مخاطبین نرسد. برای صدای دریافتی نیز این عمل انجام می‌شود، فقط در آن حالت باید آی‌سی COBBA مجهز به یک مبدل D to A شود تا بتوانیم اطلاعا دیجیتال دریافتی از BTS را به آنالوگ تبدیل کنیم. به تبدیل آنالوگ به دیجیتال باشد. هر چه فرکانس سیگنال آنالوگ بیشتر باشد، لازم است تعداد نمونه برداری‌ها افزایش یابد تا امکان تبدیل تغییرات سریع آن را داشته باشیم.






بلند گو

Earpiece یا COBBA زمانی که تبدیلات را انجام داد باید خروجی آنالوگ را به بلند گو بدهد. معمولاً در بعضی از بردهای موبایل قبل از اتصال سیگنال COBBA به بلند گو از دو مقاومت محدود کننده به صورت سری با بلند گوهای موبایل استفاده می‌کنند.






میکروفن

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






اثرات امواج تلفن همراه بر سلامت انسان

نگرانی‌ها دربارهٔ اثرات امواج تلفن همراه بر سلامت انسان با رشد بیش از حد تلفن‌های بی‌سیم همراه (۲ میلیارد در آگوست ۲۰۰۵) بیشتر شده‌است. این نگرانی‌ها به خاطر این هستند که تلفن همراه از خود امواج الکترومغناطیسی در مقیاس مایکروویو ساطع می‌کند.






اعتیاد به گوشی همراه

بنابه پژوهشی یک متخصص علوم رفتاری اعلام کرد، ۶۰ درصد از دختران موردِ پژوهش از گوشی‌های همراه برای ورود به شبکه‌های اجتماعی و بازی‌های مرتبط استفاده می‌کنند و ۳۰ درصد آنها هنگام اتمام شارژ یا جا ماندن تلفن یا قطع آن به هر شکلی دچار استرس می‌شوند، وی با اشاره به اینکه دختران دو برابر پسران به تلفن همراه وابستگی دارند، درنتیجه از اعتیاد دو برابری دختران نسبت به پسران در زمینه استفاده از تلفن همراه بر اساس این پژوهش انجام‌شده خبر داد.






معروف‌ترین سیستم‌عامل‌های تلفن همراه

iOS
Google Android
لینوکس
Palm OS
RIM Blackberry
Symbian OS
Windows Mobile
بادا bada
Firefox OS







اولین تلفن همراه در ایران

اولین تلفن همراه موجود در ایران که شکل و شمایلی به تلفن‌های همراه امروزی ندارد، متعلق به ناصرالدین شاه بود.

شکل و شمایل این تلفن همراه که در سال ۱۲۳۰ تولید شده است، به تلفن‌های همراه امروزی شباهتی ندارد. این تلفن همراه در سفرها همراه ناصرالدین شاه بوده و در زمان نیاز به کابل‌های کشیده شده بین راه وصل و با مخاطب مورد نظر تماس تلفنی برقرار می‌شده است این تلفن دارای راهنمای فارسی بوده و ساخت کارخانه «البیس» شهر زوریخ می‌باشد.







سیم‌کارت
سیم کارت یا شناس‌کارت (ماژول شناسانندهٔ مشترک) کارتی هوشمند برای تلفن‌های همراه است. سیم کارت به طور امن کلیدهای مشترک-سرویس دهنده را برای شناساندن یک تلفن همراه در خود نگه می‌دارد. یک سیم کارت به کاربران اجازه می‌دهد که گوشی تلفن خود را به آسانی فقط با خارج کردن سیم کارت و قراردادن آن در گوشی دیگر تغییر دهند.
استفادهٔ سیم کارت در شبکه‌های GSM است. معادل سیم کارت در شبکه‌های UMTS به نام USIM یا Universal Sim است، در حالیکه ماژول خارج شوندهٔ معرفی کننده کاربر (RUIM) در تلفن‌های CDMA بیشتر کاربرد دارد.
سیم کارت در دو اندازه استاندارد موجود است. اولی اندازه یک کارت اعتباری (۸۵٫۶۰م. م × ۵۳٫۹۸ م. م × ۰٫۷۶م. م) است. جدیدتر که خیلی محبوب تر هم است، اندازه مینیاتوری با ۲۵ م. م در طول، ۱۵ م. م ارتفاع و نازکی به اندازه ۰٫۷۶ م. م دارد.
W-SIM سیم کارتی هست که هسته فناوری سلولی را با کارتی درون خودش کامل می‌کند.
GSM 11.11 معرفی کننده مشخصات سیم کارت است. GSM 11.14 معرفی کننده مشخصات برنامه‌های ابزاری SIM برای سیم کارت است.






اندازه ذخیره‌سازی حافظه

نوعی ارزان قیمت سیم کارت (فقط GSM 11.11) حافظه کمی دارد، چیزی در حدود ۲-۳ کیلوبایت که در GSM 11.11 تعریف شده است (برای دفترچه تلفن و شبیه آن). همان نوع حافظه داده مستقیماً توسط گوشی مهیا می‌شود. بخش بازاری سیم کارت‌های ارزان قیمت، پایداری آن‌ها است.
سیم کارتهایی با کاربردهای اضافی (GSM 11.14) در اندازهٔ حافظه‌های زیادی موجود است، بیشترین آن‌های یک گیگابایت است. کوچک‌ترین آن‌ها از همان نوع ۳۲ کیلوبایت و ۱۶ کیلوبایت است که در جاهایی که شبکه‌های GSM کمتر گسترش یافته استفاده می‌شوند. اندازه‌های بزرگ‌تری برای حافظه سیم کارت هم وجود دارد که بین ۱۲۸ تا ۱۰۲۴ مگابایت است.
حافظه سیم کارت بیشتر به ارائه دهنده خدمات مربوط می‌شود.
در پایان ۲۰۰۶ بیشترین نوع سیم کارت GSM ای که در آمریکا مورد استفاده قرار گرفت از نوع ۶۴ کیلوبایتی بود.






تغذیه

سه نوع ولتاژ کار برای سیم کارت‌ها وجود دارد: ۵ ولت، ۳ ولت و ۱٫۸ ولت. سیم‌کارت‌های قبل از سال ۱۹۹۸ اکثراً ۵ ولت بودند. سیم‌کارت‌های بعدی با ۵ ولت و ۳ ولت سازگارند. سیم‌کارت‌های مدرن همگی هر سه ولتاژ کار را پشتبیانی می‌کنند.






سیستم‌عامل‌ها

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






داده

سیم کارت‌ها اطلاعات مشخص شده توسط شبکه را برای تصدیق هویت و معرفی مشترک به شبکه را در خود دارند، مهم‌ترین این اطلاعات عبارت اند سیم‌کارت و IMSI و Ki و LAI. یک سیم کارت همچنین اطلاعات دیگری نظیر شماره SMSC (مرکز سرویس پیغام کوتاه)، نام ارائه دهنده خدمات (SPN)، شماره‌های تماس خدمات (SDN) و برنامه‌های سرویس ارزش افزوده (VAS). (رجوع کنید به GSM 11.11)






ICCID

هر سیم کارت به طور بین‌المللی با ICC-ID (شماره کارت مداری بین‌المللی) شناخته می‌شود. ICCID در درون سیم کارت ذخیره می‌شود و همچنین برروی بدنه سیم کارت در طی فرایندی به نام شخصی سازی چاپ یا حک می‌شوند.






IMSI

هر سیم کارت برروی شبکه خودش توسط نگه داری یکتایی مشخص کننده بین‌المللی تلفن مشترک شناسایی می‌شود. اپراتورهای تلفن همراه با استفاده از IMSI تماس‌های تلفن همراه مشترک و ارتباط آن را با دیگر سیم کارت‌ها برقرار می‌کنند.






کلید تصدیق هویت (Ki)

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






پروسه تصدیق هویت

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







معرفی‌کننده موقعیت محلی

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






اندازه سیم کارت

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

اولین سایز سیم کارت به صورت سایز کامل بود(1FF): این سایز تقریباً اندازه کارتهای اعتباری بانکی بود.(۸۵٫۶۰ میلیمتر در ۵۳٫۹۸ میلیمتر به ضحامت ۰٫۷۶ میلیمتر) پس از آن سیم کارت مینی وارد بازار شد(2FF) که بخش کوچکتری از همان سیم کارت بود.(با ضخامت قبلی و ۲۵ میلیمتر در ۱۵ میلیمتر) نسخه بعدی سیم کارت که با نام سیم کارت میکرو(3FF) وارد شد بازهم طول و عرض کمتری نسبت به قبل داشت.(۱۵ میلیمتر در ۱۲ میلیمتر) با کوچکتر شدن سایز سیم کارت، سازگاری آنها با نسخ قبلی همچنان رعایت شد، به همین علت با دستگاههای برش خاص و یا قاب مخصوص می‌توان سه نوع ابتدایی سیم کارتها را به یکدیگر تبدیل کرد بدون آنکه مدار سیم کارت صدمه‌ای ببیند.

سرانجام نیز در سال ۲۰۱۲ نانو سیم کارت (4FF) تولید شد. این سیم کارت بازهم کوچکتر شد. البته برعکس تکامل نمونه‌های قبلی علاوه بر کاهش طول و عرض، ضخامتش نیز کاهش یافت.(۱۲میلیمتر در ۸٫۸ میلیمتر با ضخامت ۰٫۷ میلیمتر) در سیم کارت نانو ضخامت پردازشگر به همراه بدنه ضخامتی معادل ۰٫۷ دارد که حدوداً ۱۵ درصد نسبت به نسخ قبلی کاهش ذخامت داشته است.

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








کارت هوشمند

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

کارت‌های هوشمند از نظر اندازه و شکل ظاهری، شبیه به کارتهای اعتباری معمولی هستند.






تاریخچه کارت هوشمند

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

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

اولین ارتقاء در این کارتها با اضافه نمودن نوار مغناطیسی به آنها که امکان ذخیره سازی اطلاعات را می‌داد، پدید آمد. در ادامه در سال ۱۹۷۰ و با پیشرفت چشمگیر در ریز پردازنده‌ها و ترکیب آنها با حافظه‌های غیر فعال این امکام به وجود آمد تا از انها در کارت‌های هوشمند استفاده شود.

سرانجام در سال ۱۹۸۴ شرکت مخابراتی French PTT با موفقیت اولین کارت تلفن را عرضه کرد تا در عمل نیز این نوع کارت کارایی خود را به اثبات برساند.






کارت‌های هوشمند بدون تماس

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

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






گونه‌ها
کارت هوشمند باتماس (Smart Cards)

کارت‌های هوشمند از نظر اندازه و شکل ظاهری، شبیه به کارت‌های مغناطیسی معمولی هستند. ولی درون این کارت‌ها کاملاً با کارت‌های معمولی متفاوت است. کارت‌های مغناطیسی معمولی یک تکه پلاستیک ساده هستند با یک نوار مغناطیسی؛ در حالی که کارت‌های هوشمند درون خود یک ریز پردازنده دارند این ریز پردازنده چون بیش از اندازه کوچک است با تکنولوژی خاصی کشت می‌شود (تبدیل یک ترانزیستور اندازه یک نخود به سایزی معادل کوچک‌تر از نوک سوزن). ریزپردازنده معمولاً در زیر یک اتصال طلایی در یک طرف کارت قرار دارد. این ریز پردازنده در کارت‌های هوشمند در حقیقت جایگزین نوار مغناطیسی در کارت‌های معمولی شده‌است. اطلاعاتی را که روی نوار مغناطیسی کارت‌های معمولی وجود دارد می‌توان به راحتی خواند، روی آن نوشت، آن را حذف کرد و یا تغییر داد. به علت وجود همین مشکل نوار مغناطیسی محل خوبی برای نگهداری اطلاعات نیست. به همین دلیل هم برای استفاده از چنین کارت‌هایی و تایید صحت و دریافت و پردازش اطلاعات، به طراحی شبکه‌های کامپیوتری گسترده، نیاز هست. کارت هوشمند بدون نیاز به چنین امکاناتی به دلیل امنیت خود می‌تواند اطلاعات را در خود ذخیره کرده و در صورت لزوم در محل‌های مختلف از این اطلاعات بدون نیاز به اتصال به شبکه استفاده کند. ریز پردازنده در کارت هوشمند برای امنیت مورد استفاده قرار می‌گیرد. در واقع کارت هوشمند یک کامپیوتر کوچک است که با کامپیوتری که به دستگاه کارت خوان متصل است ارتباط برقرار می‌کند. تا ریزپردازنده کارت، از معتبر بودن دسترسی به کارت مطمئن نشود، به کارت خوان اجازه دسترسی نمی‌دهد. پس از صدور مجوز دسترسی، کارت خوان می‌تواند همانند یک دیسک با کارت که دارای حافظه (Ram)است کار کند؛ اطلاعات را خوانده، پردازش و تغییر دهید. کارت‌های هوشمند می‌توانند تا ۸ کلیو بایت Ram (حافظه با دسترسی تصادفی برای خواندن و نوشتن اطلاعات)، ۳۶۴ کیلو بایت ROM (حافظه فقط خواندنی)، ۲۵۶ کیلوبایت PROM (حافظه فقط خواندنی قابل برنامه ریزی) و یک ریزپردازنده ۱۶ بیتی داشته باشند. کارت هوشمند همچنین از یک واسط سریال برای نقل و انتقال اطلاعات استفاده کرده، انرژی خود را هم از یک منبع بیرونی (مثلاً دستگاه کارت خوان) تامین می‌کند. ریز پردازنده هم برای انجام یک مجموعه عملیات محدود همانند رمزنگاری مورد استفاده قرار می‌گیرد. کارت‌های هوشمند می‌توانند برای کارت‌های اعتباری، کارت پول‌ها، سیستم‌های امنیتی کامپیوتری، سیستم‌های تشخیص هویت دولتی و بسیاری موارد دیگر مورد استفاده قرار گیرند.






کارت هوشمند بی‌تماس (Contactless)

کارت هوشمند که شبیه به یک کامپیوتر ساده و کوچک است که می‌تواند از طریق دستگاه کارت خوان و اتصال طلایی خود ارتباط برقرار کند، تا بتوان به اطلاعاتی که درون حافظه این کارت قرار دارد دسترسی پیدا کرد. از آنجایی که این کارت‌ها دارای یک ریز پردازنده هستند و این ریز پردازنده به دسترسی به حافظه کارت نظارت می‌کند، می‌توان به امنیت اطلاعات درون کارت اطمینان داشت و اطلاعات مهم را در آن ذخیره کرد. این کارت‌ها که در سال ۱۹۷۰ عرضه شدند مشکل امنیت را که در دسترسی به کارت‌های معمولی مغناطیسی وجود داشت، برطرف کردند. ولی این نوع کارت‌های هوشمند هم همانند کارت‌های معمولی مغناطیسی نیاز به قرار گرفتن در دستگاه برای خوانده شدن اطلاعات دارند. نسل جدید کارت‌های هوشمند، کارت‌های هوشمند بدون تماس هستند. این کارت‌ها بدون تماس و با تکنولوژی القاء Radio Frequency Identification با دستگاه کارت خوان ارتباط برقرار می‌کنند. فقط کافی است این کارت در نزدیکی دستگاه قرار گیرد. این نوع کارت در مواقعی که نیاز به برقراری ارتباط سریع و حتی بدون دخالت دست وجود دارد، کاربرد بسیاری دارد. برای مثال برای ورود یک به اتاق، کارت مکن است در جیب یا کیف شخص باشد و از همان محل و بدون نیاز به خارج کردن با دستگاه کارت خوان ارتباط برقرار کرده و مجاز بودن ورود بررسی شده و در باز شود. همچنین در بسیاری از سیستم‌های حمل و نقل عمومی در دنیا به دلیل حجم زیاد مسافران و به خاطر سریع تر شدن چک کردن بلیط از این نوع کارت‌ها استفاده می‌شود. هم اکنون کارت‌های اعتباری متروی تهران و همچنین من کارت مورد استفاده برای( اتوبوس های خط واحد مشهد، موبایل پارک ها، تاکسی ها و متروی مشهد)از نوع کارت هوشمند بدون تماس هستند. استفاده از این کارتها روز به روز بیشتر می‌شود مثلاً در شهرهای تبریز نیز جهت استفاده از اتوبوس به عنوان کارت بلیط اتوبوس پیاده سازی شده‌است. از نظر فاصله مجاز برای برقراری ارتباط چند نوع کارت هوشمند وجود دارد. در دو نوع از آن‌ها (نوع A و B)که استاندارد هم شده‌اند، حداکثر فاصله مجاز برای برقراری ارتباط ۱۰ سانتی متر است. این فاصله که به این دلیل است که سیستم (برای مثال کم کردن پول از کارت مترو) به صورت ناخواسته (مثلاً گذشتن از کنار ورودی مترو) عمل نکند. همچنین در یک نوع دیگر حداکثر فاصله مجاز برای برقراری ارتباط ۵۰ سانتی متر در نظر گرفته شده‌است

تکنولوژی کارت هوشمند (Smart Card) به عنوان یکی از دستاوردهای نوین بشری، تحولی شگرف در حوزه سیستم‌های کاربردهای روزمره انسانها ایجاد کرده‌است. دو مقوله مهم امنیت(Security) و همراه بودن(Mobility) از ویژگی‌های منحصربه‌فرد این تکنولوژی است. امروزه کاربردهای این تکنولوژی در سطح دنیا در اکثر زمینه‌ها قابل مشاهده بوده و حتی این روند، رو به رشد می‌باشد. بانکها، مراکز مخابراتی، سازمانهای دولتی، مراکز بهداشتی، مراکز ارائه خدمات، مراکز آموزشی، مراکز تفریحی و... از این دستاوردهای کاربردی این تکنولوژی بهره می‌گیرند.







انواع کارت هوشمند:

کارت‌های حافظه تماسی (Contact Memory Card)

کارت‌های دارای پردازشگر (Contact CPU Card)

کارت‌های حافظه بدون تماس (Contact-less Memory Card)

کارت‌های دارای پردازشگر با رابط دوگانه (Dual Interface CPU Card)

انواع کارت‌های هوشمند از دیدگاه تکنولوژی ساخت :

کارت‌های تماسی (‍Contact)

کارت‌های بدون تماس (Contact-less)

کارت‌های با رابط دوگانه (Dual Interface) کارت های هوشمند در ایران تولید نمیشوند. شرکت های مانند شرکت داتکو وارد کننده کارت خام هوشمند هستند.
12:43 pm
کاربرد الگوریتم‌ها

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






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

یکی از کاربردهای مهم الگوریتم‌ها در ژنتیک و در پروژه ژن‌های انسانی است. هدف پروژه ژن انسان، شناسایی تمام ۱۰۰۰۰۰ ژن در 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 آن شمارش شده.
ساعت : 12:43 pm | نویسنده : admin | مطلب قبلی | مطلب بعدی
الگوریتم | next page | next page