Основи алгоритмізації та програмування Етапи розвязування задач на компютері

Exit Звідкіля беруться задачі? Чи можна назвати таке формулювання задачею? (перейдіть на наступний слайд). Одні скажуть, що задачі беруться із підручника, хтось скаже, що задачі беруться із життя, інші - що, їх складає вчитель. Напевно знайдуться і інші думки. Кожен буде по-своєму правий. Але давайте дамо відповідь на питання: – що собою являє задача і для чого потрібні задачі взагалі? У повсякденному житті людини постійно виникають певні проблеми, які потребують рішення. Наприклад, ви проживаєте у Валках і вам необхідно встигнути на десятигодинний поїзд, що відправляється із станції Ковяги.

Exit Постановка задачі Але це ще не задача, а тільки її формулювання. Крім формулювання задача містить ще розвязок – систему дій, які дозволяють із вхідних даних отримати результат. Іншими словами, задача є процесом вирішення певної проблеми. І складається вона із умови та розвязку. Виходячи із свого досвіду, ви, напевно, скажете, що ні. Бо в задачі повинно бути вказано, який ми очікуємо результат (те, що ми знаходимо) та, крім цього, описані вхідні дані (те, що нам дано). Спробуємо це зробити. Ось що у нас вийшло: "Житель міста Валки вирушає у дорогу до селища Ковяги о 9 годині 45 хвилин на автомобілі, який матиме середню швидкість руху 70 км/год. Відстань між Валками та Ковягами становить 10 км. Чи встигне він на поїзд, який відходить від станції Ковяги о 10 годині 00 хвилин?" Формулювання умови задачі називають постановкою задачі.

Exit Вимоги до умови задачі – повнота вхідних даних Чи можна знайти однозначне рішення задачі з такою умовою? Очевидно, що ні, бо той, хто розвязує задачу, не знає о котрій годині виїздить житель. Значить, для того, щоб задача мала розвязок, необхідно в її умові вказати необхідну кількість вхідних даних для отримання результату. Постановка задачі – досить непросте завдання. Справа в тому, якщо ви вкажете нечітко або не в повному обсязі вхідні дані, або нечітко опишете очікувані результати, то задача не матиме розвязку, або він буде неправильним, навіть при правильному шляху її розвязання. Розглянемо неповний варіант постановки нашої задачі: "Житель міста Валки вирушає у дорогу до селища Ковяги на автомобілі, який матиме середню швидкість руху 70 км/год. Відстань між Валками та Ковягами становить 10 км. Чи встигне він на поїзд, який відходить від станції Ковяги о 10 годині 00 хвилин?"

Exit Шкода від зайвих вхідних даних Умова задачі може також мати зайві вхідні дані. Вони безпосередньо не впливають на результат, але можуть відволікати при розвязуванні задачі. Наприклад, В цій умові є зайві дані. По-перше – це колір автомобіля. Будь-кому зрозуміло, що час прибуття в пункт призначення не залежить від кольору транспортного засобу. І, якщо цю умову розвязувач задачі, посміхнувшись, відразу відкине. То над другою – кількістю поворотів – він, мабуть, на певний час замислиться. " Житель міста Валки вирушає у дорогу до селища Ковяги о 9 годині 45 хвилин на автомобілі червоного кольору, який матиме середню швидкість руху 70 км/год Відстань між Валками та Ковягами становить 10 км, а на шляху до Ковяг 10 поворотів. Чи встигне він на поїзд, який відходить від станції Ковяги о 10 годині 00 хвилин?"

Exit Оптимізація умови задачі Взагалі, крім вказаних в умові задачі є ще інші зайві дані. Опрацювавши та спростивши умову, отримаємо наступне формулювання: "Обєкт рухається від пункту А в пункт В із середньою швидкість 70 км/год. Відстань між пунктами А та В становить 10 км. Визначити, чи прибуде він у пункт В не пізніше 10-ї години, якщо вирушив о 9,75 год."

Exit Висновок щодо умови задачі В умові задачі повинна бути вказана достатня кількість вхідних даних, що необхідні для отримання результату. Зайві дані вказувати не бажано.

