آماده سازی دانش آموزان برای المپیاد انفورماتیک. برنامه آمادگی فردی برای مرحله شهری المپیاد روسی برای دانش آموزان با موضوع "انفورماتیک و فناوری اطلاعات و ارتباطات. برنامه ریزی برای آمادگی برای المپیاد در انفورماتیک".

تجزیه و تحلیل مسائل المپیاد.

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

مطالب کلاس کارشناسی ارشد (ارائه)

در RMO معلمان انفورماتیک.

معلمان انفورماتیک و ICT

تفاهم نامه "لیسه شماره 23"

شووالووا سوتلانا یوریونا.

این مقاله خلاصه ای از مطالبی است که من در RMO معلمان انفورماتیک در سال 2011، 2012 بر اساس نتایج مراحل مدرسه المپیاد روسی برای دانش آموزان در انفورماتیک ارائه کردم.

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

اسلاید 1.

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

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

وظایف مرحله مدرسه المپیاد باید چنان پیچیده باشد که دانش آموزان را نترساند، بلکه به آنها فرصت دهد تا بهترین ویژگی های خود را نشان دهند.

اسلاید 2.

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

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

اسلاید 3.

مشکلات المپیاد برای مراحل مدرسه و شهرداری المپیاد در انفورماتیک با تنوع موضوعی متمایز می شود.

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

• ترکیبیات؛
• مرتب سازی و جستجو؛
• پردازش توالی؛
• الگوریتم های گراف؛
• عناصر هندسه محاسباتی
• شمارش گزینه ها و روش های کاهش آن؛
• برنامه نویسی پویا

اسلاید 4.

مراحل حل مسائل المپیاد:

• تجزیه و تحلیل بیان مسئله.
• رسمی کردن بیان مسئله
• توسعه یک الگوریتم برای حل مسئله.
• پیاده سازی نرم افزاری الگوریتم
• اشکال زدایی و تست برنامه.
• ارائه راه حل برای بررسی

اسلاید 5.

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

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

یکی از نکاتی که باید هنگام نوشتن برنامه به خاطر بسپارید این استذخیره فایل های ویرایش شدهدر طول تور

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

اسلاید 6.

اشتباهات رایج:

• فرمت ورودی-خروجی داده با شرایط کار مطابقت ندارد

• همه موارد ممکن در نظر گرفته نمی شود

• نوع داده (بعد) به درستی تنظیم نشده است

• از دست دادن فایل های ویرایش شده در طول یک تور

اسلاید 7.

حداقل پایه دانش برای المپیاد انفورماتیک.

زبان برنامه نویسی:

• ساختارهای الگوریتمی پایه،
• توابع ریاضی استاندارد،
• رویه ها و توابع برای پردازش متغیرهای رشته،
• رویه ها و توابع برای کار با آرایه ها.

الگوریتم های معمولی

اسلاید 8.

وظایف المپیادهای انفورماتیک همیشه با "استاندارد آموزش عمومی پایه و متوسطه (کامل) در انفورماتیک و ICT مطابقت ندارد. علاوه بر این، به عنوان راه حلی برای این مشکلات در المپیاد، ارائه برنامه های اشکال زدایی شده که با زبان برنامه نویسی سطح بالا نوشته شده اند، الزامی است و نه توضیحات الگوریتم ها.

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

اسلاید 9.

منابع اینترنتی برای آمادگی برای المپیادهای علوم کامپیوتر:

http://algolist.manual.ru/

تحلیل مشکلات دور مدرسه المپیاد 2011.

مشکل شماره 1 "ضبط موسیقی" (15 امتیاز)

اگر فضای خالی دیسک 6 مگابایت است و برای ضبط یک ثانیه صدا به 16 کیلوبایت نیاز است، بررسی کنید که آیا یک آهنگ موسیقی که m دقیقه و n ثانیه طول می کشد روی دیسک کامپیوتر قرار می گیرد یا خیر.

الگوریتم حل:

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

مشکل شماره 2 "قفل گاوصندوق ترکیبی"(20 امتیاز)

باید از 10 حرف 3 تایپ کنید تکرار حروف جایز است. تعداد ترکیب کدهای ممکن را بشمارید.

الگوریتم حل:

مشکل ترکیبی برای حل آن، لازم است یک الگوریتم معمولی برای تشکیل گروه های قرارگیری با تکرار اعمال شود. از حلقه های تو در تو استفاده می شود.

مشکل شماره 3 "مستطیل"(30 امتیاز)

N مستطیل در صفحه نشان داده شده است. هر مستطیل با مختصات رئوس پایین سمت چپ و بالا سمت راست مشخص می شود. تعیین کنید که آیا مستطیل ها دارای یک منطقه مشترک هستند یا خیر

الگوریتم حل:

اگر حداکثر مختصات X رئوس پایین سمت چپ مستطیل ها کمتر از حداقل مختصات رئوس بالا سمت راست و حداکثر مختصات Y رئوس پایین سمت چپ مستطیل ها کمتر از حداقل مختصات رئوس بالا سمت راست باشد. ، سپس کل مساحت است.

یک الگوریتم معمولی برای یافتن حداکثر (حداقل) عنصر آرایه استفاده می شود.

مشکل شماره 4 "مربع جادویی"(35 امتیاز)

در یک مربع 3×3 اعداد 1، 2، ...، 9 را قرار دهید تا مجموع اعداد هر سطر، ستون، در هر قطر با هم برابر باشد.

الگوریتم برای حل.وظیفه در راه برای پر کردن یک آرایه دو بعدی.

(روش هندی):

1. در وسط خط بالایی قرار دهید 1 ، در آخرین ردیف ستون کنار سمت راست 2 .
2. اعداد زیر در جهت مورب قرار می گیرند.
3. پس از رسیدن به لبه سمت راست مربع، به سمت چپ ترین سلول ردیف پوشاننده بعدی می روند.
4. پس از رسیدن به لبه بالایی مربع، به پایین ترین سلول ستون مجاور سمت راست می روند. توجه داشته باشید. پس از رسیدن به سلول گوشه سمت راست بالا، به سمت چپ پایین بروید.
5. پس از رسیدن به سلولی که قبلاً اشغال شده است، به سلولی می روند که مستقیماً در زیر آخرین سلول پر قرار دارد.
6. اگر آخرین خانه پر شده در ردیف پایین مربع است، به بالاترین خانه در همان ستون بروید.

تحلیل مشکلات دور مدرسه المپیک 2012.

هدف 1.

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

الگوریتم حل:

یکی از گزینه های حل با زور بی رحم:

var a, b, c, n, k: عدد صحیح;

شروع

نوشتن ("n="); readln (n);

برای یک: = 1 تا 9 انجام دهید

برای b: = 0 تا 9 انجام دهید

برای c: = 0 تا 9 انجام دهید

اگر a + b + c = n پس

شروع

نوشتن (a، b، c، "")؛

k: = k + 1;

پایان؛

نوشته شده است؛

