Лекція 7. Представлення інформації у комп'ютері – 2 год.

7.1. Цілі числа. 7.2. Дійсні числа.

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

ЗАВДАННЯ 7.4. Знайти ціле число х таке, що х + 1 х.

ЗАВДАННЯ 7.5. Явно перерахуйте і зобразіть на числовій прямій всі точки множини , зробивши такі припущення: числа зберігаються в нормалізованій формі з плаваючою точкою; для зберігання як мантиси, так і порядку числа відводиться по три біти (з яких в обох випадках один є знаковим); ніяких особливих значень немає. ЗАВДАННЯ 7.6. Знайдіть дійсне (типу double) число x таке, що (x / 2) × 2 ≠ x. Скористайтеся тим, що клас java. lang / Double визначає константу MIN_VALUE. ЗАВДАННЯ 7.7. Визначте (наближено) (машинне епсилон) для типів double і float. Машинним eпсілоном називається найбільше число даного типу, що задовольняє співвідношенню 1 + x = 1. ЗАВДАННЯ 7.8. Знайдіть послідовність чисел (типу float), при сумуванні якої в прямому і зворотному порядку результати будуть відрізнятися не менш, ніж удвічі. ЗАВДАННЯ 7.9. Напишіть програму, яка вводить дійсні коефіцієнти a, b і c квадратного рівняння + bx + c =0 з позитивним дискримінантом, що знаходить обидва корені цієї рівності досить точно у всіх випадках.

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

Лекція 8. Рекурсія, ітерація і оцінки складності алгоритмів – 2 год.

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

 

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

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

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

Лекція 9. Проектування програм – 2 год.

9.0. Предикати і документування програм. 9.1. Специфікація програми і перетворювач предикатів . 9.2. Визначення простих операторів мови Java. 9.3. Базисні схеми обробки інформації. 9.4. Проектування рекурсії та ітерації. 9.5.Інваріант і функція обмеження циклу. 9.6. Схема обчислення інваріантної функції. 9.5. Функції на просторі послідовностей.

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

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

ВКАЗІВКА. Нехай . Продиференціюємо по x рівність та підставимо потім . Ми отримаємо наступні співвідношення:

Скориставшись ними і формулами

,

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

ЗАВДАННЯ 9.29. Напишіть програму, яка підносить ціле число в цілу невід ' ємну ступінь. Точні перед- і постумови цієї програми такі: . При написанні програми величини і змінювати не дозволяється, слід використовувати інваріант і обмежуючу функцію h = у.

ЗАВДАННЯ 9.30. Напишіть програму, що знаходить найбільший спільний дільник двох цілих невід'ємних чисел та не рівних одночасно нулю. Скористайтеся наступною властивістю найбільшого загального дільника (доведіть її!):

Тут операція дозволяє знайти залишок від ділення на .

ЗАВДАННЯ 9.31. Напишіть програму, що зводить ціле число в цілу невід’ємну ступінь. Точні перед- і постумови цієїї програми такі: , . При написанні програми величини i змінювати не дозволяється. Скористайтеся тим, що функція , інваріантної щодо перетворення , що задається формулою

 

ЗАВДАННЯ 9.32. Напишіть програму, що знаходить найбільший спільний дільник двох цілих невід'ємних чисел і , не рівних одночасно нулю. Програма повинна мати тимчасову складність порядку і не використовувати операцій ділення і знаходження залишку від ділення (допустимо поділ навпіл, реалізоване з допомогою операції зсуву). Скористайтеся наступними властивостями найбільшого загального дільника (доведіть їх!):

.

ВКАЗІВКИ. Скористайтеся інваріантністю функції щодо наступного перетворення T:

 

 

Не забудьте довести Т інваріантність функції F

 

 

Лабораторне заняття 8 – 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]