ایمنی

ارائه برای درس علوم کامپیوتر: ساختارهای الگوریتمی اساسی. ارائه با موضوع "الگوریتم ها و روش های توصیف آنها" ساختار پایه "به دنبال"

عرض بلوک px

این کد را کپی کرده و در وب سایت خود قرار دهید

شرح اسلاید:

الگوریتم ها و ساختارهای داده ادبیات:

D. Knut. هنر برنامه نویسی کامپیوتر. T. 1-3، M.: Mir، 1978، 1995، و غیره.
N. Wirth. الگوریتم ها و ساختارهای داده م.: میر، 1989.

مفهوم نوع داده

اطلاعاتکه باید در کامپیوتر پردازش شود انتزاع، بخشی از دنیای واقعی را نمایش می دهد. یعنی قطعه ای که حوزه موضوعی مسئله در حال حل است. برای حل آن ابتدا می سازیم اطلاعاتیو در حالت کلی ریاضی مدلمنطقه موضوعی در حال مطالعه است و موضوع موجود انتخاب می شود یا موضوع جدیدی ساخته می شود الگوریتمحل مشکل

اطلاعات همیشه تحقق می یابد، در فرم نشان داده شده است پیام ها. به طور کلی، یک پیام نشان دهنده برخی است ثبت شده است سیگنال فیزیکی . سیگنال- این تغییر در زمان یا مکان یک شیبه ویژه، پارامتری از مقداری فیزیکی، به عنوان مثال، القای میدان مغناطیسی (هنگام ذخیره اطلاعات، به طور دقیق تر پیام هادر رسانه های مغناطیسی) یا سطح ولتاژ در مدار الکتریکی (در تراشه های پردازنده یا RAM).

گسستهیک پیام یک دنباله است نشانه ها(مقادیر سیگنال) از برخی نهایی الفبا(مجموعه محدودی از مقادیر پارامتر سیگنال)، به ویژه، برای یک کامپیوتر این است دنباله ای از کاراکترهای الفبای دوتایی، یعنی دنباله ای از بیت ها.

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

تفسیر خاص این دنباله به برنامه بستگی دارد فرم های ارائه و ساختار داده، که انتخاب می شوند برنامه نویس. این انتخاب در نهایت به مشکل حل شده و راحتی انجام اقدامات روی داده بستگی دارد.

معانی فوریاین بدون تغییراشیاء برنامه ای که خودشان را نشان می دهند: اعداد (25, 1.34E-20)، نمادها ('A', '!')، رشته ها ('Enter elements matrix');
ثابت هانام هایی هستند که به مقادیر خاصی اختصاص داده شده اند (const pi=3.1415926).
متغیرهااینها اشیایی هستند که می توانند مقداری را بگیرند، بدون تغییر آن را ذخیره کنند، و زمانی که اقدامات خاصی انجام می شوند، آن را تغییر دهند (var k:integer، x:real، a:array).
مقادیر بیان و توابع. عبارات و توابع قوانینی برای محاسبه مقادیر هستند که به روشی خاص نوشته شده اند: k*x+ sqrt(x).

داده های موجود در برنامه ها عبارتند از:

نوع داده مهمترین مشخصه ای است که تعیین می کند:

مجموعه ای از مقادیر معتبر؛
بسیاری از عملیاتی که می توان روی یک مقدار انجام داد.
ساختار ارزش (اسکالر، برداری و غیره)؛
روشی برای نمایش ماشینی معنا

برای نمایش ویژگی های نمایش کامپیوتری داده ها با ماهیت های مختلف در علوم کامپیوتر، رشته های کامپیوتر از مهمترین آنها استفاده می کنند مفهوم نوع داده

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

اصول اولیه مفهوم نوع داده
در زبان های برنامه نویسی:

انواع داده ها و ساختارها

در علوم کامپیوتر استفاده می شود تعداد زیادیمختلف انواع، متنوع ساختارهای داده، که برای مدل سازیاشیایی که در مشکلات مورد بررسی با آن مواجه می شوند.

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

