سیمز (بازی ویدئویی)
سیمز (به انگلیسی: The Sims) یکی از پروفروشترین بازی‌های تاریخ است و سبک آن شبیه‌سازی زندگی انسان است.





ریشه نام
نام The Sims که اشاره به افرادی که در بازی زندگی می‌کنند دارد و خود این کلمه مخفف کلمه انگلیسی The Simulations به معنای شبیه سازی(مجازی) است.



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




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




گونه‌های بازی‌های ویدئویی

بازی‌های رایانه‌ای بر اساس شیوه انجام بازی و حالت گرافیکی به گروه (ژانر) های زیادی از جمله موارد اشاره شده در فهرست زیر بخش می‌گردند:

آموزشی تعلیمی Educational
اتومبیل‌رانی Driving games
مسابقه اتومبیل‌رانی Racing
راهبردStrategy
راهبرد نوبتیTurn Based Strategy
راهبرد بی‌درنگReal Time Strategy
اکشن - ماجرایی Action-Adventure
مخفی کاری Stealth Action
ترس و بقا Survival Horror
اینترنتی Online games
سکوییPlatformers
تیراندازی Shooters یا Shoot'em Up
تیراندازی سوم شخص Third Person Shooters
تیراندازی اول شخص First-person shooters
شبیه‌سازیSimulation
شبیه‌سازی فضایی Space simulation
ضرباهنگیRhythm games
ماجراییAdventure
مبارزه‌ای Beat 'em up/Fighting
معمایی Puzzle
نقش آفرینی (ایفای نقش) Role-Playing Games
نقش آفرینی غربی، آمریکایی یا کامپیوتری Computer RPG
نقش آفرینی کنسولی یا ژاپنی Japanese RPG
ورزشی Sports
پیجال - هزارتو (لابیرینتی) Maze games

اکشن



اهمیت بازی‌های ویدئویی

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

تحقیقات نشان داده بازی های ویدثویی باعث افزایش هوش میشوداما باعث ایجاد خشونت نیز میشود.





بارگیری و بارگذاری

بارگیری یا دانلود (به انگلیسی: Download)، فرآیند برداشت داده‌های الکترونیکی از یک رایانه (معمولاً یک رایانه دور یا یک سرور) به رایانهٔ دیگر (معمولاً رایانه شما یا یک رایانهٔ محلی)، با مودم یا شبکه رایانه‌ای را گویند. همچنین فرستادن بلوکی از داده‌ها، مانند یک پرونده، با ساختار پست اسکریپت، به دستگاه مستقلی مانند چاپگر پست اسکریپت نیز بارگیری نامیده می‌شود. عمل وارون فرایند فوق را بارگذاری یا آپلود (به انگلیسی: Upload) گویند.

واژه‌های مصوب فرهنگستان برای دانلود و آپلود به ترتیب پایین‌گذاری و بالاگذاری هستند. در زبان اردو به این دو کنش به ترتیب «زیراثقال» و «زِبَراثقال» می‌گویند.



بارگیری
کاربرد نخست این واژه در زمینهٔ رایانه‌ها، از فعل دریافت کردن ریشه گرفته، به معنی گرفتن یک پرونده (یا بارگیری)، از یک رایانه، یک خدمات‌دهندهٔ وب، و یا سامانه‌ای همانند. این واژه در گویش خیابانی و فرهنگ عامیانه، مانند واژهٔ انگلیسی آن، دانلود (Download) گفته می‌شود.



بارگذاری
بارگذاری، یعنی ارسال کردن یک پرونده، از رایانه‌ای به رایانهٔ دیگر. این واژه در گویش خیابانی، مانند واژه انگلیسی آن، آپلود (Upload) گفته می‌شود.




شبکه رایانه‌ای
یک شبکه رایانه‌ای (به انگلیسی: Computer Network)، که اغلب به طور خلاصه به آن شبکه گفته می‌شود، گروهی از رایانه‌ها و دستگاه‌هایی می‌باشد که توسط کانال‌های ارتباطی به هم متصل شده‌اند. شبکه رایانه‌ای باعث تسهیل ارتباطات میان کاربران شده و اجازه می‌دهد کاربران منابع خود را به اشتراک بگذارند.




