Міністерство освіти і науки України
Національний технічний університет України
«Київський політехнічний інститут»
Факультет електроніки

Затверджую
Директор (декан)
факультету електроніки
_________  Жуйков В.Я.
(підпис)
«____»___________ 2015 р.

        Алгоритмізація і програмування       
(назва навчальної дисципліни)

Програма
навчальної дисципліни
підготовки                        бакалавр                            
(назва освітньо-кваліфікаційного рівня)
напряму     6.050902 Радіоелектронні апарати     
(шифр і назва)
спеціальності     8.05090201, 7.05090201                 
Радіоелектронні апарати та засоби    
(шифр і назва)
(шифр за ОПП НФ-04)

Ухвалено методичною комісією
____________________________
(назва інституту/факультету)
Протокол від _____ 2015 р. № ___
Голова методичної комісії
_________  __________________
(підпис)                                  (ініціали, прізвище)
«____»___________ 2015 р.

Київ – 2015

РОЗРОБНИКИ ПРОГРАМИ:

Доцент кафедри КЕОА Лебедев Д.Ю.                                                              
(підпис)
Старший викладач кафедри КЕОА Губар В.Г.                                               
(підпис)
Асистент кафедри КЕОА Варфоломєєв А.Ю.                                                 
(підпис)

Програму затверджено на засіданні кафедри
конструювання електронно-обчислювальної апаратури

Протокол від 11 червня 2015 року № 22

Завідувач кафедри
                            О.М. Лисенко
(підпис)
«___» _______________ 2015 р.

Ó НТУУ «КПІ», 2015 рік

Вступ

Програму навчальної дисципліни алгоритмізація і програмування складено відповідно до освітньо-професійної програми підготовки бакалавр напряму 6.050902 «Радіоелектронні апарати» (7.05090201, 8.05090201 «Радіоелектронні апарати та засоби»).
Навчальна дисципліна належить до циклу природничо-наукової підготовки.
Предмет навчальної дисципліни основи програмування мовою Си, алгоритмізація, основи об’єктно-орієнтованого програмування та мови C++.
Міждисциплінарні зв’язки: до забезпечуючи дисциплін відносяться такі предмети, що вивчаються протягом навчання у закладах середньої освіти – математика, інформатика. У свою чергу дана дисципліна забезпечує необхідними знаннями студентів для вивчення таких предметів, як “Алгоритмізація та програмування - 1”, “Алгоритмізація та програмування - 3”, “Системне програмування та керування конструюванням БД”, “Програмне забезпечення розподільних ІОС”.
Мета та завдання навчальної дисципліни
1.1. Мета навчальної дисципліни.
Метою навчальної дисципліни є формування у студентів здатностей програмування на мовах високого рівня, розвинення навичок розробки програмних рішень, підготовка студентів як спеціалістів, що володіють методами досліджень та аналізу виробничих процесів з використанням ПЕОМ.
1.2. Основні завдання навчальної дисципліни.
Згідно з вимогами освітньо-професійної програми студенти після засвоєння навчальної дисципліни мають продемонструвати такі результати навчання:
Типові задачі діяльності та проблеми, вирішенню яких повинен навчитися студент полягають у наступному:

• декомпозиція поставленої задачі з метою формування модулів програми та розробки протоколів та інтерфейсів взаємодії між ними;
• опанування основами оптимiзацiї та налагодження програмного забезпечення;
• вивчення правил оформлення документації на програмне забезпечення, в тому числі самого тексту програми;

Завдання вивчення дисципліни полягають у отриманні студентами наступних знань, навичок та вмінь:

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

Структура навчальної дисципліни

На вивчення навчальної дисципліни відводиться 210 годин / 5,5 кредити ECTS.
Навчальна дисципліна містить 3 кредитні модулі:

• Алгоритмізація та програмування – 1
• Алгоритмізація та програмування – 2
• Алгоритмізація та програмування – 3

Рекомендований розподіл навчального часу

Зміст навчальної дисципліни