Writeln ("k =، k)؛

نوشته شده است؛

پایان.

راه حل دوم با زور بی رحمانه است:

Var a, b, c, n, k, m: عدد صحیح.

شروع

نوشتن ("n="); readln (n);

برای m: = 100 تا 999 انجام دهید

شروع

c: = m mod 10;

b: = m div 10 mod 10;

a: = m div 100;

اگر a + b + c = n پس

شروع

نوشتن (m: 5);

k: = k + 1;

پایان؛

پایان؛

writeln ("k =، k)

پایان.

هدف 2. "بچه و کارلسون".

کید و کارلسون در یک اتاق مستطیل شکل زندگی می کنند A x B ... نحوه محاسبه چند فرش مربع با ضلع مورد نیاز استبا برای پوشاندن کامل کف اتاق؟ (کید و کارلسون نه می توانند تقسیم کنند و نه ضرب.) برنامه ای برای حل این مشکل بنویسید.

الگوریتم حل:

در حلقه بیرونی، در یک طرف اتاق (در حالی که ص ) فضای ذخیره برای ردیف ( p: = p + c ، سپس در حلقه داخلی در امتداد طرف دیگر (در حالی که م ) بررسی می کنیم که اپراتور از چند فرش می توان برای بستن ردیف استفاده کرد m: = m + s فضا را برای تشک و اپراتور رزرو می کند kovrik: = kovrik + 1 تعداد کل فرش های نصب شده را محاسبه می کند.

var a, b, c, kovrik, m, p: integer;

شروع

readln (الف، ب، ج)؛

kovrik: = 0;

p: = 0;

در حالی که ص

شروع

p: = p + c;

m: = 0;

در حالی که م

شروع

m: = m + c;

kovrik: = kovrik + 1

پایان؛

نوشتن (کورویک)

پایان.

وظیفه 3. "باکتری".

مستعمره شامل n باکتری (بیش از 30000). ویروسی وارد آن شد که در دقیقه اول یک باکتری را از بین برد و سپس به دو ویروس جدید تقسیم شد. به طور همزمان، هر یک از باکتری های باقی مانده نیز به دو باکتری جدید تقسیم می شوند. در دقیقه بعد، دو ویروسی که به وجود آمدند، دو باکتری را از بین بردند و سپس همه ویروس ها و باکتری ها دوباره از هم جدا شدند و به همین ترتیب. آیا این مستعمره تا ابد زنده خواهد ماند یا از بین خواهد رفت؟

برنامه شما باید:

• تعداد باکتری ها را درخواست کنید n
• پیدا کنید و گزارش دهید: در چند روز، ساعت و چند دقیقه کلنی باکتری وجود نخواهد داشت یا پیامی مبنی بر ابدی بودن کلنی صادر می کند.

پاسخ مثال: برای n = A. پاسخ - B روز C ساعت D دقیقه (که در آن A، B، C، D مقادیر عددی هستند).

الگوریتم حل:

برنامه نویسی به زبان برنامه نویسی پاسکال

Var a, b, c: shortint;

t, n, v: longint;

شروع

بنویسید ("اندازه مستعمره اولیه -")؛ readln (n)؛

v: = 1;

در حالی که n> 0 انجام دهید

شروع

t: = t + 1; (دقایق)

n: = (n - v) * 2; (باکتری)

v: = v * 2; (ویروس ها)

پایان؛

a: = t div 1440;

b: = (t - a * 1440) div 60;

ج: = t - a - b;

بنویسید ("این مستعمره وجود نخواهد داشت"، a، "روزها"، b، "ساعت ها"، c، "دقیقه")؛

پایان.

وظیفه 4.

به شما یک مستطیل با اضلاع A و B داده می شود که در آن A، B اعداد طبیعی هستند. ما شروع به بریدن مربع ها از آن می کنیم (شکل 1). اگر هر بار بزرگترین مربع را قطع کنید، چند عدد از این مربع ها را می توانید قطع کنید؟

الگوریتم حل:

1 راه.

برای حل این مشکل به توابع نیاز داریم MAX و MIN ، برای تعریف آنها از subroutines-functions استفاده می کنیم.

معرفی کنیم:

• متغیرهای کمکی X و Y (Y> = X) مربوط به اضلاع رو به کاهش مستطیل؛
• متغیر کمکیدی ، که کاهش اندازه مستطیل را پس از برش بعدی بزرگترین مربع که ضلع آن به صورت قرار دارد را تعیین می کند. X: = MIN (D، X).

ما یک چرخه را سازماندهی می کنیم که در آن طرف Y هر بار کاهش می یابد MIN (D، X) تا آخرین مربع باقی بماند، یا Y کمتر نخواهد شدایکس. در مورد دوم، اضلاع مستطیل باقی مانده را به عنوان تغییر نام دهید Y: = MAX (D، X) و X: = MIN (D، X) و چرخه را ادامه دهید.

برنامه نویسی به زبان برنامه نویسی پاسکال

var a، b، d، k، x، y: عدد صحیح.

تابع min (i, j: integer): عدد صحیح;

شروع

اگر من

else min: = j

پایان؛

تابع حداکثر (i، j: عدد صحیح): عدد صحیح؛

شروع

اگر من

other max: = i

پایان؛

شروع

تکرار

Writeln ("vvedite dva naturalnix chisla");

Readln (الف، ب)؛

تا (a> 0) و (b> 0)؛

k: = 1;

x: = min (a, b);

y: = حداکثر (a, b);

در حالی که x y انجام می دهد

شروع

k: = k + 1;

d: = y-x;

y: = حداکثر (d, x);

x: = دقیقه (d، x);

پایان؛

Writeln ("iskomoe chislo kvadratov:"، k)

پایان.

روش 2.

مشکل را می توان با استفاده از توابع استاندارد حل کردپاسکال: Y DIV X و Y MOD X، با استفاده از الگوریتم اقلیدس

الگوریتم حل:

ما چرخه ای را سازماندهی می کنیم که در آن بقایای تقسیم را تشکیل می دهیم r 0، r 1، r 2، ...، r n، r n + 1 تا زمانی که یکی از این باقیمانده ها برابر با صفر شود r n + i = 0 ... بنابراین، ما یک تابع برای تولید باقی مانده تقسیم می سازیم r n + i = r n mod r n-i، که r 0 = A و r i = B ... برای همان سیستم باقیمانده، می‌توانیم محاسبه کنیم که باقیمانده چند بار کاملاً جا می‌شود r n-i به r n.

(الگوریتم اقلیدس)

var A, B, R0, R, R1, K: عدد صحیح.

شروع

تکرار

بنویسید ("شماره طبیعی A =" را وارد کنید.

Readln (A)؛

بنویسید ("عدد طبیعی را وارد کنید

Readln (B)؛

تا (B> 0) و (A> 0) و (A> = B)؛

R0: = A;

R1: = B;

K: = R0 div R1;

در حالی که R0 mod R1 0 انجام دهید

شروع

R: = R0 mod R1;

R0: = R1;

R1: = R;

K: = K + R0 div R1

پایان؛

Writeln ("تعداد مربعات زیر K =، K)؛

مقاله توسط معلم OIVT لیسه شماره 8 Pangina N.N. از مجله "ابزارهای کامپیوتری در آموزش"، شماره 1، 2000

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

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

به مدت شش سال، بر اساس مدرسه-لیسه شماره 8 در Sosnovy Bor، دانش آموزان مدرسه برای المپیادهای سطوح مختلف آماده می شوند. به مدت پنج سال، دانش آموزان لیسه برندگان المپیادهای برنامه نویسی منطقه ای، شرکت کنندگان و برندگان جوایز المپیادهای سراسر روسیه بوده اند.

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

سوال 1... پس آیا می توان دانش آموزان مدرسه ای را برای المپیادها آماده کرد؟

ممکن است، اما نه در چارچوب برنامه اولیه.

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

ویکتور بارگاچف، 2 بار قهرمان مطلق جهان در علوم کامپیوتر در میان دانش آموزان، برنده جایزه المپیاد بین المللی در ریاضیات (مدال نقره) است.

نیکولای دوروف، برنده 4 بار المپیادهای بین المللی انفورماتیک (3 مدال نقره و یک مدال طلا)، صاحب دو مدال طلای المپیادهای بین المللی در ریاضیات است.

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

در منطقه لنینگراد، می توان به عنوان مثال، الکسی استراتونیکوف، الکسی پوتاپوف، آرتم آنانیف، آندری پانگین را ذکر کرد.

سوال 2 ... از چه سنی باید آماده سازی دانش آموزان مدرسه را شروع کرد؟

هر چه زودتر بهتر، اما در محدوده معقول.

برای سطح

کافی است المپیادهای منطقه ای را از کلاس 7 - 8 شروع کنید.

توصیه می شود المپیادهای روسیه را از کلاس پنجم تا ششم شروع کنید.

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

سوال 3 ... به چه شکل کلاس های آمادگی برای المپیادها را برگزار کنیم؟

به صورت دروس انتخابی یا اختصاصی.

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

با توجه به تجربه لیسه ما، این امر با موارد زیر تسهیل می شود:

ارتباطات بین رشته ای نقش مهمی ایفا می کند.

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

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

چنین دروسی با توجه به میزان آمادگی دانش آموزان متفاوت انجام می شود.

برای کلاس های 7 تا 8، یک اردوی مدرسه ای "عقل" در دو تا سه هفته اول تعطیلات تابستانی برگزار می شود که در آن کودکان طبق یک برنامه خاص به علوم کامپیوتر مشغول می شوند.

به عنوان مثال، برنامه هزارتو شامل موضوعات زیر است:

ساخت یک ماز ​​(الگوریتمی جالب برای تولید یک پیچ و خم تصادفی با پیچیدگی های مختلف)؛

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

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

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

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

برای 10 کلاس، تمرین صنعتی تابستانی در شرکت های مختلف در شهر Sosnovy Bor به مدت یک ماه سازماندهی می شود. دانش آموزان مهارت هایی را در حل مسائل عملی کسب می کنند، دانش کار با پایگاه های داده، برنامه های دفتر حسابداری را ادغام می کنند، به طور مستقل برنامه هایی را مطابق با تکالیف متصدیان ایجاد می کنند، دانش اضافی را به دست می آورند (به عنوان مثال، هنگام کار با شبکه های کامپیوتری، سیستم عامل یونیکس). یک بررسی قابل ستایش از سوی شرکت نتیجه رایج چنین کاری است.

بچه ها برنامه های خود را در کنفرانس سنتی مدرسه در مورد علوم کامپیوتر "ما و کامپیوتر" نشان می دهند، امسال ششمین کنفرانس وجود داشت. بهترین پیشرفت‌های نرم‌افزاری سالانه توسط بچه‌ها در کنفرانس بین‌المللی "انفورماتیک مدرسه و مشکلات توسعه پایدار" که در سن پترزبورگ برگزار می‌شود، ارائه می‌شود، جایی که کار کودکان با دیپلم‌های درجه I و II ارزیابی می‌شود.

از برنامه های فردی به عنوان مواد آموزشی استفاده می شود.

برای گروهی از "طرفداران رایانه" به معنای خوب، و نه به معنای، به عنوان مثال، بازی های رایانه ای، دروس انتخابی هدفمند و دوره های ویژه با موضوعات زیر انجام می شود: یادگیری یک زبان برنامه نویسی اضافی، الگوریتم سازی غیر استاندارد. مسائل، مسائل المپیاد، نظریه گراف و غیره.

سوال 4 ... در دروس انتخابی ویژه چند نفر باید حضور داشته باشند؟

گروه های 6 تا 12 نفره.

هنگام کار روی یک نتیجه خاص (یعنی آمادگی برای یک المپیاد شهری، منطقه ای یا روسیه)، باید یک گروه 3 تا 6 نفره وجود داشته باشد. این کلاس ها در حال حاضر در حال آموزش هستند و در اینجا معلم بیشتر به عنوان یک مربی عمل می کند و نه به عنوان یک معلم. درس چگونه پیش می رود؟

موضوع نامگذاری شده است.

وظایف مربوط به این موضوع فهرست شده است.

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

الگوریتم حل به صورت شفاهی همراه با کودکان مورد بحث قرار می گیرد.

بچه ها برنامه را می نویسند ، معلم زمان را تنظیم می کند ، اجرای راه حل ها را ارزیابی می کند ، به جستجوی خطاها کمک می کند ، به کاستی های کارایی اشاره می کند (تعداد عملیات ، استفاده از RAM ، زمان راه حل).

سوال 5 ... در آمادگی برای المپیادها چه موضوعاتی را باید مطالعه کرد؟

پیش بینی همه چیز غیرممکن است، اما گروه های زیر از الگوریتم ها را می توان متمایز کرد:

الگوریتم بر روی اعداد صحیح

بازگشت.

مرتب سازی.

وظایف برشمرده شده

مسائل هندسی

روشهای عددی.

مدل سازی آماری

نمودارها و درختان

تبدیل متن

بیایید با جزئیات بیشتری موضوعات لازم برای مطالعه در آمادگی برای المپیادها را در نظر بگیریم. مطالعات نظری باید شامل تعاریف، اظهارات (در برخی موارد، لزوما همراه با شواهد) باشد.

الگوریتم بر روی اعداد صحیح

تقسیم پذیری

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

اولین اصلاح الگوریتم اقلیدسی (با تفریق)

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

وظایفی که هنگام مطالعه این موضوع باید به آنها پرداخته شود:

تعیین کنید که آیا چند اعداد همزمان هستند یا خیر

کسر کسر (عدد و مخرج کسر وارد می شود)

برنامه "ماشین حساب" را در کسرهای ساده بنویسید

اصلاح دوم الگوریتم اقلیدس با استفاده از تقسیم باقی مانده

جایی که r – باقیمانده تقسیم عدد بزرگتر بر عدد کوچکتر

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

چالش برای حل: مستطیل با طول ضلع a و b که در آن a و b اعداد طبیعی هستند و به مربع هایی با حداکثر مساحت بریده می شوند. اندازه مربع ها و تعداد کل آنها را تعیین کنید.

معادلات دیوفانتین

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

وظایفکه هنگام مطالعه این موضوع باید از هم جدا شوند:

وظایف مبادله پول با سکه هایی با ارزش مشخص.

وظایف انتقال خون

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

اعداد اول

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

اعداد دوقلو؛

اعداد کامل؛

سفره اولام;

شماره های دوستانه و غیره

حساب بلند

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

کارهای معمولی: عدد N را پیدا کنید! (N-factorial)، دوره کسری را تعیین کنید.

بازگشت

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

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

مرحله بعدی نقشه های بازگشتی است. ما با ساده ترین نقاشی ها شروع می کنیم، به عنوان مثال، کشیدن یک "عروسک تودرتو" ساده شده.

دانه های برف در سراسر صفحه می ریزد.

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

مجموعه های فراکتال برای کودکان بسیار جالب است: دستمال سفره و سفره Sierpinski، مدل ریه انسان Mandelbrot، فراکتال Harter-Haytway (که برای ما به عنوان خط شکسته اژدها شناخته می شود)، منحنی های هیلبرت، دانه برف Koch. بازگشت در اینجا آنقدر طبیعی است که هیچ کس سؤال نمی کند که آیا بدون آن امکان پذیر است یا خیر. و فقط اکنون، زمانی که هیچ کس در زیبایی و زیبایی بازگشت شک ندارد، می توانید به کارهایی بروید که طبق تعریف بازگشتی هستند. اینها وظایف زیر هستند: فاکتوریل یک عدد، توان N-امین یک عدد، gcd ( آ, ب)، تابع آکرمن، اعداد فیبوناچی، تبدیل اعداد از سیستم اعداد دهم به 2، یافتن حداکثر و حداقل در آرایه. به نظر می رسد بسیاری از وظایف را می توان با استفاده از بازگشت انجام داد. نکته اصلی این است که چشم اندازی از بازگشت در مسائلی ظاهر می شود که قبلاً به صورت بازگشتی حل نشده اند. به منظور تازگی، به عنوان مثال، در مسئله برش یک مستطیل به مربع هایی با حداکثر مساحت، پیشنهاد شده است که یک همراه گرافیکی بصری با استفاده از بازگشت ایجاد شود. و هنگام حل مشکلاتی مانند برج هانوی، بدون بازگشت مجدد، واقعا "بد" است. در این مورد، برنامه نمایشی و آموزشی "برج هانوی" به تحقق این امر و در عمل تسلط بر الگوریتم بازگشتی برای حل این مشکل کمک می کند.

مرتب سازی

بدون دانش الگوریتم های مرتب سازی، نمی توان در المپیادهای سطوح مختلف احساس راحتی کرد. مسائل را می توان هم به طور صریح با ذکر الگوریتم مرتب سازی فرمول بندی کرد و هم با استفاده از الگوریتم مرتب سازی در داخل راه حل. دو ساده‌ترین الگوریتم‌هایی که باید بدانید، مرتب‌سازی حبابی و مبادله‌ای (با جستجوی حداقل‌های متوالی) هستند. برای مقادیر کم داده، این دو روش کاملاً کافی است، اما هنگام کار با داده های اندازه گیری شده در ده ها و صدها کیلوبایت، دانش یکی از مرتب سازی های سریع ضروری است. اولویت ممکن است به Hoare Quick Sort داده شود که به صورت بازگشتی اجرا می شود. همچنین هنگام سازماندهی داده ها در فایل های حجیم باید با ترفندهایی آشنا باشید. کل فایل به تعدادی تکه تقسیم می شود که می توان آنها را با استفاده از QSORT مرتب کرد و سپس فایل های مرتب شده را بدون برنامه مرتب سازی ادغام کرد (به هر حال، این کار از نظر فنی بسیار مفید است و به دقت و برنامه نویسی خوب نیاز دارد. تکنیک).

شمارش گزینه ها

مسائل شمارش دسته بزرگی از مسائل المپیاد را تشکیل می دهند. شمارش با ساده ترین جستجو برای حداقل و حداکثر در یک آرایه تک بعدی یا یک عنصر با ویژگی های مشخص آغاز می شود. در مرحله بعد، تکرار جفت عناصر با استفاده از یک حلقه تو در تو، سپس تکرار سه عنصر با استفاده از یک چرخه سه گانه (مثلاً در مسئله یافتن سه نقطه در صفحه در میان N نقطه داده شده که یک مثلث را تشکیل می دهند، وجود دارد. با حداکثر مساحت). و اگر ترکیبات 4، 5، 6 و غیره را مرتب کنید. عناصر؟ چند سیکل مورد نیاز است؟ به نظر می رسد که الگوریتم هایی وجود دارند که به طور قابل توجهی جستجو را کاهش می دهند.

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

با حرکت یک شوالیه، دور صفحه شطرنج N * M بروید.

8 ملکه را روی یک صفحه شطرنج 8 * 8 قرار دهید تا یکدیگر را تهدید نکنند.

راهی برای خروج از پیچ و خم پیدا کنید و غیره.

همچنین لازم است به دانش آموزان توضیح داده شود که در صورت طولانی شدن زمان اجرای برنامه، محدودیت «عقب نشینی» ضروری است. به عنوان مثال، در یک مسئله شطرنج با اندازه تخته 8 * 8، این برنامه برای مدت طولانی اجرا شده است. اعمال تقارن، آینه کاری، تکمیل یک کار برای نصف یا یک چهارم صفحه شطرنج ممکن و حتی ضروری است.

مسئله کلاسیک "بازگشت" مسئله "کوله پشتی" است، سپس مشتقات این مسئله را می توان در نظر گرفت:

N عدد را به دو زیرمجموعه تقسیم کنید که از نظر مجموع به نزدیکترین آنها هستند.

از میان مجموعه‌ای از کلمات، حداکثر دنباله‌ای از کلمات را به ترتیب فرهنگ لغت انتخاب کنید.

مسائل ترکیبی نیز با شمارش همراه است. شما باید بر الگوریتم های ایجاد نظم واژگانی تسلط داشته باشید.

مشکلات هندسه

حداقل اجباری که باید هنگام حل مسائل هندسه بدانید شامل موارد زیر است:

تا بتوانیم معادله خط مستقیمی را که از دو نقطه می گذرد به فرم بیاوریم

تبر + با + C = 0;

قادر به تعیین اینکه آیا یک نقطه متعلق به یک خط مستقیم است یا یک قطعه.

برای اینکه بتوانید تعیین کنید که آیا دو خط مستقیم همدیگر را قطع می کنند یا نه، و اگر آنها را قطع می کنند، نقطه تقاطع آنها را تعیین کنید (برای این، تعیین کننده مرتبه 2 را محاسبه کنید).

بتوانید معادله ای از یک خط عمود بر هم بنویسید یا تعیین کنید که آیا یک خط بر دیگری عمود است (با استفاده از این ویژگی که حاصل ضرب اسکالر بردارهای عمود بر صفر برابر است).

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

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

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

ماژول مقدار عددی مساحت متوازی الاضلاع ساخته شده بر روی بردارهای داده شده را تعیین می کند.

مقدار صفر - موازی بودن بردارها.

علامت به این معنی است که یک بردار "به سمت چپ" یا "به سمت راست" نسبت به دیگری قرار دارد.

بردار حاصل، نرمال به صفحه بردارهای داده شده را تعریف می کند.

روشهای عددی

روش دوگانگی

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

به طور کلی این روش بهینه است.

حل سیستم معادلات خطی: روش کرامر، روش گاوس.

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

مشکل از المپیاد منطقه ای 94.

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

مدلسازی آماری (روش مونت کارلو).

دانستن این روش بسیار مفید است:

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

چه چیزی بیشتر است، کسرهای قابل لغو یا تقلیل ناپذیر؟ (فرمول بندی ریاضی: تخمین احتمال کاهش ناپذیری کسر تصادفی).

بهترین شرط برای افراد ساده ("کوانت" شماره 5.1987)؛

مشکلات ترکیبی

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

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

برنامه نویسی پویا

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

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

مشکل کلاسیک یافتن چنین کوتاه‌ترین مسیر در یک ماتریس عددی NxN A از A (1،1) تا A (n، n)، که در آن مجموع ارقام در سلول‌ها حداقل یا حداکثر بود.

یافتن زیررشته کلی حداکثر طول (مسئله ای که از مشکل واقعی مدرن زیست شناسی مولکولی در مورد اطلاعات ژنتیکی کلی در مولکول های DNA ناشی می شود).

نمودارها و درختان

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

الگوریتم های اصلی نمودار را تجزیه و تحلیل کنید:

جستجوی اول عمق (به عبارت دیگر، "عقب نشینی" یا brute-force with backtracking)؛

Breadth First Search (یا روش پر کردن)؛

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

الگوریتم فلوید برای یافتن کوتاه ترین مسیرها در یک نمودار بین همه جفت رئوس.

تبدیل متن

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

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

سوال 6 ... در حل مسائل المپیاد چه نکاتی را می توانید راهنمایی کنید؟

با فرض "مطالعه" بودن تئوری الگوریتم ها و تسلط بر مبانی برنامه نویسی، می توان موارد زیر را به رقیب توصیه کرد:

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

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

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

انتخاب یک زبان الگوریتمی نیز مهم است، به عنوان مثال، در یک برنامه Basic کار با گرافیک راحت تر است، در حالی که یک برنامه پاسکال یک مزیت سرعت دارد.

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

اساساً هر برنامه ای ساختاری دارد:

ورود داده

بلوک تسویه حساب

خروجی گرفتن نتیجه

قبل از برنامه نویسی بلوک محاسباتی، صحیح بودن I/O (با تحلیل احتمالی داده های اشتباه) را بررسی و تأیید کنید.

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

مشکل را برای حداکثر محدودیت های داده شده بررسی کنید (به عنوان مثال، اگر n  1000 داده شود، n = 1000 را بررسی کنید). نوع متغیرهای اعلام شده را پیگیری کنید (ترجیح است از نوع "long integer" برای توصیف متغیرهای عدد صحیح استفاده کنید).

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

به عنوان آخرین راه حل، اگر یک "هکر باحال" (متخصص باحال در بخش سیستم) هستید، برنامه "همسایه" را مانند مال خود اجرا کنید (احتمالاً هیچ کس متوجه نخواهد شد).

شما مجاز هستید که برگه های تقلب خود را داشته باشید (نه به صورت الکترونیکی) یا از زمان "آزاد" برای مطالعه ادبیات مرجع استفاده کنید.

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

سوال 7 ... برای آمادگی برای المپیادها از چه ادبیاتی باید استفاده کرد؟

این مقاله و همچنین منابع زیر.

A. Shen. برنامه نویسی: قضایا و مسائل، M. MTsNMO، 1995.

A.L.Brudno، L.I. Kaplan. المپیادهای برنامه نویسی مسکو، M: علم، 1990.

V. A. Dagen، G. K. Grigas. 100 مسئله برنامه نویسی، M: آموزش، 1993.

V.M.Bondarev، V.I.Rublinetsky، E.G. Kachko. مبانی برنامه نویسی، خارکف: فولیو، 1997.

V.M.Kiryukhin، A.V. Lapunov، S.M. Okulov. وظایف انفورماتیک المپیادهای بین المللی م: ABF، 1996.

N.M.Badin، S.G. Volchenkov، N.L. Dashnits. المپیادهای یاروسلاول در انفورماتیک. یاروسلاول، 1995.

S.M. Okulov. خلاصه کلاس های علوم کامپیوتر (الگوریتم های روی نمودار). کیروف، 1996.

A.V. Alekseev. المپیاد برای دانش آموزان مدرسه در علوم کامپیوتر. انتشارات کتاب کراسنویارسک، 1995.

A.S. Sipin، A.I.Dunaev. المپیادهای منطقه ای انفورماتیک. ولوگدا، 1994.

V. Pinaev. المپیاد شهری در برنامه نویسی. ریبینسک، 1998.

S.A. آبراموف. ساخت و سازهای ریاضی و برنامه نویسی. 1987.

سوال 1. چگونه حل مسائل المپیاد در علوم کامپیوتر را یاد بگیریم؟

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

سوال 2. برای عملکرد مناسب در المپیادهای انفورماتیک چند مشکل باید حل شود؟

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

بنابراین، از آنجایی که بسیاری از وظایف بسیار بسیار مشابه هستند، لازم است یاد بگیرید که چگونه مسائل را از کل محدوده حل کنید: مرتب سازی، برنامه نویسی پویا، محاسبات طولانی و غیره.

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

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

سوال 4. اگر ساعات برنامه برای آماده سازی دانش آموزان برای المپیاد کافی نیست، چگونه آنها را آماده می کنند؟

در مورد دو گزینه اول، همه چیز روشن است، اما باید درک از جانب رهبری مدرسه وجود داشته باشد. اغلب، بین معلمان "نبرد برای ساعت" وجود دارد و ممکن است در کلاس یا یک درس انتخابی برنامه نویسی ساعت قرار نگیرد.

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

سوال 5. من 25 (26، 30 ...) ساعت از حجم کار اصلی دارم، آیا واقعاً می توان با دانش آموزان در دایره برنامه نویسی مطالعه کرد؟

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

سوال 6. آیا دانش آموزان مدرسه می توانند خارج از ساعات مدرسه برای المپیادها آماده شوند و اگر چنین است، چگونه می توان این آمادگی را به بهترین نحو برگزار کرد؟

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

سوال 7. برای آمادگی باکیفیت دانش آموزان مدرسه برای المپیاد چه چیزی از معلم لازم است؟

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

روش شناسی آمادگی برای المپیادهای علوم کامپیوتر

مرتبط بودن موضوع

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

مشکلات پیش روی معلم:

1. بررسی اشکال جدید برگزاری المپیادها.

2. آشنایی با الگوریتم های حل مسائل المپیاد.

3. حضور خود وظایف.

4. آشنایی با زبان های برنامه نویسی.

5. زمان مطالعه، اشکال زدایی و تست وظایف.

6. آموزش سازماندهی صحیح فعالیت ها در المپیاد به دانش آموزان.

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

در اینجا برخی از ویژگی های آماده سازی دانش آموزان برای برنامه نویسی المپیاد :

· در برنامه درسی مدرسه چنین موضوعی "برنامه نویسی" و حتی چنین بخشی وجود ندارد. یعنی یادگیرنده باید انگیزه نسبتاً قوی خود را داشته باشد.

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

· تمرین مداوم تقریباً در سطح ورزشی است.

· هزینه های زیاد زمان، مدت المپیاد با تجزیه اغلب بیش از 6 ساعت است.

· الگوریتم ها و فرمول های مورد استفاده در حل اکثر مسائل فقط در دانشگاه ها مورد مطالعه قرار می گیرند.

البته آموزش سطوح بالاتر نیز برای معلمان ضروری است برای کار با دانش آموزان تیزهوش شرکت کننده در المپیادهای برنامه نویسی:

· احتمالاً تحصیلات دوم، دانشگاه تخصصی برنامه نویسی.

· معلمان IPC، دوره های آموزش زبان های برنامه نویسی، برنامه نویسی المپیاد.

· خود آماده سازی با استفاده از مواد از منابع اضافی.

اما حتی دانش خوب یک زبان برنامه نویسی تضمینی 100% برای برنده شدن دانش آموز حتی در یک مدرسه یا المپیاد منطقه ای نمی دهد.

ایده آموزشی

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

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

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

در سال 1964 V. Vroom "نظریه انتظارات" را ارائه کرد. او این را باور داشت انگیزه برای کار کارآمد و با کیفیت بالا به ترکیبی از سه عامل بستگی دارد - انتظارات یک فرد:

1. توقع اینکه تلاش ها به نتیجه مطلوب منجر شود.

2. انتظار اینکه نتایج مستلزم پاداش باشد.

3. توقع اینکه پاداش ارزش کافی داشته باشد.

هر چه انسان بیشتر ایمان داشته باشد که همه این انتظارات توجیه می شود، انگیزه عمل قوی تر خواهد بود. اگر ما کمی عبارت V. Vroom را در زمینه آموزشی تغییر دهیم، این چیزی است که به دست می آورید:

تئوری انتظار نشان می دهد که معلمان باید چه کاری انجام دهند تا انگیزه های قوی برای یادگیری دانش آموزان داشته باشند:

o به دانش آموزان بیاموزید که به نتایج مورد نیاز دست یابند و همه شرایط لازم برای این کار را ایجاد کنند.

o ایجاد ارتباط مستقیم بین عملکرد و ارزشیابی دانش آموز.

o نیازهای دانش آموزان را بررسی کنید تا بدانید چه پاداش هایی برای آنها ارزشمند است.

بر این اساس مکانیسم های انگیزش و عوامل اصلی اثربخشی مشوق ها را می توان به صورت زیر بیان کرد:

o آگاهی معلمان از نیازها، علایق، نیازهای دانش آموزان.

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

o فوریت پاداش.

o درجه ارضای انتظارات.

برای آماده شدن برای المپیادهای برنامه نویسی، می توانید با استفاده از سیستم تست، متدولوژی را اعمال کنید "NSUTS" ، بر اساس NSU توسعه یافته است که به شما امکان می دهد به سرعت بسیاری از این نکات را حل کنید.

فن آوری استفاده از سیستم "NSUTS »

این سیستم در https: // المپیک. ***** / nsuts-test / nsuts_new_login. cgi... وقتی روی این لینک کلیک می کنید به صفحه مجوز می رسیم که با وارد کردن نام کاربری و رمز عبور خود می توانید وارد سیستم شوید.

https://pandia.ru/text/78/392/images/image002_97.jpg "width =" 623 "height =" 258 src = ">

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

https://pandia.ru/text/78/392/images/image004_80.jpg "width =" 623 "height =" 306 ">

در برگه " کمک»می توانید یک دستورالعمل مختصر در مورد نحوه کار در سیستم بخوانید. بیایید نگاهی به محتوای این صفحه بیندازیم.

سیستم تست NSUTS توضیحات بسیار کوتاه

شما در سیستم تست خودکار NSUTS برای انجام و بررسی المپیادهای برنامه نویسی هستید. بخش فعلی در بالای صفحه نمایش داده می شود. در گوشه سمت راست بالا - نام المپیاد فعلی، نام تیم شما و دکمه خروج از کار با سیستم - " خروج».

در فصل " تور»می توانید دور فعلی المپیاد را انتخاب کنید.

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

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

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

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

گزینه های تالیف:

Visual C ++ 6.0
Visual C ++ 2005	cl وظیفه exe / EHsc / Ox. cpp / پیوند / STACK:
MinGW 5.1.4 (GCC 3.4.5)	c ++. exe - دیوار - Wl، ​​- پشته = - وظیفه O2. cpp
Freepascal 2.2.0	ppc386.exe - O2 - وظیفه Cs. پس
جاوا 1.6.0_07	javac وظیفه exe جاوا
در حال دویدنجاوا	java - Xmx480m - Xss32m - Djava. امنیت. مدیر - دوسر. زبان = en_US وظیفه
Borland Delphi 2006

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

در صف " نتیجه»نتیجه آزمایش نمایش داده می شود:

صف - راه حل در صف آزمایش است.

در حال حاضر تست ... در حال آزمایش است.

از حد مجاز کد منبع فراتر رفته - از محدودیت کد منبع برنامه فراتر رفته است.

خطای کامپایل - کامپایل انجام نشد (دلیل ارائه شده).

هنگامی که راه حل آزمایش می شود، وضعیت یکی از مقادیر زیر را می گیرد:

پذیرفته شده! - تصمیم صحیح تلقی می شود.

پاسخ اشتباه - پاسخ اشتباه در آزمون.

از محدودیت زمانی فراتر رفت - راه حل با زمان اختصاص داده شده پردازنده مطابقت نداشت.

مهلت زمانی - راه حل با زمان تعیین شده مطابقت نداشت.

خطای زمان اجرا - راه حل یک کد خطای غیر صفر را برگرداند.

از حد حافظه فراتر رفت - محلول در حد حافظه اختصاص داده شده قرار نمی گیرد.

بدون فایل خروجی - هیچ خروجی فایل وجود ندارد. txt

نقض امنیت - راه حل عملی را انجام داده است که توسط قوانین ممنوع است.

در این مورد، شماره آزمونی که در آن خطا رخ داده است (برای المپیادهای ACM) نشان داده می شود.

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

زمان پنالتی مجموع زمان پنالتی برای تمام مشکلات است. زمان جریمه برای یک کار در صورت عدم ارسال کار 0 است. اگر کار ارسال شود، زمان جریمه آن با فرمول محاسبه می شود:

time_ of_submitting_correct_solution + (تعداد تلاش های ناموفق * 20).

بخش " پرسش و پاسخ"برای ارتباط با هیئت داوران المپیاد در نظر گرفته شده است. می توانید از هیئت منصفه در مورد شرایط اشکال سؤال بپرسید یا به نادرست بودن عبارت اشکالات اشاره کنید.

ضمناً در صورتی که هیأت داوران تغییراتی را در شرایط مشکلات لازم بدانند، اصلاحات در این قسمت یا در اخبار منتشر خواهد شد.

اکنون که با اصول کار در سیستم آشنا شدیم، در نظر خواهیم گرفت: چگونه می توانم برای المپیاد یک وظیفه بگیرم.

در تب "تور"، تور المپیاد مورد نیاز را انتخاب کنید، به عنوان مثال، " آمادگی برای المپیاد سراسر روسیه 2010.03.21 (هندسه) "... پس از آن به تب "اخبار" رفته و روی لینک "شرط تور" کلیک کنید تا فایل MS Office Word حاوی وظایف ارائه شده برای حل این دور را دانلود کنید.

پس از حل مشکل، در برگه "Pass"، ما آن را برای تأیید ارسال می کنیم و تمام پارامترهای لازم (زبان، متن برنامه یا فایل با برنامه) را تنظیم می کنیم. نتایج بررسی را می توان در برگه "نتایج" یافت.

طبقات اصلی مشکلات مطرح شده در المپیادهای انفورماتیک

برای تکمیل موفقیت آمیز نه تنها المپیاد، بلکه وظایف درون کلاسی، شما نیاز دارید:

1. مسلط به زبان و محیط برنامه نویسی (در مورد ما Free Pascal است)، بتوان با استفاده از این زبان الگوریتم های مختلفی را ساخت و پیاده سازی کرد.

2. دارا بودن دستگاه های ریاضی لازم.

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

مشکلات برنامه نویسی المپیاد طیف بسیار گسترده ای از دانش را پوشش می دهد، اما بیشترین مواردی که با آن مواجه می شوند و بیشترین مشکل را ایجاد می کنند موارد زیر است:

1. وظایف با استفاده از ساختارهای داده پیچیده مانند آرایه ها، صف ها، پشته ها، لیست های پیوندی، و درختان.

2. نمودارها، به عنوان مجموعه ای از اشیاء با ارتباطات زیاد.

3. مسائل با استفاده از هندسه تحلیلی و بر اساس مفهوم «بردار».

4. مشکلات برنامه نویسی پویا.

بیایید این دسته از وظایف را با جزئیات بیشتری در نظر بگیریم.

وظایفی که از ساختارهای داده پیچیده مانند آرایه ها، صف ها، پشته ها، لیست های پیوندی و درختان استفاده می کنند.

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

در واقع، ساختارهای داده رایانه ای بر اساس انواع داده های اساسی مانند "char"، "integer"، "real" ساخته می شوند. در سطح بعدی آرایه ها قرار دارند که مجموعه ای از انواع داده های پایه هستند. سپس رکوردهایی هستند که گروهی از انواع داده ها هستند که توسط یکی از داده ها به آنها دسترسی پیدا می کند و در آخرین سطح که جنبه های فیزیکی ارائه داده ها دیگر در نظر گرفته نمی شود، به ترتیب قرار گرفتن داده ها توجه می شود. ذخیره شده و در آن جستجو می شود. اساساً، داده های فیزیکی با یک «ماشین داده» مرتبط هستند که نحوه دسترسی به اطلاعات برنامه شما را کنترل می کند. چهار "ماشین" از این قبیل وجود دارد:

1. صف

3. لیست پیوندی.

4. درخت دوتایی.

1) http: // ru. ویکیپدیا. org / wiki /% D0% A1% D1% 82% D1% 80% D1% 83% D0% BA% D1% 82% D1% 83% D1% 80% D1% 8B_% D0% B4% D0% B0% D0 % BD% D0% BD% D1% 8B% D1% 85.

2) http: // والرا. ***** / دلفی / ساختار / اخر. html

3) http: // www. ***** / informatika / پاسکال / struktury_dannyh.

4) تی کورمن. الگوریتم ها ساخت و ساز و تجزیه و تحلیل. ویرایش دوم صفحه 255

5) مسائل و راه حل ها http: // ***** / olimp / str_prb. php

نمودارها مانند مجموعه ای از اشیاء با اتصالات زیاد هستند.

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

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

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

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

1.http: // ***** / sng / index. shtml

2.http: // ***** / sng / 4 / index. shtml

3.https: // سایت ها. / سایت / vzsitgnovosibirsk / distancionnye-kursy / distancionnyj-kurs-graf

4.http: // کتاب. ***** / 10 / grap1021.htm

5.http: // ru. ویکیپدیا. org / wiki /% D0% A2% D0% B5% D0% BE% D1% 80% D0% B8% D1% 8F_% D0% B3% D1% 80% D0% B0% D1% 84% D0% BE% D0 % B2

6. مسائل و راه حل ها http: // ***** / olimp / gra_prb. php

مسائل با استفاده از هندسه تحلیلی و بر اساس مفهوم "بردار"

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

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

1) http: // ***** /؟ صفحه = lib_viewarticle & article_id = 12.