معرفی

یک شبکه رایانه‌ای اجازه به اشتراک گذاری منابع و اطلاعات را میان دستگاه‌های متصل شده به هم، می‌دهد. در دهه ۶۰ میلادی، آژانس پروژه‌های تحقیقاتی پیشرفته (ARPA)، بودجه‌ای را به منظور طراحی شبکه آژانس پروژه‌های تحقیقاتی پیشرفته (ARPANET) برای وزارت دفاع ایالات متحده آمریکا اختصاص داد. این اولین شبکه رایانه‌ای در جهان بود. توسعه شبکه از سال ۱۹۶۹ و براساس طرح‌های توسعه یافته دهه ۶۰ آغاز شد.





هدف

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

تسهیل ارتباطات: با استفاده از شبکه، افراد می‌توانند به آسانی از طریق رایانامه (E-mail)، پیام‌رسانی فوری، اتاق گفتگو (Chat room)، تلفن، تلفن تصویری و ویدئو کنفرانس، ارتباط برقرار کنند.
اشتراک گذاری سخت افزارها: در یک محیط شبکه‌ای، هر کامپیوتر در شبکه می‌تواند به منابع سخت افزاری در شبکه دسترسی پیدا کرده و از آن‌ها استفاده کند؛ مانند چاپ یک سند به وسیله چاپگری که در شبکه به اشتراک گذاشته شده‌است.
اشتراک گذاری پرونده‌ها، داده‌ها و اطلاعات: در یک محیط شبکه‌ای، هر کاربر مجاز می‌تواند به داده‌ها و اطلاعاتی که بر روی رایانه‌های دیگر موجود در شبکه، ذخیره شده‌است دسترسی پیدا کند. قابلیت دسترسی به داده‌ها و اطلاعات در دستگاه‌های ذخیره سازی اشتراکی، از ویژگی‌های مهم بسیاری از شبکه‌های است.
اشتراک گذاری نرم‌افزارها: کاربرانی که به یک شبکه متصل اند، می‌توانند برنامه‌های کاربردی موجود روی کامپیوترهای راه دور را اجرا کنند.





تعریف

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

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




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

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




بر اساس نوع اتصال

شبکه‌های رایانه‌ای را می‌توان با توجه به تکنولوژی سخت افزاری و یا نرم‌افزاری که برای اتصال دستگاه‌های افراد در شبکه استفاده می‌شود، دسته بندی کرد؛ مانند فیبر نوری، اترنت، شبکه محلی بی‌سیم، HomePNA، ارتباط خط نیرو یا G.hn.

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

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

فناوری ITU-T G.hn از سیم کشی موجود در منازل (کابل هم‌محور، خطوط تلفن و خطوط برق) برای ایجاد یک شبکه محلی پر سرعت (تا۱ گیگا بیت در ثانیه) استفاده می‌کند.




بر اساس تکنولوژی سیم کشی

زوج به‌هم‌تابیده: زوج به‌هم‌تابیده یکی از بهترین رسانه‌های مورد استفاده برای ارتباطات راه دور می‌باشد. سیم‌های زوج به‌هم‌تابیده، سیم تلفن معمولی هستند که از دو سیم مسی عایق که دو به دو به هم پیچ خورده‌اند درست شده‌اند. از زوج به‌هم‌تابیده برای انتقال صدا و داده‌ها استفاده می‌شود. استفاده از دو سیم به‌هم‌تابیده به کاهش تداخل و القای الکترومغناطیسی کمک می‌کند. سرعت انتقال داده، دامنه‌ای از ۲ میلیون بیت درهر ثانیه تا ۱۰۰ میلیون بیت در هر ثانیه، دارد.
کابل هم‌محور: کابل هم‌محور به طور گسترده‌ای در سیستم‌های تلویزیون کابلی، ساختمان‌های اداری، و دیگر سایت‌های کاری برای شبکه‌های محلی، استفاده می‌شود. کابل‌ها یک رسانای داخلی دارند که توسط یک عایق منعطف محصور شده‌اند، که روی این لایهٔ منعطف نیز توسط یک رسانای نازک برای انعطاف کابل، به هم بافته شده‌است. همهٔ این اجزا، در داخل عایق دیگری جاسازی شده‌اند. لایه عایق به حداقل رساندن تداخل و اعوجاج کمک می‌کند. سرعت انتقال داده، دامنه‌ای از ۲۰۰ میلیون تا بیش از ۵۰۰ میلیون بیت در هر ثانیه دارد.
فیبر نوری: کابل فیبر نوری شامل یک یا چند رشته از الیاف شیشه‌ای پیچیده شده در لایه‌های محافظ می‌باشد. این کابل می‌تواند نور را تا مسافت‌های طولانی انتقال دهد. کابل‌های فیبر نوری تحت تاثیر تابش‌های الکترومغناطیسی قرار نمی‌گیرند. سرعت انتقال ممکن است به چند تریلیون بیت در ثانیه برسد.