Exit Розв'язок задачі Як вже було вказано, задача складається із умови та розвязку. Коли постановка задачі виконана з дотриманням вказаних раніше правил, необхідно знайти шлях, який веде від вхідних даних до результату. Цей шлях і буде розвязком задачі. Вхідні даніРезультатРозв'язок

Exit Побудова математичної моделі На початку розвязування задачі знаходять залежності між вхідними даними та результатом і записують їх за допомогою різних математичних формул та виразів. Наприклад, у нашому випадку це буде мати наступний вигляд: Результат визначатиметься формулою: P=(t pr <10), де P – це подія, що матиме значення "так" або "ні" в залежності від виконання умови (t pr <10), t pr – час прибуття обєкту у пункт В За цією формулою, якщо час прибуття обєкту у місце призначення буде менше 10 годин, то результат – змінна Р отримає значення "так", інакше її значення буде "ні".

Exit Проміжні величини Якби в умові задачі було вказано час прибуття, то ми відразу отримали б результат, але ж цей час необхідно визначити. В нашому випадку величина t pr не є ні результатом, ні вхідною величиною. Такі величини називають проміжними. Щоб її визначити скористаємося формулою: t pr =t vid +(S/V), де t vid – час відправлення обєкту із пункту А (задано в умові задачі), S – відстань між пунктами (задано в умові задачі), V – середня швидкість руху обєкту (задано в умові задачі). Як бачимо, всі величини, із яких отримується значення проміжної величини t pr, задані в умові задачі. Але це ще не її розвязок. Розвязок буде тоді, коли на основі цієї моделі буде побудовано, а потім виконано алгоритм розвязання задачі. Ці дві формули (P=(t pr <10 ), t pr =t vid +(S/V)), що повязують результати із вхідними даними, являють собою математичну модель поставленої задачі.

Exit Алгоритм розвязування задачі Алгоритмом називають послідовність дій, яка веде від вхідних даних до результату. 1) t vid =9,75 2) S=10 3) V=70 4) t pr =t vid +(S/V) 5) P=(t pr <10) Далі, якщо ми виконаємо всі наведені дії у заданій послідовності, то ми отримаємо результат, що і буде розвязком задачі. Запишемо його, використовуючи формули нашої математичної моделі:

Exit Виконавець алгоритму Але, дайте відповідь на питання: будь-хто зможе виконати наведений алгоритм? Певно, що ні. Такий алгоритм розрахований на людину, яка має навички виконання елементарних математичних операцій. В нашому випадку – додавання, ділення та порівняння. Крім того виконавець (той, що виконує алгоритм) повинен розуміти ту мову, якою алгоритм написаний. У нашому випадку це мова математичних формул. 1) t vid =9,75 2) S=10 3) V=70 4) t pr =t vid +(S/V) 5) P=(t pr <10)

Exit Етапи розвязування задачі виконавцем-людиною Процес розвязування задачі людиною складається із таких етапів: 1. Постановка задачі. 2. Побудова математичної моделі задачі. 3. Створення алгоритму розвязання задачі. 4. Виконання алгоритму.

Exit Використання компютера для розвязання задачі Розглянуті раніше етапи розраховані на те, що задачу виконуватиме людина. Але ж зараз ми маємо можливість для розвязування задач використовувати компютер. Тому спробуємо розглянути етапи розв'язування задачі за допомогою компютера. Якщо для розвязування задачі ми вирішили використати компютер, то четвертий етап – виконання алгоритму слід деталізувати.

Exit Вибір мови програмування Спочатку відповімо на питання: чи "зрозуміє" компютер написаний нами алгоритм? Ні. Він його не зрозуміє, бо компютер розуміє лише спеціальні мови. Їх називають мовами програмування. Значить, необхідно алгоритм перекласти на мову програмування. На сьогодні існує велика кількість компютерних мов, тому наступним кроком після складання алгоритму повинен бути вибір мови, якою буде записана програма – алгоритм для компютера.

Exit Складання програми Складання програми є перекладом алгоритму на певну мову програмування. Програміст повинен, по-перше, розуміти мову, якою подано алгоритм, а по-друге – досконало знати мову програмування, на яку він буде перекладати цей алгоритм. Цей процес нагадує роботу перекладача, який дає можливість зрозуміти невідому вам мову. Людина, яка виконує роль перекладача алгоритму на машинну мову називається програмістом.