2) http: // ***** / مقاله. asp id_sec = 1 و id_text = 1332.

3) مسائل و راه حل ها http: // ***** / olimp / geo_prb. php

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

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

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

پایه های تئوری برنامه نویسی پویا توسط R. Bellman گذاشته شد. توجه داشته باشید که کلمه "برنامه نویسی" در نام فوق (برنامه نویسی پویا) و همچنین در "برنامه نویسی خطی" (برنامه نویسی خطی) به معنای نوشتن برنامه برای رایانه نیست.

برای حل یک مسئله بهینه سازی که در آن نیاز به ساخت یک راه حل با مقدار حداکثر یا حداقل (بهینه) برخی از پارامترها است، الگوریتم مبتنی بر برنامه ریزی پویا را می توان به صورت زیر فرموله کرد:

1) مسائل فرعی را انتخاب و توصیف کنید که از طریق حل آنها راه حل مورد نظر بیان می شود.

2) روابط تکراری (معادلات) را بنویسید که مقادیر بهینه پارامتر را برای مسائل فرعی به هم متصل می کند.

3) مقدار بهینه پارامتر را برای تمام مسائل فرعی محاسبه کنید.

4) با استفاده از اطلاعات دریافتی بهینه ترین راه حل را بسازید.

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

1) http: // ***** / وبلاگ ها / الگوریتم / 113108 /.

