Главная страница « Информация « 4 курс «

Курс «Введение в функциональное программирование» (Introduction to Functional Programming)


Лектор: доц. кафедры СП, канд. физ.-мат. наук Малышко Виктор Васильевич
Продолжительность: 36 часов лекции, 36 часов семинары, 72 часа самостоятельная работа.
Аудитория: С осени 2014 года курс читается для 427 и 428 групп. Осенью 2015 из-за исключительной ситуации курс читался также для 420 и 421 групп.
Формы отчётности: экзамен.
Автор программы: канд. физ.-мат. наук Малышко В. В.
Программа составлена по материалам канд. физ.-мат. наук Чернова А. В.
Группа Вконтакте: vk.com/sp_scheme [html].
Табличка с баллами: goo.gl/M51NkS [Гугль-диск]

Оглавление


Новости
Практические задания
Материалы по курсу

Новости


• Во вторник 5 сентября вместо прака будет прочитана лекция с 14-30 в 515.

• В осеннем семестре 2017-18 учебного года лекции читаются по понедельникам в ауд. 524 в 14.30 (по нечётным неделям) и в 16.20 (по четным неделям). Неделя, начинающаяся 4 сентября -- чётная. Прак проходит по вторникам с 14-30 до 17-55 в 515.

Практические задания


• На семинарах будет осуществляться приём заданий у студентов и возможно будут проводиться письменные контрольные работы, о которых будет отдельно объявлено. Для сдачи курса на положительную оценку необходимо выполнить полностью все практические задания. Осенью 2017 года для программирования используется среда Dr. Racket [html].

• Первое задание общее для всех -- «Доктор». Старая методичка по «Доктору» доступна онлайн [pdf]. Дополнения и исправления к ней даны ниже.

• Упражнения по «Доктору» делятся на 4 блока (1-3й обязательные, 4й по желанию):
1-й блок -- упражнения с 1 по 3. Максимальный балл -- 5. Сдача без штрафа до 10 октября.
2-й блок -- упражнения 4 и 5. Максимальный балл -- 7. Сдача без штрафа до 10 октября.
3-й блок -- упражнение 6. Максимальный балл -- 8. Сдача без штрафа до 10 октября.
4-й блок -- дополнительный, упражнение 7. Максимальный балл -- 15. Сдача без штрафа до 31 октября..
За каждую полную неделю просрочки начисляется штраф в размере 20%. Сумма штрафа не превышает 100%. При штрафе 100% сдача задания не принёсёт баллов, но задание всё равно должно быть сдано.

• Рекомендуется сдавать упражнения блоками. Датой сдачи блока считается дата последнего сданного упражнения из блока, при условии что код прислан вовремя. Во время сдачи программы будьте готовы ответить на вопросы по коду, а также по материалам лекций. Например, какой процесс порождает та или иная функция: итеративный или рекурсивный, и т. п.. Вам могут предложить оценить эффективность фрагмента Вашего кода и улучшить её, переписав фрагмент.

• После сдачи любого из блоков «Доктора» следует прислать код лектору. Если код не прислан в течение 7 дней после сдачи, по заданию аннулируется отметка о сдаче.

