5. Особливості ознайомлення з ефективністю алгоритмів, жадібними алгоритмами.

Алгоритм вважають ефективним, якщо всі його оператори досить прості для того, аби їх можна було точно виконати за скінченний проміжок часу з допомогою олівця та аркушу паперу.

Ми знаємо, що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв’язків задачі. Основними вимогами до ефективності алгоритмів є перш за все ефективність за часом та економне використання пам’яті.

Жадібний алгоритм на кожному кроці обирає варіант, який здається найкращим у даний момент. Цей вибір є остаточним і надалі не переглядається. Простота формулювання жадібних алгоритмів іноді наштовхує на думку про широку їх застосовність в програмуванні, проте в розв’язуванні багатьох практичних задач жадібний алгоритм не дає оптимального результату. Це положення слід проілюструвати достатньою кількістю прикладів.

Ознаки того, що задачу можливо вирішити за допомогою жадібного алгоритму:

1.Задачу можна розбити на підзадачі;

2.Величини, що розглядаються в задачі, можна дробити так само як і задачу на підзадачі;

3.Сума оптимальних рішень для двох підзадач дасть оптимальне рішення для всієї задачі.

7. Особливості вивчення алгоритмів обчислювальної геометрії.

Обчислювальна геометрія галузь комп'ютерних наук присвячена вивченню алгоритмів що описуюються в термінах геометрії.

Основним стимулом розвитку обчислювальної геометрії як дисципліни був прогрес у комп'ютерній графіці та системах автоматизованого проектування та автоматизованих систем технологічної підготовки виробництва, проте багато задач обчислювальної геометрії є класичними за своєю природою, і можуть з'являтись при математичній візуалізації.

Іншим важливим застосуванням обчислювальної геометрії є робототехніка (планування руху та задачі розпізнавання образів), геоінформаційні системи (геометричний пошук, планування маршруту), дизайн мікросхем, програмування станків з числовим програмним управлінням.

Основними розділами обчислювальної геометрії є:

Комбінаторна обчислювальна геометрія, чи також названа алгоритмічна геометрія, яка розглядає геометричні об'єкти як дискретні сутності.

3

При вивченні теми «Обчислювальна геометрія та числові методи» учні повинні знати:

- сутність векторного добутку та напрямку повороту;

- сутність умов перетину відрізків;

- алгоритми визначення площі простого многокутника, положення точки відносно простого

многокутника, опуклої оболонки, пари найближчих точок, пари найвіддаленіших точок;

- алгоритм метода виключення для розв‘язання алгоритмічних задач.

Учні повинні мати уявлення про:

- застосування поняття векторного добутку для реалізації алгоритмів розв‘язання геометричних задач.

Учні повинні вміти:

- застосовувати алгоритми визначення площі простого многокутника, положення точки відносно простого многокутника, опуклої оболонки, пари найближчих точок, пари

найвіддаленіших точок для реалізації конкретних задач;

На початку вивчення теми необхідно повторити матеріал з аналітичної геометрії, звернувши увагу на особливості представлення геометричних об’єктів в пам’яті комп’ютера. Слід відзначити, що вивчення теми вимагає знань з математики, які виходять за рамки шкільної програми (зокрема поняття векторного добутку).

Використання векторного добутку дозволяє одержати розв’язок задачі про напрямок кута повороту, дозволяє обґрунтувати формулу для обчислення площі многокутника.

де , .