Программирование

244 группа

Юрий Литвинов

Студент TODO №1 №2 №3 №4 №5 №6 №7 Тест 1 №9 Тест 2 Тест 3
214 1 2 3 4 5 1 2 3 4 1 2 3 1 2 3 1 1 2 1 2 1 2 3 1 Доклады Текст Презентация Отзыв Защита
Виктория Фомина 5
Вологин Дмитрий 20
Донина Дарья 20
Егорова Лада 2
Зиннатулин Тимур 3
Ким Юния 3
Костин Павел 24
Липаев Савелий 21
Лямин Владимир 2
Мамро Никита 2
Мирошникова Мария 28
Паршин Максим 2
Родина Алина 17
Симанок Данила 21
Соболевская Надежда 18
Щербина Олег 26

Задачи

Тест 3. 22.05.20
  1. Текст

    Сюда надо выложить текст отчёта по учебной практике

  2. Презентация

    Сюда надо выложить презентацию с защиты

  3. Отзыв

    Сюда надо выложить отзыв научного руководителя и/или консультанта

  4. Защита

    Сюда ничего выкладывать не надо, здесь будет отмечаться факт успешно пройденной защиты

Тест 2. 15.05.20
FAKE, Scaffold
Веб-приложения в комбинаторном стиле
Type Providers, F# Data
Дополнительные возможности F#
F# и анализ данных
  1. Доклады

    Сюда нужно загрузить презентацию

Домашняя работа 10. 08.05.20
Синтаксический анализ на F#, часть 2: FParsec vs FsLex/FsYacc
Ссылка на митинг в Zoom (начало в 17:10)
Исходники с демо FParsec и FsLex/FsYacc
Домашняя работа 9. 17.04.20
Синтаксический анализ на F#
Ссылка на митинг в Zoom (начало в 17:10)
  1. Разработать синтаксический анализатор для интерпретатора лямбда-выражений из домашней работы 3, с дополнительной функциональностью: возможностью именовать лямбда-выражения. Интерпретатор должен принимать на вход строку или файл (должно поддерживаться и то и другое) с набором именованных определений и лямбда-выражением, в котором именованные определения используются. Должно выдаваться в виде строки лямбда-выражение, полученное бета-редукцией входного лямбда-выражения. Лямбда во входных данных обозначается символом \, именованное определение начинается с let и может быть только одно на строке. Должны поддерживаться лямбда-абстракции с несколькими "параметрами". Пример:

    let S = \ x y z.x z (y z)
    let K = \x y.x
    S K K
    

    Должно получиться в качестве ответа:

    \x.x
    

    (или любой другой терм, альфа-эквивалентный этому)

    Для синтаксического анализа использовать FParsec.

Тест 1. 10.04.20
  1. Найти сумму всех чётных чисел Фибоначчи, не превосходящих миллиона. Конструкции императивного программирования использовать нельзя.

  2. Реализовать функцию, возвращающую все элементы двоичного дерева, удовлетворяющие переданному как параметр условию. Конструкции императивного программирования использовать нельзя.

  3. Реализовать класс "Очередь". При попытке получить значение из пустой очереди должно бросаться исключение. Конструкции императивного программирования использовать можно, System.Collections.Generic --- нет.

