Іі. Тематичне планування навчального матеріалу:

І рік навчання

Основи програмування мовою TURBO PASCAL (70 год.)

Тема 1. Мова програмування TURBO PASCAL(10 год.)

Поняття про мови програмування, їх класифікація. Мова програмування TURBO PASCAL.

Середовище програмування. Можливості використання вбудованого редактора.

Структура програми мовою TURBO PASCAL. Операції виведення.

Постійні та змінні величини. Типи постійних i змінних величин. Операції введення-виведення та присвоєння.

Стандартні математичні операції та функції. Запис математичних виразів.

Оформлення екрану при роботі з програмою. Коментарі в програмі.

Тема 2. Базові структури мови програмування(10 год.)

Оператори управління. Оператор розгалуження та безумовного переходу. Проста і складена умови.

Оператор множинного вибору.

Цикли. Організація циклів.

Тема 3. Робота з файлами(6 год.)

Текстові файли. Опрацювання текстових файлів.

Тема 4. Структуровані типи даних (14 год.)

Масиви. Одновимірний масив. Опрацювання елементів одновимірного масиву.

Двовимірний масив. Опрацювання елементів двовимірного масиву.

Організація пошуку елементів із заданими властивостями в масивах.

Найпростіші алгоритми сортування масивів: метод “бульбашки”, метод прямої вибірки.

Рядкові дані. Процедури та функції опрацювання рядкових величин.

Записи. Масиви записів.

Тема 5. Процедури та функції(10 год.)

Підпрограми. Процедури в мові TURBO PASCAL. Структура процедури. Підпрограми-функцiї. Структура функції. Поняття рекурсії.

І рік навчання

Основи програмування мовою C++

Тема 1. Мова програмування С++ (10 год.)

Поняття про мови програмування, їх класифiкацiя. Мова програмування С++. Середовище програмування Borland C++ версії 3.1. Можливості використання вбудованого редактора. Структура програми мовою С++. Використання заголовкових файлів.

Операції виведення. Виведення текстових і числових значень. Постійні та змінні величини. Типи постійних i змінних величин. Операції введення та присвоєння. Стандартні математичні операції й основні математичні функції. Правила запису математичних виразів.

Оформлення екрану при роботі з програмою. Коментарі в програмі.

Тема 2. Базові структури мови програмування (10 год.)

Оператори управління. Оператор безумовного переходу.

Оператор розгалуження. Проста і складена умови. Тернарний оператор. Оператор множинного вибору.

Цикли. Організація циклів. Керування циклами за допомогою операторів break, continue.

Тема 3. Робота з файлами(4 год.)

Текстові файли. Створення й опрацювання текстових файлів.

Тема 4. Структуровані типи даних(16 год.)

Масиви. Одновимірний масив. Опрацювання елементів одновимірного масиву.

Двовимірний масив. Опрацювання елементів двовимірного масиву.

Організація пошуку елементів із заданими властивостями в масивах. Найпростіші алгоритми сортування масивів: метод “бульбашки”, метод прямої вибірки. Рядкові данi (символьні масиви). Функції обробки рядкових величин. Структури. Масиви структур. Вказівники та масиви. Операції над вказівниками.

Тема 5. Функції (10 год.)

Пiдпрограми-функцiї. Структура функції. Область видимості змінних. Локальні та глобальні змінні. Передача значень копіюванням та за адресою. Автоматичні та статичні змінні. Поняття рекурсії.

Практикум (20 год.)

Розроблення та аналіз алгоритмів

ІІ рік навчання

Спільна частина програми для обох груп програмістів

Тема 6. Динамічне виділення пам’яті (10 год.)

Потреба у динамічному виділенні пам’яті. Виділення та звільнення пам’яті. Контроль за виділенням пам’яті.

Задачі на опрацювання великих обсягів даних. Опрацювання лінійних і двовимірних масивів невідомого розміру.