2) http: // www. ***** / المپیادها / Rules_Olympiads / Rules21.htm.

3) http: // ***** / برچسب /% D0% B4% D0% B8% D0% BD% D0% B0% D0% BC% D0% B8% D1% 87% D0% B5% D1% 81 % D0% BA% D0% BE% D0% B5% 20% D0% BF% D1% 80% D0% BE% D0% B3% D1% 80% D0% B0% D0% BC% D0% BC% D0% B8 % D1% 80% D0% BE% D0% B2% D0% B0% D0% BD% D0% B8% D0% B5 /

4) مسائل و راه حل ها http: // ***** / olimp / rec_prb. php

مؤسسه آموزشی شهری - مدرسه راهنمایی MUZHEVSKAYA به نام N. V. ARKHANGELSKY

"المپیادهای انفورماتیک: روش آمادگی"

مواد تهیه شده توسط:

معلم فناوری اطلاعات

گالیتسکایا ایرینا ویکتورونا

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

مشکلات پیش روی معلم:

· بررسی اشکال جدید برگزاری المپیادها.

· آشنایی با الگوریتم های حل مسائل المپیاد.

· حضور خود وظایف.

· آشنایی با زبان های برنامه نویسی.

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

· آموزش سازماندهی صحیح فعالیت ها در المپیاد به دانش آموزان.

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

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