Домашняя работа 8. 03.04.20
Сборка мусора в .NET
Ссылка на митинг в Zoom (начало в 17:10)
Домашняя работа 7. 27.03.20
Многопоточное программирование в F#
Ссылка на митинг в Zoom (начало в 17:10)
  1. Переделать на F# задачу Lazy из предыдущего семестра (с некоторой дополнительной функциональностью), то есть реализовать интерфейс, представляющий ленивое вычисление:

    type ILazy<'a> =
    abstract member Get: unit -> 'a

    Объект Lazy создаётся на основе вычисления (представляемого лямбда-функцией supplier : unit -> 'a)
    - Первый вызов Get() вызывает вычисление и возвращает результат
    - Повторные вызовы Get() возвращают тот же объект, что и первый вызов
    - В однопоточном режиме вычисление должно запускаться не более одного раза, в многопоточном — как получится (см. далее)

    Создавать объекты надо не вручную, а с помощью класса LazyFactory, имеющего три метода наподобие

    static member CreateSingleThreadedLazy supplier

    возвращающих три разные реализации Lazy<'a>:
    - Простая версия с гарантией корректной работы в однопоточном режиме (без синхронизации)
    - Гарантия корректной работы в многопоточном режиме; вычисление не должно производиться более одного раза (что-то наподобие многопоточного синглтона, без лишних блокировок)
    - То же, что и предыдущее, но lock-free; вычисление может производиться более одного раза, но при этом Lazy.Get всегда должен возвращать один и тот же объект (то есть результаты "лишних" вычислений должны теряться)

  2. Написать функцию, принимающую адрес веб-страницы, скачивающую все веб-страницы, на которые есть ссылки с указанной, и печатающую информацию о размере каждой в формате "адрес страницы --- число символов". Ссылки нужно обрабатывать только заданные в форме <a href="http://...">. Для поиска ссылок на странице могут быть полезны регулярные выражения (класс System.Text.RegularExpressions.Regex). Качать страницы надо параллельно.

Домашняя работа 6. 20.03.20
Вычислительные выражения в F#
  1. Реализовать Workflow, выполняющий математические вычисления с заданной (как аргумент Builder-а) точностью. Например,

        rounding 3 {
            let! a = 2.0 / 12.0
            let! b = 3.5
            return a / b
        }
    

    должно возвращать 0.048

  2. Реализовать Workflow, выполняющий вычисления с числами, заданными в виде строк. Например,

    let result = calculate {
            let! x = "1"
            let! y = "2"
            let z = x + y
            return z
        }
    

    должно возвращать значение, содержащее 3, а

    let res = calculate {
            let! x = "1"
            let! y = "Ъ"
            let z = x + y
            return z
        }
    

    должно возвращать значение, указывающее на отсутствие результата.

Домашняя работа 5. 13.03.20
Объектно-ориентированное программирование в F#
  1. В объектно-ориентированном стиле смоделировать работу локальной сети:

    • в сети есть несколько компьютеров, связанных друг с другом (каким образом - можно задавать, например, матрицей смежности);
    • на каждом компе стоит ОС (Windows, Linux, etc...);
    • в сети гуляют вирусы, так что для каждой машины есть ненулевая вероятность заразиться (вероятность зависит от типа ОС), заражаются компьютеры, непосредственно соединённые с заражёнными;
    • заражения (и проверки, заразился компьютер или нет) происходят дискретно - по ходам.

    Требуется периодически выводить состояние сети.

    Необходимы также юнит-тесты, проверяющие корректность работы алгоритма заражения: если вероятность заражения всегда 1, вирус должен вести себя как обход в ширину, если вероятность 0 --- никто не должен заражаться. Могут быть полезны mock-объекты.

Домашняя работа 4. 06.03.20
Генерики в F#
  1. Реализовать функцию, которая по произвольной строке проверяет корректность скобочной последовательности в этой строке. Скобки бывают трёх видов.

  2. Записать в point-free стиле func x l = List.map (fun y -> y * x) l. Выписать шаги вывода и проверить с помощью FsCheck корректность результата

  3. Написать программу - телефонный справочник. Она должна уметь хранить имена и номера телефонов, в интерактивном режиме осуществлять следующие операции:
    1. выйти
    2. добавить запись (имя и телефон)
    3. найти телефон по имени
    4. найти имя по телефону
    5. вывести всё текущее содержимое базы
    6. сохранить текущие данные в файл
    7. считать данные из файла

    Во всех задачах мутабельность всё ещё запрещена

Домашняя работа 3. 28.02.20
Нетипизированное λ-исчисление
  1. Выполнить бета-редукцию λ-терма ((λa.(λb.b b) (λb.b b)) b) ((λc.(c b)) (λa.a)). Решение (в виде последовательности преобразований) набрать в TeX-е и выложить файл .tex на GitHub. Может помочь https://www.papeeria.com/ или https://www.overleaf.com/

  2. Докажите, что S K K = I. Доказательство набрать в TeX-е и выложить на GitHub. Делать надо самостоятельно, это известное (и несложное) упражнение, так что гуглить нечестно.

  3. Реализовать интерпретатор лямбда-выражений, выполняющий бета-редукцию по нормальной стратегии. Лямбда-выражения задаются через размеченные объединения. Должна поддерживаться альфа-конверсия для избежания захвата свободных переменных. Примечание: если не извращаться и делать всё по определению, задача простая.

Домашняя работа 2. 21.02.20
Продолжение про F# (слайды)
Продолжение про F# (текст)
Пример репозитория с CI для .NET Core на AppVeyor и Travis
  1. Реализовать три варианта функции, подсчитывающей количество четных чисел в списке (с использованием стандартных функций map, filter, fold). Использование рекурсии не допускается, зато нужен FsCheck для проверки функций на эквивалентность

  2. Реализовать функцию, применяющую функцию к каждому элементу двоичного дерева и возвращающую новое двоичное дерево, каждый элемент которого --- результат применения функции к соответствующему элементу исходного дерева (map для деревьев)

  3. Посчитать значение дерева разбора арифметического выражения, заданного через вложенные discriminated union-ы

  4. Реализовать функцию, генерирующую бесконечную последовательность простых чисел

    Ко всем задачам обязательны комментарии, юнит-тесты и CI

Домашняя работа 1. 14.02.20
Введение в F# (слайды)
Введение в F# (конспект)
Онлайн-интерпретатор, умеющий F#
Домашняя страница F#
Хороший блог про F#
  1. Посчитать факториал

  2. Посчитать числа Фибоначчи (за линейное время)

  3. Реализовать функцию обращения списка (за линейное время)

  4. Реализовать функцию, которая принимает на вход n и m и возвращает список из элементов [2n; 2n + 1; ...; 2n + m]

  5. Реализовать функцию, которая выдает первую позицию вхождения заданного числа в список

© 2014-2020 HwProj