Змістовий модуль 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 год.

Алгоритми. 2.2. Обчислювальні машини. 2.3. Основи фон-нейманівської архітектури.

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

6. Для кожної пари функцій f(n) та g(n) порівняйте порядок їх росту:

a) , ;

б) , ;

в) , ;

г) , ;

д) , ;

е) , .

7. Розташуйте такі функції за зростанням. Якщо деякі функції мають однаковий порядок, зазначте це.

n! n2

8. Наступні дві функції, описані напівпаскалевською мовою, обчислюють для цілих чисел k та n. Знайдіть часову складність цих функцій:

 

a) function exp1(k, n);

begin power:= 1;

for i:= 1 to n do

begin newpower:= 0;

for j:= 1 to k do

newpower:= newpower + power;

power:= newpower

end;

return(power)

end.

 

б) function exp2(k, n);

begin power:= 1;

for i:= 1 to n do

power:= power * k;

return(power)

end.

 

9. Для кожного з наведених алгоритмів знайдіть його часову оцінку для найгіршого випадку.

 

{Ці функції обчислюють Х у степені N, де N – додатне ціле число}

function power1(X, N);

begin if N = 1 then return(X)

else return(X * power1(X, N–1))

end;

function power2(X, N);

begin if N = 1 then return(X)

else

begin HALF:= N/2;

HALFPOWER:= power2(X, HALF)

if 2*HALF = N {N is even}

then return(HALFPOWER * HALFPOWER)

else return(HALFPOWER * HALFPOWER * X) {N is odd}

end

end;

 

function power3(X, N);

begin if N = 1 then return(X)

else

begin HALF:= N/2;

if 2 * HALF = N {N is even}

then return(power3(X, HALF) * power3(X, HALF))

else return(power3(X, HALF) * power3(X, HALF) * X) {N is odd}

end

end.

 

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

 

Змістовий модуль 2. Мови і базові принципи програмування

Лекція 3. Парадигми програмування [1, 2]. – 2 год.

Базові парадигми програмування. 3.2. Процедурне програмування. 3. 3. Модульне програмування. 3.4. Об’єктно-орієнтовне програмування. 3.5. Функціональне програмування. 3.6. Алгебраїчна парадигма

 

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

1. Визначити програмовану функцію для доповнення множини.

2. Визначити процедуру введення числової множини.

3. Визначити функцію, що дає мінімальний елемент числової множини.

4. Показати елементи числової множини в порядку зростання.

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

6. Діаметром числової множини називається величина

d(А) = max ¦x-y¦. х, у Î А. Визначити функцію обчислення діаметра d(А).

7. Визначити процедуру отримання мінімального, максимального елемента множини.

8. Нехай Q(х) - умова. Визначити функцію, що дає по множині А підмножину всіх таких її елементів, для яких справедлива умова Q(х).

9. Визначити функцію переведення комплексного числа з алгебраїчної у тригонометричну форму та навпаки.

10. Визначити функцію дати вчорашнього дня.

11. Визначити функцію обчислення дня тижня по його даті в поточному році.

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

13. Визначити тип плоска фігура, що включає трикутник, паралелограм, трапецію та коло. Побудувати функції обчислення периметра та площі плоских фігур.

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

 

Лекція 4. Огляд основних мов програмування [1-19] – 2 год.

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

14. Мова Picmkalkul Конрада Цузе.

15. Мінімальне програмування на апаратному рівні: псевдокоди.

16. Комп'ютер IBM 704 і мова FORTRAN.

17. Функціональне програмування: мова LISP.

18. Перший крок до удосконалення: мова ALGOL 60.

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

Лекція 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