در اینجا برخی از ویژگی های آماده سازی دانش آموزان برای برنامه نویسی المپیاد آورده شده است:

1. در برنامه درسی مدرسه چنین موضوعی "برنامه نویسی" وجود ندارد. آن ها کارآموز باید انگیزه نسبتا قوی خود را داشته باشد.

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

3. تمرین مداوم تقریباً در سطح ورزشی است.

4. هزینه های زیاد زمان، مدت المپیاد با تجزیه اغلب بیش از 6 ساعت است.

5. الگوریتم ها و فرمول های مورد استفاده در حل اکثر مسائل فقط در دانشگاه ها مطالعه می شوند.

البته برای کار معلمان با دانش آموزان مستعد شرکت کننده در المپیادهای برنامه نویسی، آموزش سطوح بالاتر نیز ضروری است:

· احتمالاً تحصیلات دوم، دانشگاه تخصصی برنامه نویسی.

· دوره های آموزش زبان های برنامه نویسی، برنامه نویسی المپیاد.

· خود آماده سازی با استفاده از مواد از منابع اضافی.

اما حتی دانش خوب یک زبان برنامه نویسی تضمینی 100% برای برنده شدن دانش آموز حتی در یک مدرسه یا المپیاد منطقه ای نمی دهد.

ایده آموزشی تجربه

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

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

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