Exit Трансляція програми Коли ми казали, що компютер "розуміє" мову програмування, ми були не дуже щирі. Насправді він "розуміє" лише мову машинних кодів, які розміщуються в оперативній памяті компютера і безпосередньо дають вказівки процесору, який до них звертається, на виконання певних дій. Тому одним перекладачем-програмістом тут не обмежишся. Необхідний ще один переклад – переклад з мови програмування на мову машинних кодів. Такий переклад називають трансляцією програми. Для трансляції програми використовують спеціальні програми-перекладачі, які отримали назву транслятори.

Exit Налагодження програми, контрольний прорахунок Налагодження програми є процесом виявлення та виправлення помилок. Засобом виявлення помилок є контрольний прорахунок.

Exit Синтаксичні помилки Під час трансляції відбувається процес компіляції – переведення вказівок програми у відповідну групу машинних кодів. При цьому, якщо транслятор знаходить вказівку програми, яка містить синтаксичну помилку, то припиняє процес трансляції та повідомляє про це програміста. Сам транслятор синтаксичні помилки не виправляє, бо це задача програміста, який повинен внести в програму відповідні виправлення. Виправлення вносяться до тих пір, поки програма не буде повністю відтрансльована.

Exit Семантичні помилки Іноді помилки виникають не під час трансляції програми, а під час її виконання. Для виявлення таких помилок виконують контрольний прорахунок за вхідними даними. При цьому нерідко зявляються помилки часу виконання, наприклад, ділення на нуль. Кажуть, що це є результатом семантичних, тобто смислових помилок. Щоб виявити та виправити всі семантичні помилки, необхідно виконати цілий ряд контрольних прорахунків, для яких відомі результати.

Exit Цікаве питання І тут виникає питання: для чого складати програму розвязку задачі, коли вже є її результати? В такій задачі результат залежить від того, які числові значення ми надамо змінним V, S, t та t 0 А при різних значеннях цих величин будуть різні результати. Справа в тому, що для розвязання таких задач яку ми розглядали, компютери звичайно не використовуються. Компютер корисний там, де вхідні дані можуть приймати різні значення. Наприклад, "Обєкт рухається від пункту А в пункт В із середньою швидкість V км/год. Відстань між пунктами А та В становить S км. Визначити, чи прибуде він у пункт В не пізніше t-ї години, якщо вирушив о t 0 год."

Exit Експлуатація програми Якщо задача побудована за принципом використання різних значень вхідних величин, то вона може використовуватися не один, а багато, навіть безліч, разів. Процес використання програми для одержання результатів називається експлуатацією програми. Експлуатація програми – останній із етапів розвязування задачі.

Exit Підсумки Відповідно до всього, що ми розглянули, робимо висновок, що процес розвязування задач з допомогою компютера складається із наступних етапів: 1. Постановка задачі.Постановка задачі. 2. Побудова математичної моделі.Побудова математичної моделі. 3. Побудова алгоритму.Побудова алгоритму. 4. Вибір мови програмування.Вибір мови програмування. 5. Складання програми.Складання програми 6. Трансляція програми.Трансляція програми. 7. Налагодження програми та контрольний прорахунок.Налагодження програми та контрольний прорахунок. 8. Експлуатація програми.Експлуатація програми.

Exit Контрольні питання 1. Звідкіля беруться задачі? 2. Що таке постановка задачі? 3. Які вимоги ставляться до умови задачі? 4. Для чого оптимізують умову задачі? 5. Що являє собою розв'язок задачі? 6. Що являє собою математична модель задачі? 7. Як ви розумієте поняття алгоритму? 8. Які існують етапи розв'язування задачі виконавцем-людиною? 9. Що таке програма? За допомогою чого вона створюється? 10. Як називають людину, що створює програми? Що він повинен знати та вміти? 11. Що таке трансляція програми? Як ви розумієте поняття "транслятор"? 12. Що таке налагодження програми? 13. Для чого виконують контрольний прорахунок? 14. Що таке експлуатація програми?