بر اساس تکنولوژی بی سیم

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

ماهواره‌ها در فضا مستقر هستند؛ به طور معمول ۲۲۰۰۰ مایل (برای ماهواره‌های geosynchronous) بالاتر از خط استوا. این سیستم‌های در حال چرخش به دور زمین، قادر به دریافت و رله صدا، داده‌ها و سیگنال‌های تلویزیونی هستند.

تلفن همراه و سیستم‌های پی سی اس: تلفن همراه و سیستم‌های پی سی اس از چندین فناوری ارتباطات رادیویی استفاده می‌کنند. این سیستم‌ها به مناطق مختلف جغرافیایی تقسیم شده‌اند. هر منطقه دارای فرستنده‌های کم قدرت و یا دستگاه‌های رله رادیویی آنتن برای تقویت تماس‌ها از یک منطقه به منطقه بعدی است.
شبکه‌های محلی بی سیم: شبکه محلی بی سیم از یک تکنولوژی رادیویی فرکانس بالا (مشابه سلول دیجیتالی) و یک تکنولوژی رادیویی فرکانس پایین استفاده می‌کند. شبکه‌های محلی بی سیم از تکنولوژِی طیف گسترده، برای برقراری ارتباط میان دستگاه‌های متعدد در یک منطقه محدود، استفاده می‌کنند. نمونه‌ای از استاندارد تکنولوژی بی سیم موج رادیویی، IEEE است.
ارتباطات فروسرخ: ارتباط فروسرخ، سیگنال‌های بین دستگاه‌ها را در فواصل کوچک (کمتراز ۱۰ متر) به صورت همتا به همتا (رو در رو) انتقال می‌دهد؛ در خط انتقال نباید هیچ گونه شی ای قرار داشته باشد.




بر اساس اندازه

ممکن است شبکه‌های رایانه‌ای بر اساس اندازه یا گستردگی ناحیه‌ای که شبکه پوشش می‌دهد طبقه‌بندی شوند. برای نمونه «شبکه شخصی» (PAN)، «شبکه محلی» (LAN)، «شبکه دانشگاهی» (CAN)، «شبکه کلان‌شهری» (MAN) یا «شبکه گسترده» (WAN).




بر اساس لایه شبکه

ممکن است شبکه‌های رایانه‌ای مطابق مدلهای مرجع پایه‌ای که در صنعت به عنوان استاندارد شناخته می‌شوند مانند «مدل مرجع ۷ لایه OSI» و «مدل ۴ لایه TCP/IP»، بر اساس نوع «لایه شبکه»ای که در آن عمل می‌کنند طبقه‌بندی شوند.




بر اساس معماری کاربری

ممکن است شبکه‌های رایانه‌ای بر اساس معماری کاربری که بین اعضای شبکه وجود دارد طبقه‌بندی شود، برای نمونه معماری‌های Active Networking، «مشتری-خدمتگذار» (Client-Server) و «همتا به همتا» Peer-to-Peer (گروه کاری).





بر اساس همبندی (توپولوژی)