در سال 1964 V. Vroom "نظریه انتظارات" را ارائه کرد. او معتقد بود که انگیزه برای کار مؤثر و با کیفیت به ترکیبی از سه عامل بستگی دارد - انتظارات فرد:

1. توقع اینکه تلاش ها به نتیجه مطلوب منجر شود.

2. انتظار اینکه نتایج مستلزم پاداش باشد.

3. توقع اینکه پاداش ارزش کافی داشته باشد.

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

تئوری انتظار نشان می دهد که معلمان برای داشتن انگیزه های قوی برای یادگیری دانش آموزان باید چه کاری انجام دهند:

· به دانش آموزان بیاموزید که به نتایج مورد نیاز دست یابند و تمام شرایط لازم را برای این امر ایجاد کنند.

· ارتباط مستقیمی بین عملکرد و ارزشیابی دانش آموزان ایجاد کنید.

· نیازهای دانش آموزان را بررسی کنید تا بدانید چه پاداش هایی برای آنها ارزشمند است.

بر این اساس مکانیسم های انگیزش و عوامل اصلی اثربخشی مشوق ها را می توان به صورت زیر بیان کرد:

1. آگاهی معلمان از نیازها، علایق، نیازهای دانش آموزان.

2. ایجاد ارتباط منصفانه و مستقیم بین نتایج و پاداش ها.