معنی اسکالر(ساده، اتمی)نوع ارائه شده صاف یکیجزء (مثال: زمان، دما).

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

معنی ساختار یافته(کامپوزیت)نوع ارائه شده بیشتر چگونه یکیجزء (به عنوان مثال: بردار، ماتریس، جدول، و غیره).

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

انواع اسکالر (ساده، اتمی):

کل؛
واقعی؛
منطقی (بولی)؛
نمادین؛

انواع ساختار یافته (کامپوزیت):

آرایه
ضبط؛
فایل (دنباله)؛
کثرت؛
نوع شی (کلاس)؛

تمام ترکیبات ممکن از انواع اسکالر و ساختار یافته؛
نوع مرجع

انواع استاتیک (ساختارهای داده)

متداول ترین انواع اسکالر از پیش تعریف شده عبارتند از: عدد صحیح ( عدد صحیح), واقعی ( واقعی، نمادین ( کاراکتر), بولی ( بولی).

مقادیر دقیق عدد صحیح مثالها: 73، -98، 5، 19674.
نمایش ماشین: فرمت نقطه ثابت. محدوده مقادیر با طول فیلد تعیین می شود. عملیات: +، -، *، div، mod،=،<, и т.д.

تایپ کنید عدد صحیح

تقریب های غیر صحیح مثال‌ها: 0.195، -91.84، 5.0
نمایش ماشین: فرمت ممیز شناور. محدوده و دقت مقادیر با طول میدان تعیین می شود. عملیات: +، -، *، /، =،<, и т.д.

تایپ کنید واقعی

کاراکترهای تک متنی مثال‌ها: 'a'، '!'، '5'.
نمایش ماشین: فرمت ASCII. مجموعه مقادیر با جدول کد و قابلیت های صفحه کلید تعیین می شود. عملیات: +، =،<, и т.д.

تایپ کنید کاراکتر

دو مقدار بولی false و true. علاوه بر این، نادرست
نمایش ماشین ─ مقدار صفر و یک بیت: false 0 کدگذاری می شود، درست ─ 1. عملیات: ، ، ، =،< и т.д.

تایپ کنید بولی

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

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

انواع ساختاریافته (کامپوزیت) با موارد زیر مشخص می شوند: تعداد و نوع احتمالی اجزای ارزش، و همچنین نحوه دسترسی به یک جزء ارزش فردی.

معمولاً ساختارهای مشابه بردارها و ماتریس ها در علوم کامپیوتر نامیده می شوند آرایه ها. همه عناصر آرایه باید باشند همان چیزنوع

نوع آرایه یا معمولی

برای دسترسی (رجوع به) یک عنصر آرایه منفرد، از یک شاخص یا چند شاخص (w; w; A) استفاده می شود. ایندکس ها می توانند عباراتی باشند که مقادیر آنها می تواند به طور دلخواه در محدوده های از پیش تعریف شده تغییر کند. بنابراین، آنها می گویند که عناصر آرایه دارند دسترسی مستقیم.

ساختارهای مشابه ردیف های جدول نامیده می شوند رکوردها. اجزای رکوردها معمولاً نامیده می شوند زمینه ها. فیلدهای مختلف (ستون های جدول) می تواند باشد متفاوت استانواع برای دسترسی به فیلدهای فردی یک رکورد، آنها ثابت و غیر قابل تغییر هستند نام ها. به عنوان مثال: روز پیروزی ماه: = اردیبهشت. فیلدها را می توان به هر ترتیبی برای پردازش انتخاب کرد، بنابراین گفته می شود دسترسی به اجزای رکورد وجود دارد مستقیم.

نوع ضبط یا ترکیبی

روز پیروزی:

فایل (توالی)

ساختار اصلی داده ای که برای ذخیره اطلاعات در دستگاه های خارجی (دیسک های مغناطیسی، نوارها و غیره) استفاده می شود. فایل هایا دنباله ها. در نظر گرفته می شود که فایل همیشه در دستگاه خارجی است. در این مورد، تعداد اجزای فایل ناشناخته است. دسترسی به اجزاء ─ سازگار.

پرواز گاگارین:

بسیاری

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

X1 X5 X4

ساختارهای داده پویا

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

شی
لیست خطی؛
درخت؛
نمودار

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

لیست خطی

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

بسیاری از انواع دیگر ساختارهای دینامیکی بر اساس یک لیست خطی سازماندهی شده اند. این به ویژه است: حلقه ها, صف ها, عرشه هاو پشته ها.

ساختار حلقه

تفاوت بین حلقه و لیست خطی در این است که یک حلقه بین آخرین عنصر لیست و اولین عنصر خود ارتباط دارد.

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

ساختار صف

انتهای صف برای درج در دسترس است و ابتدای صف برای حذف (انتخاب) در دسترس است. عنصری که زودتر وارد صف شده و ابتدا سرویس می شود. می گویند صف سازه ای است با نظم و انضباط خدماتی FIFO (افاول من n افاول O ut) ─ "اول آمدن، اول رفتن."

ساختار عرشه

عرشه دارای هر دو انتهای در دسترس است، هم برای گنجاندن و هم برای نمونه برداری. بنابراین، می توان گفت که دسامبر ─ است صف دو طرفه

ساختار پشته

یک پشته فقط یک انتهای ساختار برای تعامل در دسترس است: بالای پشته. هم گنجاندن یک عنصر جدید در پشته و هم انتخاب آخرین عنصر قبلاً گنجانده شده از بالای پشته می‌گذرد. بنابراین، کالایی که آخرین بار وارد شده است ابتدا پردازش می شود. آنها می گویند که پشته سازه ای است با نظم و انضباط نگهداری LIFO (L ast من n افاول O ut) ─ "آخرینی که آمد، اولین بار که رفت."

از توجه شما متشکرم!

برای استفاده از پیش نمایش ارائه، یک حساب Google ایجاد کنید و وارد آن شوید: https://accounts.google.com

شرح اسلاید:

الگوریتم تست درس، خواص آن و ساختارهای الگوریتمی اساسی

هیچ چیز به اندازه انجام کارهای نیک انسان را به خدا نزدیک نمی کند. مارکوس تولیوس سیسرو

طرح تست “نامه به اولاد” کار مستقل حل مسائل تکلیف

الگوریتم چیست؟ الگوریتم توصیفی از دنباله ای از اقدامات با هدف به دست آوردن داده ها از داده ها در تعداد محدودی از مراحل گسسته با استفاده از دستورات قابل درک است. نتیجه اولیه قطعی برای مجری

ویژگی های الگوریتم: - مجری الگوریتم باید بداند که چگونه آن را اجرا کند. - الگوریتم در حال اجرا باید به تعداد محدودی از مراحل منجر شود. - هر الگوریتم باید شامل اقدامات خاصی باشد که به ترتیب خاصی دنبال می شوند. - الگوریتم یکسان را می توان با داده های منبع مختلف استفاده کرد. قابل فهم بودن محدود بودن گسستگی عظیم

اشکال ارائه الگوریتم ها شفاهی شفاهی. گرافیک نوشتاری شفاهی (نمودار جریان):

فلوچارت فلوچارت مجموعه ای است که هر یک از آنها یک عمل را در یک الگوریتم توصیف می کند. اشکال هندسی

– شروع / پایان الگوریتم – ورودی/خروجی داده - محاسبه (انجام عمل). - بررسی شرایط (تصمیم گیری).

انواع اصلی ساختارهای الگوریتمی: چرخه ای انشعاب خطی

"چنگال ها" به صورت کامل و ناقص می آیند

الگوریتم چرخه ای می تواند "حلقه با یک شمارنده"، "حلقه با پیش شرط" و "حلقه با یک شرط پسا" باشد.

مساحت و محیط مستطیل را محاسبه کنید. شروع پایان S = a*b a، b خروجی S را وارد کنید، Р Р = (a + b)*2

محاسبه مقدار هیپوتنوز یک مثلث قائم الزاویه، در صورتی که مقادیر پایه های آن مشخص باشد، ابتدا a، b c = √ a 2 + b 2 خروجی از پایان وارد کنید.

یک تابع مشخص شده را بسته به مقدار آرگومان شروع X محاسبه کنید

یک بلوک دیاگرام برای تعیین مقدار تابع y = √ x ترسیم کنید، زمانی که x غیر منفی است. شروع X > = 0 y = √ x پایان وجود ندارد

مجموع اعداد از فاصله 5 تا 10 با شروع a از 5 تا 10 s = s + a S = 0 پایان شروع s = s + a a

حاصلضرب تمام اعداد از بازه 5 تا 10 با شروع a از 5 تا 10 s = s * a S = 1 پایان شروع s = s * a a

کل زندگی ما الگوریتمی از ساختار پیچیده است. ما باید تلاش کنیم تا اطمینان حاصل کنیم که هر اقدام ما عمدی است و به نتیجه درست و شایسته منتهی می شود!

سعی کنید یک ضرب المثل معروف روسی را با استفاده از فلوچارت آن فرموله کنید

نتیجه الگوریتم ارائه شده در قالب بلوک دیاگرام را تعیین کنید

نمودار جریانی برای عبارت "اگر فکری را نمی توان با کلمات ساده بیان کرد، بی اهمیت است و باید کنار گذاشته شود" تهیه کنید.

یک فلوچارت برای مشکل تهیه کنید: توپ های سفید و سیاه در سبد وجود دارد. شما باید توپ های سفید را در یک جعبه سفید و توپ های سیاه را در یک جعبه سیاه قرار دهید.

تکالیف: یک فلوچارت برای هر ضرب المثل معروف روسی در کتاب کار خود ایجاد کنید.

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

اولین ساختار اساسی زیر است
متشکل از یک زنجیره بلوک بدون
انشعابات

انشعاب

بله
خیر
وضعیت

مورد خاص انشعاب
وضعیت

انشعاب در مواردی استفاده می شود که
هنگامی که شما نیاز به انتخاب یکی از
دو راه برای حل مشکل

چرخه

چرخه در مواردی استفاده می شود که
برای حل مشکل لازم است
همان چیزها را بارها و بارها تکرار کنید
اقدامات

حلقه با شرط پست

حلقه با پیش شرط

چرخه پارامتریک

چرخه پارامتری کنترل شده
پارامتر
پارامتر حلقه یک متغیر است
که به طور یکنواخت در چرخه تغییر می کند،
و معیار خروج بستگی به آن دارد
چرخه

من:= در
بدن
چرخه
i:= i + di
خیر
بله
من > ik

من:=در
i>ik
بدن
چرخه
i:=i+di

طراحی الگوریتم های پیچیده

روش طراحی الگوریتم از بالا به پایین

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

مثال

با توجه به معادله ax2 + bx + c = 0 و تابع
f(x).
اگر معادله ای دو واقعی داشته باشد
ریشه های x1 و x2، جدولی از مقادیر بسازید
تابع در بخش متشکل از n
امتیاز

الگوریتم سطح بالا
ورودی a,b,c
راه حل
معادلات
خیر
x1، x2
یافت
بله
n را وارد کنید
ساخت و ساز
جداول
هیچ راه حلی وجود ندارد
توقف

الگوریتمی که حل مشکل فرعی را پیاده سازی می کند
معادله درجه دوم
d:=b2 – 4ac
خیر
D> 0
بله
X1=(- b + √ d)/2/a
X2= (- b - √ d)/2/a

الگوریتم ساخت جدول مقادیر
توابع
h=(x2-x1)/(n-1)
x = x1
i=1
خروجی x, f(x)
x=x+h
i = i +1
بله
خیر
i>n

بنابراین، راه حل برای مشکل
مشکل از یک الگوریتم بالا تشکیل شده است
سطح و دو کار فرعی
پیوند الگوریتم وظایف فرعی
راه حل
معادلات
ساخت و ساز
جداول f(x)