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

244 группа

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

Студент TODO №1 №2 №3 №4 №5 №6 №7 Тест 1 №8 №9
184 1 2 3 4 1 2 3 1 2 3 4 1 2 3 1 2 3 1 1 2 1 2 3 1 2 Презентация Текст Защита
Zhilkin Fedor 4
Алексей Гирин
Андреев Сергей
Асеева Серафима 5
Афанасов Артем 14
Балашов Илья
Гуданова Варвара 5
Ивашева Валерия
Камкова Екатерина 10
Короткий Иван 27
Коёкин Ярослав 6
Мартынович Максим 21
Мендалиев Роман
Мишуров Илья 14
Панфилёнок Дмитрий 9
Пиккио Полина 28
Пономарёв Егор 20
Попок Артем 21
Смирнов Александр
Холодаева Екатерина

Задачи

Домашняя работа 9. 10.05.19
  1. Презентация
  2. Текст
  3. Защита
Домашняя работа 8. 19.04.19
Многопоточное программирование в F# (слайды)
О курсовых (слайды)
  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). Качать страницы надо параллельно.

Тест 1. 12.04.19
  1. Найти среднее арифметическое синусов всех чисел из списка с помощью хвостовой рекурсии. Конструкции императивного программирования использовать нельзя.

  2. Посчитать минимальное расстояние в дереве от корня до листьев. Конструкции императивного программирования использовать нельзя.

  3. Реализовать класс "Блокирующая очередь". При попытке получить значение из пустой очереди поток блокируется до тех пор, пока в очереди не появится значение. Реализация всех методов должна быть потокобезопасной. Мутабельные переменные разрешены, пользоваться библиотечной блокирующей очередью нельзя.

Домашняя работа 7. 05.04.19
Вычислительные выражения в 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
        }
    

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Домашняя работа 2. 22.02.19
Введение в F# (слайды)
Введение в F# (конспект)
  1. Реализовать функцию, которая выдает первую позицию вхождения заданного числа в список

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

  3. Написать mergesort: функцию, которая принимает список и возвращает отсортированный список

    Юнит-тесты ко всем задачам обязательны и должны быть в отдельном проекте. Сборка в CI тоже обязательна.

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

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

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

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

© 2014-2019 HwProj