ممکن است شبکه‌های رایانه‌ای بر اساس نوع همبندی شبکه طبقه‌بندی شوند مانند: «شبکه باس» (Bus)، «شبکه ستاره» ((Star، «شبکه حلقه‌ای» (Ring)، «شبکه توری» (Mesh)، «شبکه ستاره-باس» (Star-Bus)، «شبکه درختی» (Tree) یا «شبکه سلسله مراتبی» (Hierarchical) و ترکیبی و غیره.

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





بر اساس قرارداد

ممکن است شبکه‌های رایانه‌ای بر اساس «قرارداد» ارتباطی طبقه‌بندی شوند. برای اطلاعات بیشتر لیست پشته‌های قرارداد شبکه و لیست قراردادهای شبکه را ببینید.



انواع شبکه‌های رایانه‌ای از نظر اندازه




شبکه شخصی (PAN)

«شبکه شخصی» (Personal Area Network) یک «شبکه رایانه‌ای» است که برای ارتباطات میان وسایل رایانه‌ای که اطراف یک فرد می‌باشند (مانند «تلفن»ها و «رایانه‌های جیبی» (PDA) که به آن «دستیار دیجیتالی شخصی» نیز می‌گویند) بکار می‌رود. این که این وسایل ممکن است متعلق به آن فرد باشند یا خیر جای بحث خود را دارد. برد یک شبکه شخصی عموماً چند متر بیشتر نیست. موارد مصرف شبکه‌های خصوصی می‌تواند جهت ارتباطات وسایل شخصی چند نفر به یکدیگر و یا برقراری اتصال این وسایل به شبکه‌ای در سطح بالاتر و شبکه «اینترنت» باشد.

ارتباطات شبکه‌های شخصی ممکن است به صورت سیمی به «گذرگاه»های رایانه مانند USB و فایروایر برقرار شود. همچنین با بهره‌گیری از فناوری‌هایی مانند IrDA، «بلوتوث» (Bluetooth) و UWB می‌توان شبکه‌های شخصی را به صورت بی‌سیم ساخت.





شبکه محلی (LAN)
«شبکه محلی» (Local Area Network) یک «شبکه رایانه‌ای» است که محدوده جغرافیایی کوچکی مانند یک خانه، یک دفتر کار یا گروهی از ساختمان‌ها را پوشش می‌دهد. در مقایسه با «شبکه‌های گسترده» (WAN) از مشخصات تعریف‌شده شبکه‌های محلی می‌توان به سرعت (نرخ انتقال) بسیار بالاتر آنها، محدوده جغرافیایی کوچکتر و عدم نیاز به «خطوط استیجاری» مخابراتی اشاره کرد.

دو فناوری «اترنت» (Ethernet) روی کابل «جفت به هم تابیده بدون محافظ» (UTP) و «وای‌فای» (Wi-Fi) رایج‌ترین فناوری‌هایی هستند که امروزه استفاده می‌شوند، با این حال فناوری‌های «آرکنت» (ARCNET) و «توکن رینگ» (Token Ring) و بسیاری روشهای دیگر در گذشته مورد استفاده بوده‌اند.





شبکه کلان‌شهری (MAN)

«شبکه کلان‌شهری» (Metropolitan Area Network) یک «شبکه رایانه‌ای» بزرگ است که معمولاً در سطح یک شهر گسترده می‌شود. در این شبکه‌ها معمولاً از «زیرساخت بی‌سیم» و یا اتصالات «فیبر نوری» جهت ارتباط محل‌های مختلف استفاده می‌شود.





شبکه گسترده (WAN)

«شبکه گسترده» (Wide Area Network) یک «شبکه رایانه‌ای» است که نسبتاً ناحیه جغرافیایی وسیعی را پوشش می‌دهد (برای نمونه از یک کشور به کشوری دیگر یا از یک قاره به قاره‌ای دیگر). این شبکه‌ها معمولاً از امکانات انتقال خدمات دهندگان عمومی مانند شرکت‌های مخابرات استفاده می‌کند. به عبارت کمتر رسمی این شبکه‌ها از «مسیریاب»ها و لینک‌های ارتباطی عمومی استفاده می‌کنند.

شبکه‌های گسترده برای اتصال شبکه‌های محلی یا دیگر انواع شبکه به یکدیگر استفاده می‌شوند. بنابراین کاربران و رایانه‌های یک مکان می‌توانند با کاربران و رایانه‌هایی در مکانهای دیگر در ارتباط باشند. بسیاری از شبکه‌های گسترده برای یک سازمان ویژه پیاده‌سازی می‌شوند و خصوصی هستند. بعضی دیگر به‌وسیله «سرویس دهندگان اینترنت» (ISP) پیاده‌سازی می‌شوند تا شبکه‌های محلی سازمانها را به اینترنت متصل کنند.





شبکه متصل (Internetwork)

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

در کاربردهای جدید شبکه‌های به هم متصل شده از قرارداد IP استفاده می‌کنند. بسته به اینکه چه کسانی یک شبکه از شبکه‌ها را مدیریت می‌کنند و اینکه چه کسانی در این شبکه عضو هستند، می‌توان سه نوع «شبکه متصل» دسته بندی نمود:

شبکه داخلی یا اینترانت (Intranet)


شبکه خارجی یا اکسترانت (Extranet)


شبکه‌اینترنت (Internet)

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




شبکه داخلی (Intranet)

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

به طور مثال شبکه ملی در ایران نوعی از شبکه‌های داخلی (اینترانت) می‌باشد.





شبکه خارجی (Extranet)

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





شبکه اینترنت (Internet)

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

اعضای شبکه اینترنت یا شرکت‌های سرویس دهنده آنها از «آدرسهای IP» استفاده می‌کنند. این آدرس‌ها از موسسات ثبت نام آدرس تهیه می‌شوند تا تخصیص آدرسها قابل کنترل باشد. همچنین «سرویس دهندگان اینترنت» و شرکت‌های بزرگ، اطلاعات مربوط به در دسترس بودن آدرس‌هایشان را بواسطه «قرارداد دروازه لبه» (BGP) با دیگر اعضای اینترنت مبادله می‌کنند.





اجزای اصلی سخت‌افزاری

همه شبکه‌ها از اجزای سخت‌افزاری پایه‌ای تشکیل شده‌اند تا گره‌های شبکه را به یکدیگر متصل کنند، مانند «کارت‌های شبکه»، «تکرارگر»ها، «هاب»ها، «پل»ها، «راهگزین»ها و «مسیریاب»ها. علاوه بر این، بعضی روشها برای اتصال این اجزای سخت‌افزاری لازم است که معمولاً از کابلهای الکتریکی استفاده می‌شود (از همه رایجتر «کابل رده ۵» (کابل Cat5) است)، و کمتر از آنها، ارتباطات میکروویو (مانند آی‌تریپل‌ئی ۸۰۲٫۱۱) و («کابل فیبر نوری» Optical Fiber Cable) بکار می‌روند.





کارت شبکه (network adapter)

«کارت شبکه»، «آداپتور شبکه» یا «کارت واسط شبکه» (Network Interface Card) قطعه‌ای از سخت‌افزار رایانه‌است و طراحی شده تا این امکان را به رایانه‌ها بدهد که بتوانند بر روی یک شبکه رایانه‌ای با یکدیگر ارتباط برقرار کنند. این قطعه دسترسی فیزیکی به یک رسانه شبکه را تامین می‌کند و با استفاده از «آدرسهای MAC»، سیستمی سطح پایین جهت آدرس دهی فراهم می‌کند. این شرایط به کاربران اجازه می‌دهد تا به وسیله کابل یا به صورت بی‌سیم به یکدیگر متصل شوند.





تکرارگر (repeater)

«تکرارگر» تجهیزی الکترونیکی است که سیگنالی را دریافت کرده و آن را با سطح دامنه بالاتر، انرژی بیشتر و یا به سمت دیگر یک مانع ارسال می‌کند. بدین ترتیب می‌توان سیگنال را بدون کاستی به فواصل دورتری فرستاد. از آنجا که تکرارگرها با سیگنال‌های فیزیکی واقعی سروکار دارند و در جهت تفسیر داده‌ای که انتقال می‌دهند تلاشی نمی‌کنند، این تجهیزات در «لایه فیزیکی» یعنی اولین لایه از «مدل مرجع OSI» عمل می‌کنند.





هاب (جعبه تقسیم)- hub

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





پل (bridge)

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




پل‌ها به سه دسته تقسیم می‌شوند:

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




راهگزین (switch)

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

از نظر فنی می‌توان گفت که راهگزین در «لایه پیوند داده» از «مدل مرجع OSI» عمل کنند. ولی بعضی انواع راهگزین قادرند تا در لایه‌های بالاتر نیز به بررسی محتویات بسته بپردازند و از اطلاعات بدست آمده برای تعیین مسیر مناسب ارسال بسته استفاده کنند. به این راه گزین‌ها به اصطلاح «راهگزین‌های چندلایه» (Multilayer Switch) می‌گویند.




مسیریاب (router)

«مسیریاب»ها تجهیزات شبکه‌ای هستند که بسته‌های داده را با استفاده از «سرایند»ها و «جدول ارسال» تعیین مسیر کرده، و ارسال می‌کنند. مسیریاب‌ها در «لایه شبکه» از «مدل مرجع OSI» عمل می‌کنند. همچنین مسیریاب‌ها اتصال بین بسترهای فیزیکی متفاوت را امکان‌پذیر می‌کنند. این کار با چک کردن سرایند یک بسته داده انجام می‌شود.

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




اینترنت

اینترنت (به انگلیسی: Internet) (مخفف interconnected networks شبکه‌های به هم پیوسته) را باید بزرگ‌ترین سامانه‌ای دانست که تاکنون به دست انسان طرّاحی، مهندسی و اجرا گردیده‌است. ریشهٔ این شبکهٔ عظیم جهانی به دههٔ ۱۹۶۰باز می‌گردد که سازمان‌های نظامی ایالات متّحدهٔ آمریکا برای انجام پروژه‌های تحقیقاتی برای ساخت شبکه‌ای مستحکم، توزیع شده و باتحمل خطا سرمایه‌گذاری نمودند. این پژوهش به همراه دوره‌ای از سرمایه‌گذاری شخصی بنیاد ملی علوم آمریکا برای ایجاد یک ستون فقرات جدید، سبب شد تا مشارکت‌های جهانی آغاز گردد و از اواسط دههٔ ۱۹۹۰، اینترنت به صورت یک شبکهٔ همگانی و جهان‌شمول در بیاید. وابسته شدن تمامی فعّالیت‌های بشر به اینترنت در مقیاسی بسیار عظیم و در زمانی چنین کوتاه، حکایت از آغاز یک دوران تاریخیِ نوین در عرصه‌های گوناگون علوم، فن‌ّآوری، و به خصوص در نحوه تفکّر انسان دارد. شواهد زیادی در دست است که از آنچه اینترنت برای بشر خواهد ساخت و خواهد کرد، تنها مقدار بسیار اندکی به واقعیت درآمده‌است.

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

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




واژه‌شناسی

در زبان انگلیسی واژهٔ Intrnet هنگامی که به شبکه جهانی مبتنی بر پروتکل IP اطلاق می‌گردد، با حرف بزرگ در اول کلمه، نوشته می‌شود.
در رسانه‌ها فرهنگ عامه، گاه با اینترنت به صورت یک مقوله عمومی و مرسوم برخورد کرده و آن را با حرف تعریف و به صورت حروف کوچک می‌نگارند(the internet)
در برخی منابع بزرگ نوشتن حرف اول را به دلیل اسم بودن آن جایز می‌دانند نه برای صفت بودن این واژه.
واژهٔ لاتین the Internet چنانچه به شبکهٔ جهانی اینترنت اشاره کند، اسم خاص است و حرف اوّلش با حروف بزرگ آغاز می‌شود(I). اگر حرف اوّل آن کوچک باشد می‌تواند به عنوان شکل کوچک شده کلمه Internetwork برداشت شود که به معنی میان شبکه است. واژه "ابر" نیز به صورت استعاری، به ویژه در ادبیات رایانش ابری و نرم‌افزار به عنوان سرویس، برای اشاره به اینترنت به کار می‌رود.
7:26 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 آن شمارش شده.
ساعت : 7:26 am | نویسنده : admin | مطلب قبلی | مطلب بعدی
الگوریتم | next page | next page