3. فوریت ثواب.

4. درجه ارضای انتظارات.

تکنولوژی را تجربه کنید

البته آمادگی برای المپیادها فرآیندی طولانی و پر زحمت است.

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

پیاده سازی را تجربه کنید

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

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

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

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

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

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

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

اثربخشی

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

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

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

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

در مراحل بعدی کار، وظایف پیچیده تر می شوند.

مشکل اضافه بار روانی و جسمی

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

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

بخش 1. مبانی ریاضی برنامه نویسی

بخش 2. تکنیک برنامه نویسی

1. مبانی زبان برنامه نویسی (Pascal, C) متغیرها و ساده ترین انواع داده ها، اندازه انواع. برنامه های خطی اپراتورهای شرطی چرخه ها رویه ها و عملکردها. انواع داده های پیچیده (آرایه ها، رشته ها، رکوردها، اشاره گرها، فایل ها).

2. آرایه ها آرایه های تک بعدی. آرایه های دو بعدی (ماتریس). آرایه های چند بعدی

3. رشته ها. عناصر عملیات واژگانی و تجزیه عملیات روی رشته ها. واژگان، شمارش نشانه ها در انواع مختلف. اعداد را از یک رشته استخراج کنید.

4. کار با فایل ها خواندن و نوشتن در یک فایل متنی. تبدیل داده های دریافتی از فایل به یک ساختار مناسب. کار با فایل های تایپ شده فایل های تایپ نشده بافر ورودی

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

