Національний університет «Києво-Могилянська Академія»

Національний університет «Києво-Могилянська Академія»

Факультет інформатики

 

Кафедра інформатики

Укладач: доктор фіз.-мат. наук, професор Глибовець М.М.

 

МОВИ ПРОГРАМУВАННЯ

 

РОБОЧА НАВЧАЛЬНА ПРОГРАМА

 

за напрямком бакалавр» за галуззю знань 12 «Інформаційні технології» спеціальністю 122 «Комп’ютерні науки та інформаційні технології»

 

Всього годин 240

Лекційних 28

Практичних 56

Самостійна робота 156

Офісні 4

Форма контролю: іспит

Кредитів за курс: 8

Вступ

Дисципліна "Мови програмування" є базовою нормативною дисципліною для студентів спеціальності «Комп’ютерні науки та інформаційні технології» (факультет інформатики), що читається на 1 курсі в 1 семестрі.

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

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

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

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

Вимоги до знань та вмінь.

Студент повинен знати: основи інформатики.

Студент повинен вміти: ефективно застосовувати отримані знання для розв¢язку прикладних задач та проведення наукових досліджень за фахом.

Місце в структурно-логічній схемі спеціальності. Нормативна навчальна дисципліна «Мови прграмування» є складовою циклу професійної підготовки фахівців освітньо-кваліфікаційного рівня “бакалавр”та служить базою для вивчення спеціальних курсів магістерської програми.

Принципи та філософія курсу:

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

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

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

 

Компоненти навчальних матеріалів курсу:

 

1. Аудиторні заняття (лекції і практичні заняття).

2. Колоквіуми і лабораторні роботи

3. Текстові навчальні матеріали, презентації, посилання на додаткову літературу.

 

Оцінювання:

Задовільне опанування курсу (допуск до іспиту) досягається через присутність на заняттях, працю на лекціях і практичних заняттях, успішно виконаних контрольних і лабораторних роботах, зданому колоквіуму. Очікується, що за роботу в триместрі (на лекціях і практичних) спудей може отримати 50 балів рейтингу. На іспиті можна отримати решту – 50 балів рейтингу.

Система контролю знань та умови складання іспиту. Робота студентів з дисципліни оцінюється за модульно-рейтинговою системою. Матеріал дисципліни поділяється на 3 іспитові модулі.

Результати навчальної діяльності студентів оцінюються за 100 - бальною шкалою.

Модульний контроль.

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

- домашнє виконання завдань– 3 бали в кожному модулі;

- усна відповідь, доповнення (як на лекції, так і на практичному зан.) – 2 бали в кожному модулі;

- модульні контрольні роботи – 5 балів в кожному модулі;

Підсумковий контроль проводиться у формі письмового іспиту – 50 балів.

 

За результатами семестру студент отримує підсумкову оцінку за 100-бальною системою, яка розраховується як накопичення оцінок за кожен з модулів у семестрі та оцінки за іспит. Підсумкова оцінка 100 = 5 * (3+2+5)+50.

Студент допускається до складання іспиту за умови виконання положення про навчаня в НаУКМА (відвідуваність), та якщо кількість набраних ним балів за роботу в семестрі становить не менше 35 балів. Пропущені заняття без поважних причин мають бути відпрацьовані додатково.

Іспит вважається не зданим, якщо сумарна кількість балів з дисципліни складає менше 60 балів.

Підсумкова оцінка “x” з дисципліни у балах (100 – бальна шкала) переводиться у чотирибальну (національну шкалу) з розрахунку: 60<= х <76 – задовільно, 76<= х <91 – добре, 91<= х <=100 – відмінно.

 

Студент може отримати індивідуальний графік опанування курсу за узгодження із викладачем.

 

НАВЧАЛЬНО-ТЕМАТИЧНИЙ ПЛАН ЛЕКЦІЙ

І ПРАКТИЧНИХ ЗАНЯТЬ

№ п. п.	Назва лекції	Кількість годин
Лекції	Практичні	Самост. робота
Змістовний модуль 1 Базові концепції інформатики та програмування
	Інформатика. Предмет науки програмування
	Алгоритми і обчислення
	Модульна контрольна робота № 1
Змістовний модуль 2 Мови і базові принципи програмування
	Парадигми програмування.
	Огляд основних мов програмування.
	Трансляція і формальні граматики
	Java - мова ООП
	Модульна контрольна робота № 2
Змістовний модуль 3 Проектування програм з використанням мови програмування Java
	Представлення інформації у комп'ютері
	Рекурсія, ітерація і оцінки складності
	Базові методи проектування програм
	Знаходження інваріанта циклу і доведення правильності програм
	Індуктивні функції на просторі послідовностей
	Модульна контрольна робота № 3

Змістовий модуль 1. Базові концепції інформатики та програмування

Лекція 1. Вступ [1], [2][6-13]. – 2 год.