• Программы 1-3 блоков следует составлять на версии языка scheme/base (начинайте свой код с директивы #lang scheme/base). В них использование мутаторов (присваиваний и т. п.), мутируемых структур данных Racket, запрещено. Составленная в ходе выполнения упражнений программа должна быть показана лектору в ходе офлайновой сдачи. При переходе от начальных упражнений к последующим код следует дописывать так, чтобы функциональность программы расширялась (то, что было раньше, не портить).

• Рекомендации, на которые следует обратить внимание для получения полного балла по «Доктору»:

  1. В упражнении 2 следует переписать many-replace, реализовав корректный алгоритм. Попытки заплатками лечить неверный алгоритм не рассматриваются.

  2. В упражнении 3 (стр. 5 методички) на самом деле имеется в виду, что при построении ответной реплики фраза пользователя, взятая из истории, подвергается тому же преобразованию, что и в упражнении 2, только вместо результата qualifier к фразе приписывается префикс "earlier you said that". Например, если из истории выбрана реплика (you are not being very helpful to me), то по ней будет построен ответ (earlier you said that i am not being very helpful to you).

  3. В упражнении 5 следует пополнить набор ключевых слов и ответов и использовать гибкую (со *) структуру данных. Построение реплик должно быть реализовано так, чтобы можно было вносить изменения только в структуру данных, не исправляя код функции, составляющей реплику. Реализуйте случайный выбор ключевого слова для построения реплики, если этих слов несколько во фразе пользователя. Предусмотрите учёт ситуации, когда одно и то же ключевое слово относится к разным группам.

  4. В упражнении 6 следует переписать reply, добавив ему параметр — список стратегий построения реплики, в этом списке для каждой стратегии есть предикат — функция, определяющая применима ли стратегия, тело — функция, строящая реплику, вес — число, помогающее выбрать одну стратегию из нескольких применимых. Функция reply проверяет предикаты всех стратегий, составляет список применимых стратегий, случайно с учётом веса выбирает одну стратегию из этого списка, запускает её тело. Все стратегии ответов, имеющиеся в программе должны быть представлены в списке. Каких-либо способов построения ответов вне списка стратегий быть не должно.

• 4й дополнительный блок (упражнение 7) посвящёно дальнейшему совершенствованию «Доктора». Одним из путей совершенствования является добавление, так называемого, метауровня. Выполняя блок 3, мы реализовали один из способов выбора стратегии построения ответов. Этот способ заключался в том, что среди всех применимых стратегий с учётом их весов случайно применяется одна. Обозначим этот способ выбора как управляющую стратегию №1. Мы могли бы использовать другой способ выбора (другую управляющую стратегию). Например, можно упорядочить стратегии по весу, проверять сначала применимость более тяжёлых и, как только какая-то стратегия применима, останавливать проверку и использовать её (т. н. управляющая cond-стратегия с весами). Другие управляющие стратегии могли бы учитывать историю (предыдущие использования стратегий построения ответов), сложность выполняемых проверок и др.. На метауровне «Доктор» перед тем как выбирать стратегию построения ответа, анализирует, какие управляющие стратегии применимы в текущий момент. Из применимых управляющих стратегий «Доктор» выбирает одну (случайно, с учётом веса). Далее он запускает выбранную управляющую стратегию для выбора стратегии построения ответа.

Совершенствовать «Доктора» в рамках дополнительного блока можно с учётом истории в стратегии ответов по ключевым словам. «Доктор» может запоминать, какое ключевое слово было использовано и к какой группе ключевых слов относилась выбранная реплика (ведь одно слово может входить в несколько групп). В последующем «Доктор» мог бы, с одной стороны поддерживать тему, выбирая реплики-ответы из предыдущей группы, если есть такая возможность, с другой стороны, избегать повторов, заменяя * в заготовке реплики не на использованное ранее ключевое слово, а на родственные ключевые слова из одной группы с ним. Например, если предыдущий обмен репликами, касался матери пациента, «Доктор» мог бы поддержать тему семьи, но переключить разговор на других родственников пациента.

• Второе практическое задание выполняется по индивидуальному варианту. На выбор студента им может быть реализовано либо задание по генетическому программированию, либо задание по созданию игровой программы на основе минимаксного алгоритма.
• Сведения о вариантах 2-го задания опубликованы отдельно: «Создание игровой программы на основе минимаксного алгоритма» [html]; «Генетическое программирование» [html]. Для зарабатывания дополнительных баллов можно выполнить полностью или частично работу по другому (не совпадающему с выбранным) варианту. Например, Вы можете выбрать создание игры и дополнительно сдать 1й этап по «генетике».

• До окончания семестра необходимо сдать все задания, даже если сроки сдачи по ним прошли. Со стороны преподавателей будут приложены все усилия к тому, чтобы положительную оценку по экзамену получили только те студенты, которые сдадут все практические задания.

Материалы по курсу


• Слайды лекций (выкладываемые по мере чтения) и другие материалы ищите в ВК-группе. Если Вы испытываете затруднения с доступом в группу, запросите материалы по e-mail    у лектора. Все предоставленные материалы (в том числе задания анкет/контрольных/итоговых работ) должны быть использованы только лично Вами для учёбы во время изучения курса. Пожалуйста, не распространяйте их как-либо и где-либо.

Предупреждение


Размещение на других ресурсах, а также коммерческое использование материалов, опубликованных в данном разделе, возможно только с разрешения авторов. По всем вопросам пишите:   

  

© Кафедра системного программирования ВМК МГУ.

Обновлено: 11.9.2017