Кредитний модуль 1.
Тема 1.1. Мови програмування. Класифікація. Історія виникнення.
Тема 1.2. Внутрішня організація комп’ютера. Загальні поняття про пам’ять комп’ютера.
Тема 1.3. Системи числення і основні дії в них.
Тема 1.4. Загальне знайомство з мовою програмування С.
Тема 1.5. Препроцесор. Компілятор.
Тема 2.1. Прості типи, розміри типів, декларації, класи пам'яті.
Тема 2.2. Вивідні типи (масив, вказівник).
Тема 2.3. Оператори.
Тема 2.4. Приведення типів, пріоритет операцій та порядок обчислень.
Тема 3.1. Інструкції та блоки. Конструкція if-else.
Тема 3.2. Інструкція перемикач switch. Інструкція переходу goto.
Тема 3.3. Цикли while, for, do-while.
Тема 4.1. Структура програми.
Тема 4.2. Способи передачі параметрів. Повернення значення з функції.
Тема 4.3. Області дії ідентифікаторів.
Тема 4.4. Рекурсія та рекурсивні функції.
Тема 5.1. Одно-, дво- та багатомірні масиви.
Тема 5.2. Вирази та арифметичні операції із вказівниками.
Тема 5.3. Використання модифікатора const із вказівниками.
Тема 5.4. Зв’язок між вказівниками та масивами.
Тема 5.5. Масиви покажчиків. Покажчик на функцію.
Тема 5.6. Динамічне виділення пам'яті.
Тема 6.1. Використання Arduino IDE.
Тема 6.2. Підключення елементів управління та візуалізації в Arduino.
Тема 6.3. Аналого-цифрове перетворення.
Тема 6.4. Передача даних на Arduino з ПК через послідовний порт.
Тема 7.1. Файли та потоки.
Тема 7.2. Файли із послідовним доступом.
Тема 7.3. Файли із довільним доступом.
Тема 7.4. Стандартні потоки. Зв’язок із консольним вводом-виводом.
Тема 8.1. Функції ввода-виводу.
Тема 8.2. Математичні функції.
Тема 8.3. Функції роботи зі строками та послідовністю байтів.
Тема 8.4. Функції роботи з часом та датами.
Тема 9.1. Функції зі змінною кількістю аргументів.
Тема 9.2. Аргументи командної строки.
Тема 9.3. Налагодження програм. Вбудовані макроси.

Кредитний модуль 2.
Тема 1. Загальні відомості про алгоритми. Поняття алгоритму. Графічне зображення алгоритму.
Тема 2. Динамічні масиви, списки, черга, стек.
Тема 3. Дерева
Тема 4. Сортування
Тема 5. Пошук
Тема 6. Графи
Тема 7. Динамічне програмування

Кредитний модуль 3.
Тема 1. Загальні відомості про об’єктно-орієнтоване підхід.
Тема 2. Класи та об’єкти.
Тема 3. Контроль доступу до об’єкта. Посилання.
Тема 4. Конструктори і деструктори. Робота з динамічною пам’яттю.
Тема 5. Перевантаження функцій та операторів.
Тема 6. Наслідування. Віртуальні функції.
Тема 7. Множинне наслідування. Абстрактні класи. Віртуальне наслідування.
Тема 8. Шаблони та стандартна бібліотека шаблонів (STL).
Тема 9. Обробка виняткових ситуацій. Простори імен.

Рекомендована тематика практичних (семінарських) занять

Приблизна тематика практичних занять за кредитним модулем 1:

• Константи, прості типи, оператори, вирази.
• Прості типи, розміри типів, декларації, класи пам'яті.
• Вивідні типи (масив, вказівник).
• Оператори.
• Приведення типів, пріоритет операцій та порядок обчислень.
• Механізми управління потоком
• Інструкції та блоки. Конструкція if-else.
• Інструкція перемикач switch. Інструкція переходу goto.
• Цикли while, for, do-while.
• Функції.
• Способи передачі параметрів. Повернення значення з функції.
• Вказівники, масиви та функції.
• Одно-, дво- та багатомірні масиви.
• Вирази та арифметичні операції із вказівниками.
• Використання модуля Arduino Leonardo.
• Рекурсія та рекурсивні функції.
• Використання модифікатора const із вказівниками.

