Практикум на ЭВМ, весна 2013, 171

Новости

    • 02.04.2013 - Опубликованы комментарии к некоторым заданиям на F#.

Часть 1 - Си/Интерпретатор SVM

Описание языка ассемблера и архитектуры виртуальной машины.

Задание 1.

    • Написать алгоритм нахождения наибольшего общего делителя на языке ассемблера.
    • В задаче закодировать входные данные - 2330 и 3770, как первые две инструкции ldc.

Задание 2.

    • Реализовать интерпретатор SVM

Задание 3. На языке ассемблера SVN реализовать следующие задачи:

    • Посчитать сумму чётных чисел Фибоначчи не превосходящих 2000000.
    • Найти 10001-ое простое число.
    • * Найти наибольший простой делитель числа 208574561.

Задание 4. Design Document

    • Написать документ описывающий предложения по реализации процедур, вызовов и передачи параметров при вызовах в языке ассемблера и виртуальной машине SVN.
    • Хороший документ должен содержать следующую информацию:
      • Заголовок, автор (группа)
      • Введение - пара предложений с описанием контекста документа (что это все про SVM)
      • Постановка задачи: мотивация для введения реализации процедур и требования к ним.
      • Основная часть (предложение): рассмотреть синтаксис и семантику команд, которые предлагается ввести.
      • Заключение: анализ того, что получилось.
      • Приложение: примеры программ с использованием предложенного синтаксиса.
      • (Можно не выносить в приложения, а оставить в основной части.)

Инфраструктурное

Для выкладывания заданий каждый должен создать логин на сайте https://github.com и репозиторий для заданий.

  • Все задания должны быть выложены в репозиторий на github.

Задание git-training: записаться в список в репозитории https://github.com/vpolozov/git-training

Часть - 2: F#

Задание 1: Введение в синтаксис F#/ императивное программирование на F#

  • Решить первые 10 проблем projecteuler.net
  • * Либо решить любые 3 проблемы с projecteuler.net с количеством сдавших менее 10000.

Замечание 1. Для реализации некоторых заданий точности типа int (int32) может не хватить. Но есть несколько целочисленных альтернатив:

      • int64 - 64-битное знаковое целое. Пример записи литерала: 123456L
      • bigint - целое число произвольной точности (синоним для System.Numerics.BigInteger - http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.aspx). Пример записи литерала: 123456I

или не целочисленных:

      • float - аналог double в Си. Не рекомендуется для точных вычислений и десятичной арифметики. Пример: 123.456
      • decimal - десятичное число с плавающей точкой: 127 бит - 1 бит знак, 96 битовое целое число (~ ±7.9×1028), и оставшиеся биты могут принимать значения 0-28, что соответствует количеству знаков после запятой. Пример: 123.456M

Для конвертации типа, как правило, можно использовать функцию с тем же именем. Например, "int x" - приведение к целому, "float n" - приведение к типу float.

Подробнее про литералы различных типов можно посмотреть тут: http://msdn.microsoft.com/en-us/library/dd233193.aspx

Задание 2: Без использования изменяемых значений (mutable, ref и т.п.) реализовать следующие функции:

    • Добавление элемента в конец списка
    • addToEnd :: 'a -> list 'a -> list 'a
    • Конкатенация списков
    • append :: 'a list -> 'a list -> 'a list
    • "Перевернуть" список
    • reverse :: 'a list -> 'a list
    • Постараться сделать за O(n) операций
    • Поиск элемента в списке по предикату
    • find :: ('a -> bool) -> 'a list -> 'a option
  • Реализовать функцию map, применяющую любую функции к каждому элементу списка
  • map :: ('a -> 'b) -> 'a list -> 'b list
  • используя либо библиотечную функцию List.foldBack либо List.fold
  • Для всех функций написать тесты, например, как функцию (unit -> bool)

Задание 3: Создать алгебраический тип данных (АДТ) соответствующий бинарному дереву поиска и реализовать следующие функции для работы с ним:

    • добавление элемента в дерево
    • проверка, есть ли такой элемент в дереве
    • удаление элемента из дерева
    • "красивая" печать дерева

Задание 4: Реализовать библиотеку длинной арифметику используя объектно-ориентированный подход :

    • Тип, соответствующий целому числу со знаком без ограничений по длине.
    • Операции реализовать как методы (члены, member) данного типа:
      • Сложение
      • Вычитание
      • Умножение
      • * Деление

Успеваемость

2012-2013.IT.171