6. محاسبات "طولانی" ذخیره اعداد در برنامه که در انواع استاندارد قرار نمی گیرند. عملیات حسابی روی اعداد "بلند". اعداد "طولانی" با قسمت اعشاری. استخراج ریشه با دقت معین.

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

بخش 3. الگوریتم ها، روش ها و اصول حل مسائل.

1. مفهوم پیچیدگی یک الگوریتم. تعیین پیچیدگی

2. الگوریتم های جستجو و مرتب سازی یک عنصر را در یک آرایه نامرتب جستجو کنید. جستجوی دودویی با کلید در یک آرایه مرتب (دوگانگی). جستجوی فیبوناچی در یک آرایه n بعدی مرتب شده جستجو کنید. k امین عنصر آرایه بزرگ را جستجو کنید. روش های مرتب سازی ساده ("حباب"، "انتخاب"، "درج"، "شمارش"). روشهای سریع ("سریع"، "ادغام"، "هرمی")، متعادل کردن درختان دوتایی. مرتب سازی به روش اسکوپ.

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

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

5. اصل برنامه نویسی پویا مفهوم، کاربرد. مقایسه با نیروی بی رحم

6. مفهوم الگوریتم های حریصانه، قابلیت کاربرد. مقایسه با بروت فورس و برنامه نویسی پویا.

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

8. تحلیل لغوی و نحوی مسئله «ماشین حساب». نمودارهای نحوی Backus-Naur شکل می گیرد. پشته و مدل تجزیه بازگشتی. ماشین های حالت محدود گرامر

9. وظایف با "پیچ و خم"

بخش 4. المپیادها در انفورماتیک

1. قوانین برگزاری المپیادها در برنامه نویسی

2. خطاهای معمولی و اشکال زدایی برنامه

3. تکنیک های المپیاد

به نظر من بخش 2 و 3 بیشترین ارزش را دارند.اگر برای یادگیری زبان برنامه نویسی مشکلی ندارید (تعداد زیادی کتاب در این زمینه وجود دارد) پس با الگوریتم ها کار دشوارتر خواهد بود. کتاب‌های زیادی نیز در این زمینه وجود دارد، اما اغلب آنها بیش از حد مملو از تئوری هستند و فقط در المپیادها تمرین لازم است. از منابع الکترونیکی در مورد الگوریتم ها می توانم کتاب SM Okulov و سایت algolist.manual.ru را توصیه کنم که کمتر از کتاب Okulov به مطالعه "المپیاد انفورماتیک" می پردازد، اما حاوی تعداد زیادی الگوریتم است که در کتاب نیست. اما بد نیست بدانید. به کار در حالت عادت کنید: نوشتن + اشکال زدایی در Borland Pascal / Borland C ++ و کامپایل (با تغییر اولیه ثابت ها) در Free Pascal / GNU C. کامپایلرهای جدید 32 بیتی محدودیت حافظه سخت ندارند و بسیار سریعتر کار کنید (تفاوت به ویژه در سرعت اجرای برنامه های 16 و 32 بیتی در P4 قابل توجه است). این تاکتیک دشوار با فقدان یک دیباگر مناسب در پلتفرم‌های جدید و سازگاری تقریباً کامل آنها با کامپایلرهای Borland توضیح داده می‌شود (در FP فراموش نکنید که فایل خروجی را ببندید).