Інформатика. 1.2. Алгоритм. 1.4. Застосування мов програмування.1.5. Стандартизація мов програмування. 1.6. Середовище розробки. 1.7. Тестування і верифікація програм.

Завдання для самостійної роботи 7 год.

1. Задання даних в пам’яті ЕОМ

 

Лекція 2. Алгоритми і обчислення [1], [2][6-13] – 2 год.

Лекція 5. Трансляція і формальні граматики – 4 год.

Транслятори. 5.2. Процес трансляції. 5.3. Формальні граматики. 5.4. Регулярні вирази

 

Завдання для самостійної роботи 15 год.

Класифікація граматик за Хомським.

Лабораторне заняття 4. – 6 год. [3]

Лекція 6. Java - мова ООП – 2 год.

Об'єктно-орієнтоване програмування. 6.2. Основні властивості програм і перші приклади. 6.3. Типи, змінні, оператори. 6.4. Використання класу Xterm. 6.6. Логічні та умовні оператори.

Завдання для самостійної роботи 15 год.

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

Лабораторне заняття 5. – 6 год. [3]

Змістовний модуль 3. Проектування програм з використанням мови програмування Java

Співставимість рекурсії та ітерації. 8.2. Виняткові ситуації і робота з послідовностями

 

Завдання для самостійної роботи 15 год.

Запрограмувати 5-6 основних алгоритмів із «матричної арифметики».

Лабораторне заняття 7. – 8 год. [3]

Лекція 10. Знаходження інваріанта циклу і доведення правильності – 4 год.

Умови правильності циклу. 10.2. Теорія повітряної кульки. 10.3. Усунення кон'юнктивного члена. 10.4. Заміна константи змінною. 10.5. Розширення області значення змінної. 10.6. Завдання для самостійного рішення.

 

Завдання для самостійної роботи 20 год.

При вирішенні завдань необхідно побудувати і довести правильність побудованої програми виду "S0; while (e) S;", а за відсутності в умові задачі явно заданих інваріанта циклу і обмежуючій функції пояснити попередньо, яким чином вони були отримані.

Задача 1.1. Напишіть програму, що друкує n-е число Фібоначчі . При написанні програми використовуйте Число в програмі змінити не можна.

Задача 1.2. Напишіть програму, що знаходить приватна і залишок від ділення на , не використовуйте операції множення і ділення. При написанні програми покладіть , , . Величини x і у в програмі змінювати не дозволяється.

Задача 1.3. Напишіть програму, що знаходить найбільший спільний дільник gcd (X, Y) двох цілих позитивних чисел X і Y, не використовує операцій множення і ділення і не змінну величин X і Y. При написанні програми покладіть ,

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

,

,

.

Задача 1.4. Напишіть програму, що знаходить наближене значення квадратного кореня із заданого невід’ємного цілого числа n. Ось більш точне формулювання перед- і постумови: При написанні програми величину n змінювати не можна. Для побудови інваріанта видаліть з постумови кон'юнктивний член . Оцініть тимчасову складність отриманої програми і порівняйте її зі складністю програми, побудованої в задачі 2.1.

Задача 1.5. Напишіть програму, що визначає перше входження заданого цілого числа х в заданий масив масивів цілих чисел . Значення елементів масиву b і числа х, m і n в програмі змінювати не можна. У момент завершення має бути або , або, якщо числа x в масиві немає, . Точні перед- і постумови необхідної програми такі: , .

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

Задача 1.6. Напишіть програму (бінарний або двійковий пошук), визначальну для впорядкованого за не зменшенням масиву цілих чисел і заданого цілого числа х позицію , в яку може бути вставлене це число без порушення впорядкованості масиву. Точні перед- i постумови необхідної програми, тимчасова складність якої не повинна перевершувати , такі; . При написанні програми величини х, n і елементи масиву b зраджувати не дозволяється, для побудови інваріанта використовуйте метод заміни константи змінної.

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

 

Лабораторне заняття 9. – 8 год. [3]

РЕКОМЕНДОВАНА ЛІТЕРАТУРА

1. http://distedu.ukma.kiev.ua
2. Глибовець М. М. Основи комп’ютерних алгоритмів. К.: Видавничий дім “КМ Академія”, 2003.
3. Алгоритмы + структуры данных = программы, Н.Вирт
4. Алгоритмы на Java 4-е издание, Роберт Седжвик, Кевин Уейт, Вильямс, 2013
5. http://algs4.cs.princeton.edu
6. https://www.coursera.org/course/algs4partI
7. https://www.coursera.org/course/algs4partII

8. Г.В. Электрическая машина Холлерита для подсчета статистических данных // В. О. Ф.Э.М. — 1895. — № 225. — С. 193–201.

9. Лафоре Р. Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. — СПб.: Питер, 2013. — 704 с.: ил. — (Серия«Классика computer science»).