Приблизна тематика практичних занять за кредитним модулем 2:

• Динамічні масиви, черга, стек.
• Дерева
• Сортування
• Пошук
• Графи

Приблизна тематика практичних занять за кредитним модулем 3:

• Декларації в C++. Створення нових типів даних в C++. Потоковий ввід/вивід C++.
• Класи та об’єкти. Способи опису класів. Створення об’єктів. Звернення до атрибутів і методів об’єктів.
• Класи – конструктори і деструктори. Конструктори за замовчуванням.
• Прототипи функцій і контроль відповідності типів. Вбудовані функції. Параметри-посилання. Модифікатор const. Динамічний розподіл пам’яті за допомогою new і delete.
• Перевантаження функцій і операторів.
• Розподіл пам’яті. Проблеми при явному розподіл пам’яті в С++, способи їх вирішення. Посилання і вказівники.
• Похідні класи, наслідування. Наслідування, види наслідування. Віртуальні методи. Абстрактні класи. Множинне наслідування.
• Шаблони. Поняття шаблону. Функції-шаблони. Шаблони класів. Приклади використання.
• Стандартна бібліотека шаблонів (STL).
• Обробка помилок та виняткових ситуацій.

Рекомендований перелік лабораторних робіт (комп’ютерних практикумів)

Приблизний перелік лабораторних робіт за кредитним модулем 1:

• Вказівники, масиви та функції. Зв’язок між вказівниками та масивами.Масиви покажчиків. Покажчик на функцію.
• Динамічне виділення пам'яті. Структури, об'єднання, перелічення. Декларація та ініціалізація структур. Доступ до елементів структур.
• Масиви, вказівники та структури. Об’єднання. Бітові поля. Перелічення. Перевизначення типів (typedef). Використання структур та об’єднань разом з функціями.
• Файли та потоки.Файли із послідовним доступом.Файли із довільним доступом. Стандартна бібліотека функцій.
• Функції ввода-виводу. Математичні функції. Функції роботи зі строками та послідовністю байтів.
• Робота з модулем Arduino Leonardo.
• Функції зі змінною кількістю аргументів. Аргументи командної строки.

Приблизний перелік комп’ютерних практикумів за кредитним модулем 3:

• Класи та об’єкти. Розподіл пам’яті.
• Перевантаження функцій та операторів.
• Наслідування.
• Шаблони.
• Стандартна бібліотека шаблонів (STL).
• Простори імен.
• Обробка помилок та виняткових ситуацій.

Рекомендовані індивідуальні завдання

За першим кредитним модулем дисципліни передбачено ДКР.
Тематика індивідуальних завдань має наступні напрями:

• Робота з файловими потоками та збереження даних у бінарному вигляді.
• Функції зі змінною кількістю аргументів. Аргументи командної строки
• Робота з текстовою базою даних.
• Робота з бінарними потоками.
• Програмна реалізація моделі складної системи.

За третім кредитним модулем дисципліни індивідуальних завдань не передбачено.

Рекомендована література

