Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Програмного забезпечення
Інформація про роботу
Рік:
2007
Тип роботи:
Інші
Предмет:
Логічне та функційне програмування
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ІНСТРУКЦІЇ ДО ВИКОНАННЯ ЛАБОРАТОРНИХ РОБІТ №1-4
З ПРЕДМЕТУ «Логічне та функційне програмування»
Затверджено
на засіданні кафедри
програмного забезпечення
Протокол №8 від 15.03 2007
Львів-2007
Інструкції до лабораторних робіт №1-4 з курсу “Логічне і функційне програмування” для студентів базового напрямку “Комп’ютерні науки” спеціальності “Програмне забезпечення автоматизованих систем”/ Укл.: Є.В. Левус. – Львів: Видавництво Національного університету “Львівська політехніка”, 2007. – 12 с.
Укладач Левус Є.В., канд. техн. наук, доцент
Відповідальний за випуск Коротрєєва Т.О., канд. техн. наук, доцент
Рецензенти Семотюк В.М., канд. техн. наук, доц.,
Іванців Р.Д., канд. техн. наук, доц.,
Дані інструкції призначені для виконання лабораторних робіт №1-4 з розділу “Функційне програмування” обсягом 12 годин. Матеріали до лабораторної роботи містять тему, мету, перелік термінів, визначень, правил, знання яких необхідні для виконання лабораторної роботи заданої теми, перелік варіантів завдань. Завдання пропонується виконувати у середовищі функційного програмування DrScheme.
Scheme — один з двох найбільш популярних в наші дні діалектів мови Lisp (другий популярний діалект — це Common Lisp). Aвтори мови Scheme — Гай Стіл (Guy L. Steele) і Джеральд Сассмен (Gerald Jay Sussman) з Массачусетського Технологічного Інституту — створили його в середині 1970-років. Робота в середовищі DrScheme можлива в режимі трансляції та інтерпретації. DrScheme містить усі необхідні компоненти для відлагодження функційних програм. Для виконання лабораторних робіт функційною мовою програмування Scheme необхідно вибрати в меню мову Standard.
Лабораторна робота №1.
Тема. Побудова елементарних функційних програм на основі базових елементарних.
Мета. Навчитися створювати прості функції на основі базових примітивів.
Теоретичні матеріали. Поняття функції. Типи даних: атом, список, пара. Функції-примітиви. Конструктор, селектори. Предикати. Умовний вираз. Блокування обчислень. Визначення нової функції.
Варіанти завдання до лабораторної роботи №1.
Варіант 1.
Довизначити функцію CAR(X) для випадку, коли Х є атомом.
Варіант 2.
Побудувати предикат ATOM(X).
Варіант 3.
Довизначити функцію CDR(X) для випадку, коли Х є атомом.
Варіант 4.
Визначити функцію QUADRAT(A,B,C,D), яка за вхідними параметрами формує спискову структуру ((A B) (C D)).
Варіант 5.
Визначити функцію, яка за 2 вхідними параметрами списками виду (A, B, C), (X, Y, Z) будує список (A, Y, Z). Передбачити випадок, якщо на вхід дано 2 порожніх списку, то на вихід – порожній список.
Варіант 6.
Визначити логічну функцію “І” (кон’юнкція) двох аргументів.
Варіант 7.
Визначити функцію, яка за 2 вхідними параметрами списками виду (A, B, C), (X, Y, Z) будує список (B, C, Z). Передбачити випадок, якщо на вхід дано 2 порожніх списку, то на вихід – порожній список.
Варіант 8.
Визначити функцію TYPE(X), яка визначає тип виразу X. Можливі лише 3 типи виразів і відповідні значення функції TYPE: атом, пустий список, непустий список.
Варіант 9.
Визначити логічну функцію “(” (імплікація) двох аргументів.
Варіант 10.
Визначити логічну функцію “(” (виключаюче додавання) двох аргументів.
Варіант 11.
Визначити логічну функцію заперечення одного аргумента.
Варіант 12.
Визначити логічну функцію дез’юнкція двох аргументів.
Лабораторна робота №2.
Тема. Використання методу рекурсії для написання функційних програм.
Мета. Навчитися створювати функції на основі базових примітивів, використовуючи принцип рекурсії.
Теоретичні матеріали. Поняття рекурсії. Список – рекурсивна структура. Термінальна та рекурсивні гілки в обчислювальному процесі. Розгортка та згортка рекурсії. Порядок гілок в рекурсивних обчисленнях. Нескінченна рекурсія. Рекурсія за аргументом та значенням.
Варіанти завдань до лабораторної роботи №2.
Варіант 1.
Визначити функцію СУМА(Х), де Х - список довільної довжини, який складається з цілих чисел, а результат функції – сума цих чисел.
Варіант 2.
Побудувати функцію предикатного типу НАЛЕЖИТЬ(Е, X), яка перевіряє чи заданий елемент Е входить до списку Х.
Варіант 3.
Визначити функцію ДОБУТОК(Х), де Х - список довільної довжини, який складається з цілих чисел, а результат функції – добуток цих чисел.
Варіант 4.
Визначити функцію ОСТАННІЙ(Х), яка видає як результат останній елемент списку Х.
Варіант 5.
Визначити функцію ОБЕРНУТИ(Х), яка видає список Х в оберненому порядку на верхньому рівні.
Варіант 6.
Визначити функцію ВИДАЛИТИ(Е, Х), яка видаляє перше входження заданого елемента Е зі списку Х.
Варіант 7.
Визначити функцію ДОВЖИНА(Х), яка обчислює кількість елементів списку Х на верхньому рівні.
Варіант 8.
Визначити функцію ВИДАЛИТИ_ОСТАННІЙ (Х), яка вилучає останній елемент зі списку Х.
Варіант 9.
Визначити функцію НОВИЙ(Х, У), яка чергуючи елементи двох списків, утворює новий список.
Варіант 10.
Визначити функцію ОБ’ЄДНАТИ(Х, У), яка об’єднує два списки Х і У в один.
Варіант 11.
Визначити функцію, яка вилучає кожен другий елемент зі списку Х.
Варіант 12.
Визначити функцію предикатного типу, яка визначає чи її аргумент є однорівневим списком.
Лабораторна робота №3.
Тема. Використання методу параметрів нагромадження для написання ефективних функційних програм.
Мета. Навчитися створювати функції на основі базових примітивів, використовуючи метод параметрів нагромадження.
Теоретичні матеріали. Поняття ефективності програми. “Дорогі” функції. Підвищення ефективності програми. Параметр-акумулятор. Схема методу параметру нагромадження.
Варіанти завдань до лабораторної роботи №3.
Варіант 1.
Визначити функцію СУМА_ДОБУТОК(Х), де Х - список довільної довжини, який складається з цілих чисел, а результат функції – список двох елементів: сума та добуток цих чисел.
Варіант 2.
Побудувати функцію ОБЕРНУТИ (X), яка записує в оберненому порядку елементи списку Х на всіх рівнях ієрархії. Для побудови цієї функції використати допоміжну ОБЕРНУТИ (X, У), де У – параметр нагромадження.
Варіант 3.
Визначити функцію ВИДАЛИТИ(Е, Х), яка видаляє всі входження заданого елемента Е зі списку Х.
Варіант 4.
Визначити функцію МНОЖИНА(Х), яка зі списку Х формує множину: всі елементи мають одне входження (без повторень).
Варіант 5.
Визначити функцію ДОДАТНІ_ВІД’ЄМНІ(Х), де Х - список довільної довжини, який складається з цілих чисел, а результат функції – список двох елементів: кількість додатних та від’ємних чисел у цьому списку.
Варіант 6.
Визначити функцію ІНДИВІД(Х), яка будує новий список з елементів списку Х, які зустрічаються у Х лише один раз.
Варіант 7.
Визначити функцію ДОДАТНІ_ДОВЖИНА(Х), де Х - список довільної довжини, який складається з цілих чисел, а результат функції – список двох елементів: кількість додатних чисел у цьому списку та загальна кількість елементів.
Варіант 8.
Визначити функцію 1_2(Х), де Х - список довільної довжини, а результат функції – список двох елементів: кількість елементів на верхньому рівні та загальна кількість елементів списку.
Варіант 9.
Побудувати 2 варіанти функції визначення чисел Фібоначчі, використовуючи звичайну рекурсію та “хвостову”.
Варіант 10.
Побудувати 2 варіанти функції обчислення факторіалу, використовуючи звичайну рекурсію та “хвостову”.
Лабораторна робота №4.
Тема. Використання функцій вищих порядків для написання функційних програм.
Мета. Навчитися створювати функції вищих порядків.
Теоретичні матеріали. Функції вищих порядків. Функції на місці аргументу. Функції на місці значення. Функціонали.
Варіанти завдань до лабораторної роботи №4.
Варіант 1.
Побудувати функцію СУМА(Х) через РЕДУКЦІЯ(X,G,A), де Х – список чисел, G – бінарна функція, А – постійний параметр.
Варіант 2.
Побудувати функцію ДОБУТОК(Х) через РЕДУКЦІЯ(X,G,A), де Х – список чисел, G – бінарна функція, А – постійний параметр.
Варіант 3.
Побудувати функцію СУМА_ ДОБУТОК (Х) через РЕДУКЦІЯ(X,G,A), де Х – список чисел, G – бінарна функція, А – постійний параметр. Результат цієї функції список з 2-ох чисел (добуток, сума).
Варіант 4.
Побудувати функцію ЗМЕНШИТИ(Х, 2), яка кожен елемент числового списку Х зменшує на 2. Використати попередньо побудувану функцію ВІДОБРАЗИТИ(Х,У), яка застосовує функцію У до кожного елементу списку Х.
Варіант 5.
Побудувати функцію ЗАЛИШОК(Х, 2), яка визначає залишки від ділення кожного елемента числового списку Х на 2. Використати попередньо побудувану функцію ВІДОБРАЗИТИ(Х,У), яка застосовує функцію У до кожного елементу списку Х.
Варіант 6.
Побудувати функцію ДІЛЕННЯ (Х, 3), яка визначає частки від ділення кожного елемента числового списку Х на 3. Використати попередньо побудувану функцію ВІДОБРАЗИТИ(Х,У), яка застосовує функцію У до кожного елементу списку Х.
Варіант 7.
Побудувати функцію ЗБІЛЬШИТИ(Х, 5), яка кожен елемент числового списку Х збільшує на 5. Використати попередньо побудувану функцію ВІДОБРАЗИТИ(Х,У), яка застосовує функцію У до кожного елементу списку Х.
Варіант 8.
Побудувати функцію ЗБІЛЬШИТИ(Х, 5), яка кожен елемент числового списку Х збільшує в 5 разів. Використати попередньо побудувану функцію ВІДОБРАЗИТИ(Х,У), яка застосовує функцію У до кожного елементу списку Х.
Варіант 9.
Побудувати функцію ЗМЕНШИТИ(Х, 2), яка кожен елемент числового списку Х зменшує в 2 рази. Використати попередньо побудувану функцію ВІДОБРАЗИТИ(Х,У), яка застосовує функцію У до кожного елементу списку Х.
Варіант 10.
Побудувати функцію ЗАЛИШОК(Х, 3), яка визначає залишки від ділення кожного елемента числового списку Х на 3. Використати попередньо побудувану функцію ВІДОБРАЗИТИ(Х,У), яка застосовує функцію У до кожного елементу списку Х.
Варіант 11.
Побудувати функцію ДІЛЕННЯ (Х, 2), яка визначає частки від ділення кожного елемента числового списку Х на 2. Використати попередньо побудувану функцію ВІДОБРАЗИТИ(Х,У), яка застосовує функцію У до кожного елементу списку Х.
ПОРЯДОК ВИКОНАННЯ РОБОТИ:
Отримати номер індивідуального варіанту завдання у викладача.
З допомогою середовища DrScheme виконати завдання на комп’ютері.
Задати три варіанти вхідних даних для створеної функції. Проаналізувати отримані результати.
Продемонструвати викладачеві роботу функції, відповісти на 3 контрольні питання стосовно теми лабораторної роботи та тексту програми.
Оформити звіт про роботу.
ПОРЯДОК ОФОРМЛЕННЯ ЗВІТУ.
Лабораторна робота обов’язково супроводжується оформленням звіту. Звіт повинен містити такі компоненти:
титульна сторінка,
тема,
мета,
теоретичні відомості (коротко про використані функції та методи),
формулювання завдання,
текст функційного означення,
отримані результати,
висновок.
Сторінки звіту повинні бути пронумеровані та скріплені належним чином.
За неправильно оформлений звіт знімаються бали отримані за демонстрацію написаної програми, а без оформленого звіту робота не зараховується.
Перелік контрольних запитань для самоперевірки
з розділу “Функційне програмування”
Суть строго функційного програмування.
Історія виникнення та розвитку функційного програмування. Області застосування функційного програмування.
Поняття функції, області значення та області визначення функції, композиція функцій, основні способи задання функцій.
Способи представлення даних у функційному програмуванні. Поняття S-виразу. Типи S-виразів у мові Лісп. Значення S-виразів.
Атом. Список. Пара. Зв’язок між цими структурами.
Базові функції Лісп: селектори, конструктори, предикати.
Умовний вираз у мові Лісп.
Визначення нової функції у мові Лісп. Основні арифметичні та логічні функції.
(-обчислення. Формальні та фактичні параметри. Застосування (-виразів у функційному програмуванні.
Рекурсивне визначення функцій у функційному програмуванні. Поняття стеку перерваних процесів. Термінальна гілка.
Порядок обчислювальних гілок у рекурсивному визначенні функції. Нескінченна рекурсія.
Різні форми рекурсії за структурою обчислювального процесу.
Рекурсія за значенням. Рекурсія за аргументом.
Суть методу нагромадження параметрів. Поняття ефективності функційної програми.
Функції вищих порядків. Функціональний аргумент. Функціонали.
Список літератури
Хювёнен Э., Сеппенен И. Мир Lisp'а. В 2-х томах. М.: Мир, 1990.
Душкин Р. В. Текст лекций по курсу «Функциональное программирование». - Москва, 2001
Медведєв М.Г. Функціональна мова програмування ЛІСП: Навчальний посібник для студентів. - Київ – 1999.
Морозов М.Н. Функциональное программирование. - 1999.
Дехтяренко И.А. Декларативное программирование. –2003.
Заєць В.М. Функційне програмування. – Л.:2002.
Левус Є.В. Елементи функційного програмування./Метод.вказівки до практичних занять. –2007.
Навчальне видання
Кафедра програмного забезпечення
ІНСТРУКЦІЇ ДО ВИКОНАННЯ ЛАБОРАТОРНИХ РОБІТ №1-4
З ПРЕДМЕТУ «Логічне та функційне програмування»
Укладач Левус Євгенія Василівна
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора