Задания на последнюю лабораторную работу
Пояснения к заданиям
1. Первое задание выполняется на F# (на оценку «5») или на Лиспе (на оценку «3» или «4»).
2. Второе задание выполняется на F# (на оценку «5») или на Лиспе (на оценку «3» или «4»). Требуется реализовать интерфейс взаимодействия с пользователем (на F#) и графическую анимацию поиска решения (на оценку «5»), либо текстовую анимацию (в виде последовательности текстовых блоков, записываемые в файл) на Лиспе (на оценку «4)», либо просто отображение результата (на оценку «3»).
3. Пример решения третьего задания смотрите в конце данного документа. Данное задание выполняется на Прологе.
4. Четвертое задание. Дана предметная область (задача) для решения упрощенной экспертной системы. Составить не менее 10 предложений (фактов и правил). Пример решения упрощенной экспертной системы можно взять из лекции № 1 по Прологу и из лабораторной работы № 1 по Прологу (система, описывающая дерево родственных отношений). Система задает вопрос пользователю, а пользователь отвечает. Система должна уметь запоминать новые объекты (состояние), которых не было в базе данных (используйте assert). Данное задание выполняется на Прологе.
Вариант №1
1. Вычисление арифметического выражения в инфиксной записи.
2. Генерация списка всех возможных расстановок максимального количества слонов на доске (12 x 7) клеток таким образом, чтобы ни один из слонов не бил другого. Слоном называется фигура, ходящая по диагонали.
3. Трое ребят вышли гулять с собакой, кошкой и хомячком. Известно, что Петя не любит кошек и живет в одном подъезде с хозяйкой хомячка. Лена дружит с Таней, гуляющей с кошкой. Определить, с каким животным гулял каждый из детей?
4. Локализация неисправности персонального компьютера по внешним симптомам.
Вариант №2
1. Перевод обратной польской записи в инфиксную арифметическую запись.
2. Генерация списка всех возможных расстановок максимального количества ладей на доске (12 x 7) клеток таким образом, чтобы ни одна из ладей не била другую. Ладьёй называется фигура, ходящая прямо в горизонтальном или вертикальном направлении.
3. Витя, Юра и Миша сидели на скамейке. В каком порядке они сидели, если известно, что Юра сидел слева от Миши и справа от Вити.
4. Определение конфигурации персонального компьютера в зависимости от потребностей пользователя.
Вариант №3
1. Расстановка скобок в инфиксной арифметической записи в соответствии с общепринятыми приоритетами операций.
2. Генерация списка всех возможных расстановок максимального количества слонов на доске (10 x 9) клеток таким образом, чтобы ни один из слонов не бил другого. Слоном называется фигура, ходящая по диагонали.
3. Пять пионеров Алик, Боря, Витя, Лена и Даша приехали в лагерь из 5 разных городов: Харькова, Умани, Полтавы, Славянска и Краматорска. Есть 4 высказывания:
1) Если Алик не из Умани, то Боря из Краматорска.
2) Или Боря, или Витя приехали из Харькова.
3) Если Витя не из Славянска, то Лена приехала из Харькова.
4) Или Даша приехала из Умани, или Лена из Краматорска.
Кто откуда приехал?
4. Определение конфигурации компьютера с точностью до моделей комплектующих с учетом возможных конфликтов оборудования.
Вариант №4
1. Вычисление арифметического выражения в инфиксной записи.
2. Поиск и генерация списка всех возможных расстановок семи ферзей на доске (12 x 7) таким образом, чтобы ни один из ферзей не бил другого. Ферзём называется фигура, ходящая в любом направлении: по горизонтали, вертикали или диагонали.
3. Четыре человека играют в домино. Их фамилии Кузнецов, Токарев, Слесарев и Резчиков. Профессия каждого игрока соответствует фамилии одного из других игроков. Напротив Кузнецова сидит слесарь.
Напротив Резчикова сидит резчик.
Справа от Слесарева сидит токарь.
Кто сидит слева от кузнеца?
4. Выбор комплекта программного обеспечения для компьютера в соответствии с задачами, которые необходимо решать пользователю.
Вариант №5
1. Вычисление логического выражения в инфиксной записи (операции: and, xor, or, not, “)”, “(“).
2. Генерация списка всех возможных расстановок максимального количества ладей на доске (10 x 9) клеток таким образом, чтобы ни одна из ладей не била другую. Ладьёй называется фигура, ходящая прямо в горизонтальном или вертикальном направлении.
3. Трое ребят вышли гулять с собакой, кошкой и хомячком. Известно, что Петя не любит кошек и живет в одном подъезде с хозяйкой хомячка. Лена дружит с Таней, гуляющей с кошкой. Определить, с каким животным гулял каждый из детей?
4. Выбор оптимального языка программирования в зависимости от поставленной задачи.
Вариант №6
1. Генерация списка <счастливых> 2N-значных чисел (т. е. таких, сумма первых N чисел которых равна сумме вторых N чисел).
2. Поиск и генерация списка всех возможных расстановок девяти ферзей на доске (10 x 9) таким образом, чтобы ни один из ферзей не бил другого. Ферзём называется фигура, ходящая в любом направлении: по горизонтали, вертикали или диагонали.
3. В одной школе уроки по истории, математике, биологии, географии, английскому и французскому языку вели три учителя – Морозов, Васильев и Токарев. Каждый из них преподавал два предмета.
Географ и учитель французского языка – соседи по дому.
Учитель биологии старше учителя математики. Морозов – самый молодой.
В понедельник первый урок по расписанию у Токарева, у биолога и у учителя французского языка.
В воскресенье Морозов, математик и учитель английского языка были на рыбалке.
Какие предметы преподает каждый учитель?
4. Диагностика неисправности автомобиля (телевизора, телефона, пылесоса …).
Вариант №7
1. Генерация списка <счастливых> шестизначных чисел (т. е. таких, сумма первых трёх цифр которых равна сумме трёх вторых).
2. Генерация списка всех возможных расстановок максимального количества слонов на доске (11 x 10) клеток таким образом, чтобы ни один из слонов не бил другого. Слоном называется фигура, ходящая по диагонали.
3. Есть четыре боксера: Томас Герберт, Герберт Френсис, Френсис Джеймс и Джеймс Томас.
Герберт намного сильнее Томаса.
Френсис сильнее и Томаса и Герберта. Герберт слабее Джеймса, но сильнее Френсиса.
В каком порядке нужно расположить боксеров от слабейшего к сильнейшему?
4. Выбор оптимального способа путешествия (самолет, поезд, пароход, автостопом, на машине, автобусом).
Вариант №8
1. Вычисление логического выражения в инфиксной записи (операции: and, xor, or, not, “)”, “(“)
2. Генерация списка всех возможных расстановок максимального количества ладей на доске (11 x 10) клеток таким образом, чтобы ни одна из ладей не била другую. Ладьёй называется фигура, ходящая прямо в горизонтальном или вертикальном направлении..
3. Имеется четыре котенка: Дружок, Елисей, Фантик и Мурлыка – и четыре мальчика: Миша, Максим, Леня и Дима. Каждый мальчик взял себе котенка любимого цвета.
При этом:
1) Фантик – не рыжий. Мурлыка – не серый
2) Дружок – не белый. Елисей – не серый
3) У Миши – черный котенок. У Максима – Мурлыка
4) У Лени – Елисей. У Димы – белый котенок
5) Дима не взял Фантика. Дружок – не серый
Одно из этих пяти утверждений ложное. У какого мальчика какой котенок?
4. Выбор сорта вина для заданного набора блюд.
Вариант №9
1. Перевод инфиксной арифметической записи в обратную польскую запись.
2. Поиск и генерация списка всех возможных расстановок максимального количества ферзей на доске (11 x 10) таким образом, чтобы ни один из ферзей не бил другого. Ферзём называется фигура, ходящая в любом направлении: по горизонтали, вертикали или диагонали.
3. В пяти домах разного цвета живут люди пяти национальностей. Они курят пять разных сортов сигарет, пьют пять разных напитков и содержат пять разных видов животных.
1) Англичанин живет в красном доме.
2) Швед держит собак.
3) Датчанин пьет чай.
4) Зеленый дом слева от белого.
5) Хозяин зеленого дома любить пить кофе.
6) Любитель Рall Мall содержит птиц.
7) Хозяин желтого дома курит Dunhill.
8) В центральном доме предпочитают молоко.
9) Норвежец живет в первом доме.
10) Курящий Вlend живет по соседству с хозяином кошек.
11) Хозяин лошадей живет рядом с тем, кто курит Dunhill.
12) Любитель пива курит Вluemasters.
13) Немец курит Рrince.
14) Норвежец живет рядом с синим домом.
15) Курящий Вlend живет по соседству с пьющим воду.
Кто держит рыбок?
4. Подбор учебных курсов, которые необходимо изучить для получения определенных навыков (веб-программист, windows-программист, unix-программист, тестировщик, архитектор ПО и т. д.).
Вариант №10
1. Вычисление арифметического выражения в инфиксной записи.
2. Генерация списка всех возможных расстановок максимального количества слонов на доске (14 x 5) клеток таким образом, чтобы ни один из слонов не бил другого. Слоном называется фигура, ходящая по диагонали.
3. Трое ребят вышли гулять с собакой, кошкой и хомячком. Известно, что Петя не любит кошек и живет в одном подъезде с хозяйкой хомячка. Лена дружит с Таней, гуляющей с кошкой. Определить, с каким животным гулял каждый из детей?
4. Определение места отдыха для предстоящего отпуска.
Вариант №11
1. Перевод обратной польской записи в инфиксную арифметическую запись.
2. Генерация списка всех возможных расстановок максимального количества ладей на доске (14 x 5) клеток таким образом, чтобы ни одна из ладей не била другую. Ладьёй называется фигура, ходящая прямо в горизонтальном или вертикальном направлении.
3. Витя, Юра и Миша сидели на скамейке. В каком порядке они сидели, если известно, что Юра сидел слева от Миши и справа от Вити.
4. Выбор высшего учебного заведения абитуриентом.
Вариант №12
1. Вычисление логического выражения в инфиксной записи (операции: and, xor, or, not, “)”, “(“).
2. Генерация списка всех возможных расстановок максимального количества слонов на доске (11 x 9) клеток таким образом, чтобы ни один из слонов не бил другого. Слоном называется фигура, ходящая по диагонали.
3. Пять пионеров Алик, Боря, Витя, Лена и Даша приехали в лагерь из 5 разных городов: Харькова, Умани, Полтавы, Славянска и Краматорска. Есть 4 высказывания:
1) Если Алик не из Умани, то Боря из Краматорска.
2) Или Боря, или Витя приехали из Харькова.
3) Если Витя не из Славянска, то Лена приехала из Харькова.
4) Или Даша приехала из Умани, или Лена из Краматорска.
Кто откуда приехал?
4. Выбор оптимального способа изучения иностранного языка в зависимости от бюджета, начального уровня знаний и других особенностей обучаемого.
Вариант №13
1. Перевод инфиксной арифметической записи в обратную польскую запись.
2. Поиск и генерация списка всех возможных расстановок максимального количества ферзей на доске (14 x 7) таким образом, чтобы ни один из ферзей не бил другого. Ферзём называется фигура, ходящая в любом направлении: по горизонтали, вертикали или диагонали.
3. Четыре человека играют в домино. Их фамилии Кузнецов, Токарев, Слесарев и Резчиков. Профессия каждого игрока соответствует фамилии одного из других игроков. Напротив Кузнецова сидит слесарь.
Напротив Резчикова сидит резчик.
Справа от Слесарева сидит токарь.
Кто сидит слева от кузнеца?
4. Выбор операционной системы персонального компьютера или рабочей станции (DOS, Windows, Linux, FreeBSD, MacOS 9, MacOS X, Digital UNIX и др.).
Вариант №14
1. Расстановка скобок в инфиксной арифметической записи в соответствии с общепринятыми приоритетами операций.
2. Генерация списка всех возможных расстановок максимального количества ладей на доске (11 x 9) клеток таким образом, чтобы ни одна из ладей не била другую. Ладьёй называется фигура, ходящая прямо в горизонтальном или вертикальном направлении.
3. Трое ребят вышли гулять с собакой, кошкой и хомячком. Известно, что Петя не любит кошек и живет в одном подъезде с хозяйкой хомячка. Лена дружит с Таней, гуляющей с кошкой. Определить, с каким животным гулял каждый из детей?
4. Выбор оптимального способа подключения к интернет (модем, локальная сеть, ADSL, GPRS, спутниковый канал, FloppyNet).
Вариант №15
1. Генерация списка <счастливых> шестизначных чисел (т. е. таких, сумма первых трёх цифр которых равна сумме трёх вторых).
2. Поиск такого пути коня на доске 10 x 12 клеток, что в каждой клетке доски конь побывает один и только один раз. При невозможности найти такой путь считается, что его не существует.
3. В одной школе уроки по истории, математике, биологии, географии, английскому и французскому языку вели три учителя – Морозов, Васильев и Токарев. Каждый из них преподавал два предмета.
Географ и учитель французского языка – соседи по дому.
Учитель биологии старше учителя математики. Морозов – самый молодой.
В понедельник первый урок по расписанию у Токарева, у биолога и у учителя французского языка.
В воскресенье Морозов, математик и учитель английского языка были на рыбалке.
Какие предметы преподает каждый учитель?
4. Подбор охотничьего снаряжения.
Вариант №16
1. Генерация всех возможных расстановок знаков арифметических операций и скобок в заданном шестизначном числе так, чтобы результатом полученного выражения было число 100.
2. Поиск такого пути коня на шахматной доске 12 x 12, что в каждой клетке конь побывает один и только один раз.
3. Есть четыре боксера: Томас Герберт, Герберт Френсис, Френсис Джеймс и Джеймс Томас.
Герберт намного сильнее Томаса.
Френсис сильнее и Томаса и Герберта. Герберт слабее Джеймса, но сильнее Френсиса.
В каком порядке нужно расположить боксеров от слабейшего к сильнейшему?
4. Формирование набора документов для совершения нотариального действия (купля-продажа квартиры, оформление наследства, завещания и т. д.).
Вариант №17
1. Генерация списка <счастливых> 2N-значных чисел (т. е. таких, сумма первых N чисел которых равна сумме вторых N чисел).
2. Генерация списка всех возможных расстановок максимального количества ладей на доске (14 x 8) клеток таким образом, чтобы ни одна из ладей не била другую. Ладьёй называется фигура, ходящая прямо в горизонтальном или вертикальном направлении.
3. Имеется четыре котенка: Дружок, Елисей, Фантик и Мурлыка – и четыре мальчика: Миша, Максим, Леня и Дима. Каждый мальчик взял себе котенка любимого цвета.
При этом:
1) Фантик – не рыжий. Мурлыка – не серый
2) Дружок – не белый. Елисей – не серый
3) У Миши – черный котенок. У Максима – Мурлыка
4) У Лени – Елисей. У Димы – белый котенок
5) Дима не взял Фантика. Дружок – не серый
Одно из этих пяти утверждений ложное. У какого мальчика какой котенок?
4. Выбор оптимальной стратегии действий для студента, находящегося на грани отчисления в сессию.
Вариант №18
1. Генерация всех возможных расстановок знаков арифметических операций и скобок в заданном N-значном числе так, чтобы результатом полученного выражения было заданное число M.
2. Поиск и генерация списка всех возможных расстановок максимального количества ферзей на доске (14 x 8) таким образом, чтобы ни один из ферзей не бил другого. Ферзём называется фигура, ходящая в любом направлении: по горизонтали, вертикали или диагонали.
3. В пяти домах разного цвета живут люди пяти национальностей. Они курят пять разных сортов сигарет, пьют пять разных напитков и содержат пять разных видов животных.
1) Англичанин живет в красном доме.
2) Швед держит собак.
3) Датчанин пьет чай.
4) Зеленый дом слева от белого.
5) Хозяин зеленого дома любить пить кофе.
6) Любитель Рall Мall содержит птиц.
7) Хозяин желтого дома курит Dunhill.
8) В центральном доме предпочитают молоко.
9) Норвежец живет в первом доме.
10) Курящий Вlend живет по соседству с хозяином кошек.
11) Хозяин лошадей живет рядом с тем, кто курит Dunhill.
12) Любитель пива курит Вluemasters.
13) Немец курит Рrince.
14) Норвежец живет рядом с синим домом.
15) Курящий Вlend живет по соседству с пьющим воду.
Кто держит рыбок?
4. Выбор оптимальной стратегии действий для студента, находящегося на грани отчисления в сессию.
Вариант №19
1. Генерация списка <счастливых> 2N-значных чисел (т. е. таких, сумма первых N чисел которых равна сумме вторых N чисел).
2. Генерация списка всех возможных расстановок максимального количества ладей на доске (13 x 12) клеток таким образом, чтобы ни одна из ладей не била другую. Ладьёй называется фигура, ходящая прямо в горизонтальном или вертикальном направлении.
3. Пять пионеров Алик, Боря, Витя, Лена и Даша приехали в лагерь из 5 разных городов: Харькова, Умани, Полтавы, Славянска и Краматорска. Есть 4 высказывания:
1) Если Алик не из Умани, то Боря из Краматорска.
2) Или Боря, или Витя приехали из Харькова.
3) Если Витя не из Славянска, то Лена приехала из Харькова.
4) Или Даша приехала из Умани, или Лена из Краматорска.
Кто откуда приехал?
4. Формирование набора документов для оформления Шенгенской визы.
Вариант № 20
1. Вычисление арифметического выражения в инфиксной записи.
2. Поиск такого пути коня на доске 10 x 12 клеток, что в каждой клетке доски конь побывает один и только один раз. При невозможности найти такой путь считается, что его не существует.
3. Имеется четыре котенка – Дружок, Елисей, Фантик и Мурлыка, и четыре мальчика – Миша, Максим, Леня и Дима. Каждый мальчик взял себе котенка любимого цвета.
При этом:
1) Фантик – не рыжий. Мурлыка – не серый
2) Дружок – не белый. Елисей – не серый
3) У Миши – черный котенок. У Максима – Мурлыка
4) У Лени – Елисей. У Димы – белый котенок
5) Дима не взял Фантика. Дружок – не серый
Одно из этих пяти утверждений ложное. У какого мальчика какой котенок?
4. Выбор книги в соответствии с пожеланиями читателя.
Вариант №21
1. Генерация всех возможных расстановок знаков арифметических операций в заданном N-значном числе так, чтобы результатом полученного выражения было заданное число M.
2. Генерация списка всех возможных расстановок максимального количества ладей на доске (14 x 8) клеток таким образом, чтобы ни одна из ладей не била другую. Ладьёй называется фигура, ходящая прямо в горизонтальном или вертикальном направлении.
3. Пять пионеров Алик, Боря, Витя, Лена и Даша приехали в лагерь из 5 разных городов: Харькова, Умани, Полтавы, Славянска и Краматорска. Есть 4 высказывания:
1) Если Алик не из Умани, то Боря из Краматорска.
2) Или Боря, или Витя приехали из Харькова.
3) Если Витя не из Славянска, то Лена приехала из Харькова.
4) Или Даша приехала из Умани, или Лена из Краматорска.
Кто откуда приехал?
4. Профориентация школьника.
Вариант №22
1. Вычисление арифметического выражения в инфиксной записи.
2. Поиск такого пути коня на доске 8 x 11 клеток, что в каждой клетке доски конь побывает один и только один раз. При невозможности найти такой путь считается, что его не существует.
3. Четыре человека играют в домино. Их фамилии Кузнецов, Токарев, Слесарев и Резчиков. Профессия каждого игрока соответствует фамилии одного из других игроков. Напротив Кузнецова сидит слесарь.
Напротив Резчикова сидит резчик.
Справа от Слесарева сидит токарь.
Кто сидит слева от кузнеца?
4. Диагностика неисправности телевизора.
Вариант №23
1. Генерация списка <счастливых> 2N-значных чисел (т. е. таких, сумма первых N чисел которых равна сумме вторых N чисел).
2. Генерация списка всех возможных расстановок максимального количества ладей на доске (13 x 12) клеток таким образом, чтобы ни одна из ладей не била другую. Ладьёй называется фигура, ходящая прямо в горизонтальном или вертикальном направлении.
3. Пять пионеров Алик, Боря, Витя, Лена и Даша приехали в лагерь из 5 разных городов: Харькова, Умани, Полтавы, Славянска и Краматорска. Есть 4 высказывания:
5) Если Алик не из Умани, то Боря из Краматорска.
6) Или Боря, или Витя приехали из Харькова.
7) Если Витя не из Славянска, то Лена приехала из Харькова.
8) Или Даша приехала из Умани, или Лена из Краматорска.
Кто откуда приехал?
4. Формирование набора документов для оформления Американской визы.
Вариант №24
1. Перевод инфиксной арифметической записи в прямую польскую запись.
2. Генерация списка всех возможных расстановок максимального количества слонов на доске (13 x 9) клеток таким образом, чтобы ни один из слонов не бил другого. Слоном называется фигура, ходящая по диагонали.
3. Четыре рыцаря, каждый в сопровождении оруженосца, съехались на берегу реки и хотят переправиться на другой берег. Есть лодка, которая может перевести только двух человек. Найти как могут переправиться рыцари и их оруженосцы на другой берег при условии, что оказавшись отдельно от своего рыцаря, ни один оруженосец не находился бы при этом в обществе других рыцарей.
4. Диагностика неисправности пылесоса.
Пример решения логической задачи (третье задание в лабораторной работе):
«В велосипедных гонках три первых места заняли Алеша, Петя и Коля. Какое место занял каждый из них, если Петя занял не второе и не третье место, а Коля – не третье?»
Решение задачи заключается в установлении зависимости между спортсменами и местами, которую можно описать табл. 1 (прочерки указывают известную информацию):
Таблица 1
Имя | 1-е место | 2-е место | 3-е место |
Алеша | |||
Петя | - | - | |
Коля | - |
Очевидно, Петя может занимать только первое место, тогда Коля – только второе, а Алеше достается третье (табл. 2).
Таблица 2
Имя | 1-е место | 2-е место | 3-е место |
Алеша | - | - | + |
Петя | + | - | - |
Коля | - | + | - |
При описании этой задачи на ПРОЛОГе получается следующая программа:
name(alex).
name(pier).
name(nike).
mesto(odin).
mesto(dva).
mesto(tri).
prizer(X, Y):-name(X),mesto(Y),X=pier, not(Y=dva),not(Y=tri); name(X),mesto(Y),X=nike, not(Y=tri);
name(X),mesto(Y),not(X=pier),not(X=nike).
solution(X1,Y1,X2,Y2,X3,Y3):-name(X1),name(X2),name(X3), mesto(Y1),mesto(Y2),mesto(Y3),prizer(X1,Y1),
prizer(X2,Y2), prizer(X3,Y3),Y1\=Y2,Y2\=Y3,Y1\=Y3, X1\=X2,X2\=X3,X1\=X3,!.