Тема 7. Опрацювання довгих чисел (10 год.)

Поняття довгого числа. Використання числових і символьних масивів для подання довгого числа. Математичні дії з довгими числами: додавання, множення, віднімання, остача від ділення. Перевірка довгих чисел на простоту. Обчислення факторіалів і степенів з використанням довгих чисел.

Тема 8. Елементи обчислювальної геометрії (10 год.)

Основні формули аналітичної геометрії. Знаходження довжини відрізку в n-вимірному просторі. Відстань від точки до прямої. Координати точок перетину відрізків і прямих. Рівняння прямої, кола, площини.

Знаходження площі багатокутника. Метод триангуляції. Метод трапецій.

Перевірка опуклості багатокутника.

Векторна геометрія. Колінеарність векторів. Перевірка належності точок прямій.

Ліві та праві трійки векторів. Знаходження порядку обходу вершин опуклого багатокутника. Задача про Едемський сад.

Задачі мінімізації в геометричній інтерпретації.

Тема 9. “Жадібні” алгоритми (10 год.)

Поняття “жадібного” алгоритму. Теоретичні основи “жадібних” алгоритмів. Переваги та недоліки “жадібних” алгоритмів.

Класичні приклади “жадібних” алгоритмів. Задача про вкладання рюкзака.

Розв’язання задач із застосуванням “жадібних” алгоритмів. Геометричні, транспортні, економічні задачі.

Тема 10. Синтаксичний розбір і лексичний аналіз виразів(10 год.)

Розділення виразів на складові частини. Опрацювання текстів і сортування окремих елементів тексту.

Аналіз, перетворення й обчислення виразів. Перевірка коректності запису математичних виразів. Калькуляторні задачі.

Постфіксна система запису математичних виразів (польська нотація). Алгоритм RРN-калькулятора.

Практикум (20 год.)

ІІІ рік навчання

Тема 11. Алгоритми на графах (10 год.)

Основні поняття теорії графів. Матричне подання графів. Матриця зв’язності та матриця відстаней на графі. Пошук найкоротших шляхів та оптимальних маршрутів у графах. Алгоритм Дейкстри. Метод Беллмона. Знаходження мінімального остовного дерева графа за алгоритмом Прима-Краскала. Перевірка зв’язності графів. Алгоритм Тарьяна знаходження найменшого спільного пращура. Поняття про NP-повні задачі. Аналіз алгоритмів розв’язання NP-повних задач. Задача про найменше вершинне покриття.

Тема 12. Комбінаторні задачі (10 год.)

Основні поняття комбінаторики. Поняття комбінаторної задачі. Перестановки. Підрахунок кількості можливих перестановок. Організація перестановок. Розміщення та сполучення. Підрахунок кількості. Організація знаходження всіх можливих розміщень і сполучень. Методи організації повного перебору.

Тема 13. Методи перебору з відсіканням гілок (10 год.)

Метод гілок і границь. Обмеження варіантів перебору. Алгоритми пошуку з повертанням. Задача про розстановку дужок. Задача про гамільтонові шляхи на графі.

Пошук у ширину на графах. Пошук в глибину на графах.

Тема 14. Динамічне програмування (10 год.)

Поняття про динамічне програмування. Основні підходи до розв’язання задач методом динамічного програмування. Матричне числення. Перемноження декількох матриць. Знаходження найбільшої спільної підпослідовності множин. Визначення оптимальної тріангуляції багатокутника. Задачі лінійного програмування. Симплекс-метод розв’язання задач економічного планування.

Тема 15. Пошук та сортування (10 год.)

Алгоритми пошуку: бінарний пошук, алгоритм Бойера-Мура, алгоритм ЗСУВ-І, наближений пошук.

Методи впорядкування масивів: вставка, “вичерпування”, метод Шелла, пірамідальне упорядкування.

Швидке впорядкування. Опис і робота швидкого впорядкування.

Практикум (20 год.)