• Болски М.И. Язык программирования Си. Справочник - М: Радио и связь, 1988. –   96 с.: ил.
• Керниган Б., Ритчи Д. Язык программирования Си ‑ Спб.: Невский диалект, 2004. - 352 с.
• Джехани Н. Программирование на языке Си ‑ М: Радио и связь, 1988. –   272 с.
• Тондо С., Гемпел Р. Язык Си М. 1997. –  157 с.
• Уэит М., Прата С., Мартин Д. Язык Си М: Мир,1988. – 267 с.
• Шилдт Г. Полный справочник по С, 4-е издание. – М.: Издательский дом «Вильямс», 2007. – 704 с.: ил.
• Объектно-ориентированный анализ и проектирование с примерами приложений, 3-е издание / [Г. Буч, Р.А. Максимчук, М.У. Энгл и др.] : Пер. с англ. – М.: ООО «И. Д. Вильямс», 2008. – 720 с.
• Дейтел Х.М., Дейтел П.Дж. Как программировать на Си / Х.М. Дейтел, П.Дж. Дейтел. – М.: Издательство Бином, 2005. – 912 с.
• Страуструп Б. Язык программирования С++. Специальное издание : Пер. с англ. – М.: Издательство Бином, 2011. – 1136 с.
• Дональд Э. Кнут Искусство программирования, том 1. Основные алгоритмы, 3-е издание. - Москва:Вильямс, 2006. - 720 стр., с ил.
• Дональд Э. Кнут Искусство программирования, том 2. Получисленные алгоритмы, 3-е издание. - Москва:Вильямс, 2007. - 832 стр., с ил
• Дональд Э. Кнут Искусство программирования, том 3. Сортировка и поиск, 2-е издание. - Москва:Вильямс, 2007. - 824 стр., с ил

Додаткова література

• Мальцев А.И. Алгоритмы и рекурсивные функции. - М.: Наука, 1986. - 368c.
• Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1985. - 406c.
• Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989. - 360c.
• Гудман С., Хидитниеми С. Введение в разработку и анализ алгоритмов. - М.: Мир, 1981. - 368с.
• Кормен Т. Х., Лейзерсон Ч. И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. - М.: Вильямс, 2005. - 1296 с.
• Гарднер М. Математические новеллы. - М.: Мир, 1974. - 456 c.
• Седжвик Р. Фундаментальные алгоритмы на С++. Т 1-4. Анализ/Структуры данных/Сортировка/Поиск. - СПб.: ООО "ДиаСофтЮП", 2002. - 688 с.
• Седжвик Р. Фундаментальные алгоритмы на С++. Т 5. Алгоритмы на графах. - СПб.: ООО "ДиаСофтЮП", 2002. - 496 с.
• Дональд Э. Кнут Искусство программирования, том 4, выпуск 2. Генерация всех кортежей и перестановок. - Москва:Вильямс, 2007. - 160 стр., с ил.
• Дональд Э. Кнут Искусство программирования, том 4, выпуск 3. Генерация всех сочетаний и разбиений. - Москва:Вильямс, 2007. - 208 стр., с ил.
• Дональд Э. Кнут Искусство программирования, том 4, выпуск 4. Генерация всех деревьев. - Москва:Вильямс, 2007. - 160 стр., с ил.
• Альфред Ахо, Джон Хопкрофт, Джеффри Ульман. Структуры данных и алгоритмы. - Москва:Вильямс, 2004. - 384 стр., с ил.

Засоби діагностики успішності навчання

Рекомендовані засоби діагностики успішності навчання за кредитним модулем 1

• проміжна модульно-контрольна робота з практичними та теоретичним завданнями;
• домашня контрольна робота з практичними та теоретичним завданнями;
• залікові білети з теоретичними та практичними питаннями.

Рекомендовані засоби діагностики успішності навчання за кредитним модулем 3:

• проміжна модульно-контрольна робота з практичними та теоретичним завданнями;
• екзаменаційні білети з теоретичними та практичними питаннями.

Методичні рекомендації

Даний курс орієнтований на не підготовленого слухача і є першим для студента при вивченні мов програмування в інституті, тому дуже важливо закласти основи розуміння внутрішньої архітектури комп'ютера, принципів організації пам'яті, найбільш часто використовуваних систем числення, а також процесів створення програмного забезпечення (ПЗ) з вихідних кодів і його наступної роботи.
Курс зосереджує основну увагу на принципах якісного конструювання програмного забезпечення.
Написання ясних і зрозумілих програм — найважливіша із цілей початкового курсу по програмуванню. Тому, щоб підкреслити можливі шляхи поліпшення програм, у курс включені рекомендації, по підвищенню ефективності.