Практикум на ЭВМ (161гр, 2 семестр, 2010г)

Новости

• 09.04.2010 - конрольная работа по λ-исчислению (свободные/связанные переменные, подстановка, β-редукция, нормальная форма)

Часть 1 - Си

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

Задание 1

• Написать алгоритм нахождения наибольшего общего делителя на языке ассемблера.

Задание 2:

• Реализовать алгоритм обхода конем шахматной доски.
• (до 27.03.2010)

Задание 3:

• Реализовать интерпретатор для описанной ранее архитектуры.
• (до конца апреля)

Часть - 2: Haskell

Задание 1: простейшие функции (до 16.04.2010)

• длина списка
• сумма элементов списка
• добавление элемента в конец списка
• сумма квадратов
• перевернуть список
• реализовать функцию map, применяющую любую функции к каждому элементу списка (map :: (a -> b) -> [a] -> [b])

Задание 2: бесконечные списки (до 23.04.2010)

• Список чисел Фибоначчи через рекурсивное отношение
• Список чисел Фибоначчи через себя
• Сумма четных чисел Фибоначчи не превосходящих 4000000

Задание 3: бесконечные списки-2 (до 30.04.2010)

• Список всех простых чисел через тест на простоту
• Список всех простых чисел методом решета Эратосфена.
• Найти наибольший простой делитель числа 600851475143.
• Реализовать map через fold

Задание 4: Ввод-вывод

• head - вывести в стандартный поток вывода первые n строк из входа.
• Реализовать head следует в виде исполнимого модуля. Программа должна работать аналогично одноименной утилите Linux:
  • Программа имеет необязательный параметр - имя входного файла. Если параметр не указан, то чтение должно производиться из стандартного потока ввода.
  • Программе можно передать необязательный параметр "-n <число>" задающий количество строк для вывода. По умолчанию - 10.
  • Если на входе менее n строк, то выводится всё содержимое.

Задание 5: Элементы интерпретатора

• Реализовать работу с памятью как набор функций над типами:
• type Addr = Int
• type Value = Int
• type Memory = Addr -> Value
• Реализовать функцию
• goto : [a] -> (a -> Bool) -> [a]
• такую, что для типа AssemblerCode, где
• data Instruction a = Ldc Value | Ld Addr | St Addr | Add | Sub | Cmp | Br a | Jmp a | Lbl a | Ret
• type AssemblerCode = [Instruction String]
• и
• code :: AssemblerCode
• функция
• jmp l = goto code (let f (Lbl a) | a == l = True | _ -> False in f)
• по имени метки вернет хвост кода, начиная с этой метки.

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