10. Роберт Седжвик, Кевин Уэйн. Алгоритмы на Java, 4-е издание = Algorithms, 4th Edition. — М.: «Вильямс», 2012. — 848 с. — ISBN 978-5-8459-1781-2.

11. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков. -- М., Наука, 1988.

 

Національний університет «Києво-Могилянська Академія»

Факультет інформатики

 

Кафедра інформатики

Укладач: доктор фіз.-мат. наук, професор Глибовець М.М.

 

МОВИ ПРОГРАМУВАННЯ

 

РОБОЧА НАВЧАЛЬНА ПРОГРАМА

 

за напрямком бакалавр» за галуззю знань 12 «Інформаційні технології» спеціальністю 122 «Комп’ютерні науки та інформаційні технології»

 

Всього годин 240

Лекційних 28

Практичних 56

Самостійна робота 156

Офісні 4

Форма контролю: іспит

Кредитів за курс: 8

Вступ

Дисципліна "Мови програмування" є базовою нормативною дисципліною для студентів спеціальності «Комп’ютерні науки та інформаційні технології» (факультет інформатики), що читається на 1 курсі в 1 семестрі.

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

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

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

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

Вимоги до знань та вмінь.

Студент повинен знати: основи інформатики.

Студент повинен вміти: ефективно застосовувати отримані знання для розв¢язку прикладних задач та проведення наукових досліджень за фахом.

Місце в структурно-логічній схемі спеціальності. Нормативна навчальна дисципліна «Мови прграмування» є складовою циклу професійної підготовки фахівців освітньо-кваліфікаційного рівня “бакалавр”та служить базою для вивчення спеціальних курсів магістерської програми.

Принципи та філософія курсу:

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

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

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

 

Компоненти навчальних матеріалів курсу:

 

1. Аудиторні заняття (лекції і практичні заняття).

2. Колоквіуми і лабораторні роботи

3. Текстові навчальні матеріали, презентації, посилання на додаткову літературу.

 

Оцінювання:

Задовільне опанування курсу (допуск до іспиту) досягається через присутність на заняттях, працю на лекціях і практичних заняттях, успішно виконаних контрольних і лабораторних роботах, зданому колоквіуму. Очікується, що за роботу в триместрі (на лекціях і практичних) спудей може отримати 50 балів рейтингу. На іспиті можна отримати решту – 50 балів рейтингу.

Система контролю знань та умови складання іспиту. Робота студентів з дисципліни оцінюється за модульно-рейтинговою системою. Матеріал дисципліни поділяється на 3 іспитові модулі.

Результати навчальної діяльності студентів оцінюються за 100 - бальною шкалою.

Модульний контроль.

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

- домашнє виконання завдань– 3 бали в кожному модулі;

- усна відповідь, доповнення (як на лекції, так і на практичному зан.) – 2 бали в кожному модулі;

- модульні контрольні роботи – 5 балів в кожному модулі;

Підсумковий контроль проводиться у формі письмового іспиту – 50 балів.

 

За результатами семестру студент отримує підсумкову оцінку за 100-бальною системою, яка розраховується як накопичення оцінок за кожен з модулів у семестрі та оцінки за іспит. Підсумкова оцінка 100 = 5 * (3+2+5)+50.

Студент допускається до складання іспиту за умови виконання положення про навчаня в НаУКМА (відвідуваність), та якщо кількість набраних ним балів за роботу в семестрі становить не менше 35 балів. Пропущені заняття без поважних причин мають бути відпрацьовані додатково.

Іспит вважається не зданим, якщо сумарна кількість балів з дисципліни складає менше 60 балів.

Підсумкова оцінка “x” з дисципліни у балах (100 – бальна шкала) переводиться у чотирибальну (національну шкалу) з розрахунку: 60<= х <76 – задовільно, 76<= х <91 – добре, 91<= х <=100 – відмінно.

 

Студент може отримати індивідуальний графік опанування курсу за узгодження із викладачем.

 

НАВЧАЛЬНО-ТЕМАТИЧНИЙ ПЛАН ЛЕКЦІЙ

І ПРАКТИЧНИХ ЗАНЯТЬ

№ п. п.	Назва лекції	Кількість годин
Лекції	Практичні	Самост. робота
Змістовний модуль 1 Базові концепції інформатики та програмування
	Інформатика. Предмет науки програмування
	Алгоритми і обчислення
	Модульна контрольна робота № 1
Змістовний модуль 2 Мови і базові принципи програмування
	Парадигми програмування.
	Огляд основних мов програмування.
	Трансляція і формальні граматики
	Java - мова ООП
	Модульна контрольна робота № 2
Змістовний модуль 3 Проектування програм з використанням мови програмування Java
	Представлення інформації у комп'ютері
	Рекурсія, ітерація і оцінки складності
	Базові методи проектування програм
	Знаходження інваріанта циклу і доведення правильності програм
	Індуктивні функції на просторі послідовностей
	Модульна контрольна робота № 3