Главная / Программирование / Функциональное программирование

Функциональное программирование - ответы на тесты Интуит

Правильные ответы выделены зелёным цветом.
Все ответы: Курс знакомит слушателей с парадигмой функционального программирования, в которой решение задач сводится к описанию функций, перерабатывающих некоторые входные данные в выходные и строящихся из более простых функций на основе принципов функциональной абстракции и аппликации. Рассматриваются теоретические основы функционального программирования (лямбда-исчисление, комбинаторная логика, вопросы вычислимости), на примере функционального подхода дается представление о некоторых теоретических разделах компьютерных наук (семантика языков программирования, доказательство программ). С другой стороны курс содержит значительную практическую составляющую, основанную на промышленном языке программирования F# (входит в состав Microsoft Visual Studio 2010), рассматриваются вопросы использования функциональных языков для построения компиляторов, грамматического разбора и т.д.

Как можно отделить голову и хвост списка?

(1) с помощью сопоставления с образцом let

(2) с помощью сопоставления с образцом match

(3) с помощью функций hd и tl

(4) с помощью конструктора списков cons

Как связаны двоичные деревья и деревья общего вида?

(1) дерево общего вида является частным случаем двоичного дерева

(2) двоичное дерево является частным случаем дерева общего вида

(3) любое дерево общего вида однозначно представимо в виде двоичного дерева

Какие есть основные модели вычислений?

(1) нормальные алгоритмы Маркова

(2) машина фон-Неймана

(3) машина Тьюринга

(4) логика высказываний

Как определяются значения логического типа при формальном построении языка функционального программирования?

(1) true = 1; false = 0

(2) true = λx.λy.x ; false = λx.λy.y

(3) true = λx.λy.xy ; false = λx.λy.yx

(4) как атомарные константы T и F

В динамических языках программирования:

(1) тип переменной определяется заранее, но память под нее может выделяться динамически

(2) тип переменной определяется в начале выполнения программы и остается неизменным в процессе выполнения

(3) тип переменной определяется в процессе выполнения программы и может меняться

(4) переменная всегда имеет строковый тип, но ее значения могут интерпретироваться по-разному

Eval/Apply-интерпретатор состоит из

(1) Конечного автомата с двумя состояниями Eval и Apply

(2) двух основных взаимно-рекурсивных функций Eval и Apply

(3) функции вычисления выражения Eval, которая оперирует с деревом функциональных аппликаций

Какого типа выражение <@@ (1+2)*3 @@>?

(1) int

(2) int → int

(3) unit → int

(4) Expr

За счет чего функциональные программы содержат меньше ошибок?

(1) функциональные программы не содержат побочных эффектов

(2) функциональные программы короче

(3) на функциональных языках автоматически контролируются ошибки типа переполнения буфера

(4) функциональные программ более просты и понятны для программиста

Какие основные операции в чистом λ-исчислении?

(1) абстракция и аппликация

(2) аппликация и инкапсуляция

(3) абстракция и инкапсуляция

(4) абстракция, аппликация и сложение

C помощью какой функции можно эффективно посчитать сумму элементов целочисленного списка?

(1) iter

(2) iteri

(3) fold

(4) Map

В каком порядка обходятся поддеревья в инфиксном порядке обхода?

(1) корень, левое поддерево, правое поддерево

(2) левое поддерево, корень, правое поддерево

(3) левое поддерево, правое поддерево, корень

(4) корень, правое поддерево, левое поддерево

Какие базовые операции чистого лямбда-исчисления?

(1) аппликация

(2) абстракция, аппликация

(3) абстракция, аппликация, композиция

(4) абстракция, аппликация, композиция, сложение

Как определяется конструкция let?

(1) let x=e1 in e2 => (λx.e2)e1

(2) let x=e1 in e2 => (λx.e1)e2

(3) let x=e1 in e2 => (λf.[x/f]e2)e1

(4) Y(λf.[x/f]e1) e2

Какое множество значений у прямой суммы T1+T2?

(1) множество пар <x,y> : x T1, y ∈T2

(2) объединение множеств T1∪T2

(3) помеченное объединение { <o,x> | x ∈T1 } ∪ { <1,y> | y ∈T2 }

(4) множество T1∪T2\(T1ЗT2)

Какие стеки включает в себя SECD-машина?

(1) стек объектов вычислений, среда, управляющая строка, стек возвратов

(2) стек операций, стек операндов, управляющая строка, стек возвратов

(3) стек объектов вычислений, управляющая строка

(4) стек объектов операндов, стек возвратов, среда

Что такое монада?

(1) Механизм реализации ввода-вывода в функциональных языках

(2) языковый механизм для расширения системы типов и внесения дополнительных свойств

(3) полиморфный монадический тип, для которого определены операции return и bind

(4) полиморфный монадический тип, для которого определены операции return и bind, обладающие определенными свойствами

Какой принцип построения функциональных программ?

(1) программа строится из набора функций, каждая из которых перерабатывает входные данные в выходные. Функции также могут рассматриваться как данные

(2) программа строится из набора функций, каждая из которых перерабатывает входные данные в выходные. Существует четкое разделение между данными и функциями

(3) программа строится из набора вызывающих друг друга подпрограмм (процедур и функций)

(4) программа представляет собой одно большое арифметическое выражение

Что такое каррирование?

(1) представление функции от нескольких аргументов как функции от одного аргумента, возвращающей результат-функцию

(2) представление функции от нескольких аргументов как функции от одного аргумента – упорядоченной n-ки

(3) представление функции от нескольких аргументов как функции от одного аргумента спискового типа

(4) запрет на использование функций от нескольких аргументов

Какой тип имеет функция map?

(1) (‘a→’b) → ‘a list → ‘b list

(2) (‘a → ‘a) → ‘a list → ‘a list

(3) ‘a → ‘a → ‘a list → ‘a list

(4) (‘a → bool) → ‘a list → ‘a list

Что такое дерево поиска?

(1) одноуровневое дерево общего вида, в котором все узлы упорядочены

(2) дерево общего вида, в котором все узлы упорядочены

(3) двоичное дерево, в котором все листья упорядочены

(4) двоичное дерево, в котором для каждого узла все элементы левого поддерева меньше, а правого поддерева – больше текущено.

Как расставляются скобки в выражении λx.λy.e1e2?

(1) (λx.(λy.e1)e2)

(2) λx.((λy.e1)e2)

(3) (λx.λy).(e1e2)

(4) (λx.(λy.e1e2))

Что такое замыкание?

(1) фрагмент программы, в котором данная переменная имеет область видимости

(2) лексическая область видимости имени

(3) функция с некоторым контекстом вычислений, сохраненным на момент определения функции

(4) функция с некоторым текущим контекстом вычислений

Какой будет наиболее общий тип для функции tl: let tl x::t = t?

(1) ‘a list → ‘a list

(2) list → list

(3) int list → int list

(4) ‘a list → ‘a

Программа, порожденная генератором fsyacc:

(1) строит по входному тексту программы синтаксическое дерево

(2) строит по последовательности лексем синтаксическое дерево программы

(3) строит по входному тексту программы последовательность лексем

(4) строит по входному тексту программы код абстрактной машины

Чему равен результат выражения nondet { return 10; } для монады недетерминированных вычислений?

(1) 10

(2) [10]

(3) Nondet(10)

(4) Nondet<10>

Какая алгоритмическая модель лежит в основе функционального программирования?

(1) λ-исчисление

(2) логика предикатов 1-го порядка

(3) логика высших порядков

(4) машина Тьюринга

В чем разница между конструкциями fun и function в F#?

(1) fun – это более короткий способ записи function

(2) function может описывать функции от одного аргумента, fun – каррированные функции от нескольких аргументов

(3) fun служит для задания функциональной константы, function – для описания функции

(4) function служит для задания функциональной константы, fun – для описания функции

Какой функции эквивалентна запись [ for x in L → x*2 ]?

(1) filter

(2) map

(3) reduce

(4) fold

Что такое продолжение (continuation)?

(1) оператор, указывающий, откуда продолжить вычисления

(2) оператор, помогающий компилятору распознать хвостовую рекурсию

(3) передаваемая в качестве параметра функция, которую необходимо вызвать по завершении выполнения текущей функции

Какое из приведенных ниже преобразований является примером бета-редукции?

(1) (λx.sin x) z → sin z

(2) (λx.sin x) z → (λy.sin y) z

(3) sin 0 → 0

(4) (λx.sin x) 0 → 0

Пусть L – генератор последовательности длины n. Какова сложность операции map f L?

(1) O(1)

(2) O(n)

(3) O(log n)

(4) O(n²)

Что такое операционная семантика языка программирования?

(1) описание семантики языка в терминах изменения состояний или сведением конструкций языка в более примитивной абстрактной машине

(2) описание семантики путем сопоставления конструкций языка с некоторыми формальными математическими объектами

(3) описание того, как некоторые свойства меняются в процессе применения конструкций языка

Как правильно параллельно вычислить сумму 100-го и 200-го чисел Фибоначчи?

(1) sum(Async.RunSynchronously(Async.Parallel([async { return (fib 100) }, async { return (fib 200) }])))

(2) Async.RunSynchronously(sum(Async.Parallel([async { return (fib 100) }, async { return (fib 200) }])))

(3) Async.Parallel((fib 100)+(fib 200))

(4) Async.Parallel(async { return (fib 100) + (fib 200) })

Почему функциональное программирование сейчас представляет повышенный интерес для изучения?

(1) это молодое направление программирования

(2) многие программные проекты сейчас реализуются на функциональных языках

(3) функциональный подход помогает решать такие проблемы, как распараллеливание вычислений

Как описываются рекурсивные функции в F#?

(1) специальным оператором rec

(2) добавлением rec в операцию связывания let

(3) в F# нельзя описывать рекурсивные функции

Какие условия являются необходимыми для хвостовой рекурсии?

(1) линейная рекурсия

(2) косвенная рекурсия

(3) рекурсивный вызов является последним в теле функции

Какой самый внутренний редекс в выражении (λx.λy.y) ((λz.z z) (λz.z z))?

(1) (λz.z z)

(2) (λz.z z) (λz.z z)

(3) (λx.λy.y) ((λz.z z) (λz.z z))

(4) (λx.λy.y)

Что такое домены?

(1) произвольные множества, на которых определяются значения λ-выражений

(2) полные множества, на которых определяются значения λ-выражений

(3) частично-упорядоченные множества, на которых определяются значения λ-выражений

(4) полные частично-упорядоченные множества, на которых определяются значения λ-выражений

В каком представлении матриц проще реализовать операцию транспонирования?

(1) в виде списка списков

(2) в порядковом представлении

(3) сложность реализации при списковом и порядковом представлении примерно одинакова

Какой будет следующий шаг при нормальном порядке редукции выражения (λx.x+x)(2+3)?

(1) (2+3)+(2+3)

(2) (λx.x+x) 5

(3) 10

(4) (λx.(2+3)+x)(2+3)

Неразрешимость проблемы остановки означает:

(1) невозможность построения программы, которая по произвольному алгоритму и входным данных определит, остановится ли он или нет

(2) невозможность построения программы, которая будет останавливаться на определенных входных данных и зацикливаться на других

(3) невозможность построения программы, которая по некоторой программе будет определять возможные случаи зацикливания

Какова сложность добавления элемента на первое место списка длины n?

(1) O(1)

(2) O(n)

(3) O(log n)

(4) O(n²)

Что является следствием теоремы Черча-Россера?

(1) применение нормального порядка редукции позволяет всегда получить нормальную форму

(2) применение нормального порядка редукции предпочтительнее, чем аппликативного

(3) если нам удалось редуцировать выражение до нормальной формы, то эта форма единственная, вне зависимости от порядка редукции

(4) если нам удалось редуцировать выражение до нормальной формы, то эта форма единственная с точностью до альфа-преобразования, вне зависимости от порядка редукции

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

(1) с помощью оператора неподвижной точки Y

(2) с помощью рекуррентных соотношений

(3) с помощью комбинаторов I, K

Какой будет результат выполнения let x::y = [1;2;3;4] ?

(1) Ошибка

(2) x=[1;2;3;4], y=[]

(3) x=1, y=2

(4) x=1, y=[2;3;4]

(5) x=[1;2;3], y=4

Как правильно описать дерево общего вида на F#?

(1) type 'T tree = Leaf of 'T | Node of 'T*('T tree list)

(2) type 'T tree = Leaf of 'T | Node of 'T*T'

(3) type 'T tree = Nil | Leaf of 'T | Node of 'T -> ('T tree list)

(4) type 'T tree = Nil | Leaf of 'T | Node of 'T*T’*(’T tree)

Какая модель вычислений служит формальной основой функционального программирования?

(1) Машина Тьюринга

(2) логика предикатов

(3) логика высказываний

(4) комбинаторная логика

При введении списков, как определяется функция отделения первого элемента hd?

(1) hd = λx.x true

(2) hd cons x y = x

(3) hd = λh.λt.λs.s h t

(4) hd x = x false

При статическом контроле типов:

(1) тип переменной известен на момент компиляции

(2) достигается высокая эффективность программы в момент выполнения

(3) возможно построить более богатую систему типов по сравнению с динамическим

(4) возможно устранять большее количество ошибок на этапе компиляции

Какой тип имеет функция eval в Eval/Apply-интерпретаторе?

(1) eval : expr→env→expr

(2) eval : expr→expr

(3) eval : expr→env→value

(4) eval : env→expr

Что означает запись <@ fun x→ x*2 @>?

(1) создается отложенное вычисление для вычисления функции x*2

(2) создается дерево выражения, описывающего функцию удвоения

(3) в данном случае запись эквивалентна fun x → x*2

Какие операторы традиционно отсутствуют в функциональных языках?

(1) оператор присваивания

(2) оператор присваивания и операторы циклов с пред- и пост-условиями

(3) оператор присваивания и условный оператор

(4) все операторы присутствуют

Какие недостатки "классической" нотации для определения функции f(x)=2*x+1?

(1) она может быть истолкована неоднозначно

(2) она неудобна для программирования

(3) в ней сложно различать свободные и связанные переменные

С помощью какой функции можно удалить из списка все элементы, стоящие на четных позициях?

(1) iter

(2) map

(3) filter

(4) ни одна из перечисленных

В каком порядка обходятся поддеревья в префиксном порядке обхода?

(1) корень, левое поддерево, правое поддерево

(2) левое поддерево, корень, правое поддерево

(3) левое поддерево, правое поддерево, корень

(4) корень, правое поддерево, левое поддерево

Какая операция повышает порядок функции?

(1) аппликация

(2) абстрация

(3) композиция

(4) унификация

Как определяется конструкция letrec?

(1) letrec x=e1 in e2 => (λx.e2)e1

(2) letrec x=e1 in e2 => (λx.e1)e2

(3) letrec x=e1 in e2 => (λf.[x/f]e1)e2

(4) с помощью комбинатора неподвижной точки Y

Какое множество значений у типа T1 → Т2?

(1) множество всех функций из T1 в T2

(2) множество всех непрерывных функций из T1 в T2

(3) множество всех функций из T1 в T2, дополненное элементом nil

(4) множество всех функций из T1 в T2, дополненное элементом ^

Что помещается в стек возвратов D SECD-машины?

(1) номер инструкции, на который необходимо вернуться после вычисления функции

(2) окружение, в котором вычислялась вызываемая функция

(3) состояние стека вычислений до вызова функции

(4) состояние стеков S, E и C до вызова функции

Укажите правильное монадическое свойство:

(1) return x >>= f є f x

(2) return x >>= f є x f

(3) return (f x) >>= g є f(g x)

(4) (return x >>= f) є return (x>>=f)

Какие основные способы борьбы со сложностью используются в функциональных программах?

(1) функциональная абстракция и функциональная декомпозиция

(2) наследование и полиморфизм

(3) функциональная абстракция и мемоизация

(4) функциональная декомпозиция и динамическое связывание

Какой тип у каррированной функции сложения целых чисел?

(1) int -> (int -> int)

(2) (Int -> int) -> int

(3) (int Ч int) -> int

(4) Int -> int

Какой тип имеет функция filter?

(1) (‘a→’b) → ‘a list → ‘b list

(2) ‘a → ‘b → ‘a list → ‘b list

(3) ‘a → bool → ‘a list → bool list

(4) (‘a → bool) → ‘a list → ‘a list

Какова сложность поиска в дереве поиска?

(1) O(log n)

(2) O(n)

(3) между O(log n) и O(n), в зависимости от сбалансированности дерева

(4) между O(n) и O(n2), в зависимости от количества элементов дерева

Как расставляются скобки в выражении f sin x*2?

(1) ((f sin) x)*2

(2) (f (sin x))*2

(3) f(sin(x*2))

(4) f(sin(x))*2

Пусть геометрическое преобразование определяется функцией трансляции координат int*int → int*int. Мы хотим определить функцию сдвига translate : int*int, которая возвращался бы замыкание. Как это сделать?

(1) let translate (dx,dy) = fun (x,y) → (x+dx, y+dy)

(2) let translate dx dy = function x → function y → (x+dx, y+dy)

(3) let translate (dx,dy) = closure { fun (x,y) → (x+dx, y+dy) }

(4) let translate dx dy = function (x,y) → closure (x+dx, y+dy)

Что необходимо сделать для вывода типов в некотором выражении?

(1) проверить, что реальные типы всех имен, входящих в выражение, соответствуют указанным

(2) проверить, что реальные типы всех подвыражений соответствуют указанным

(3) решить систему функциональных уравнений относительно типов

При реализации синтаксического анализатора методом рекурсивного спуска, какой тип удобно использовать для функции parse:

(1) token list → expr

(2) token list → expr → token list

(3) token list → (expr * token list)

(4) (expr*token list) → (expr*token list)

Какого типа выражение async { return 10; }?

(1) int

(2) unit → int

(3) Async

(4) Async<int>

Какая алгоритмическая модель лежит в основе императивного программирования?

(1) λ-исчисление

(2) логика предикатов 1-го порядка

(3) логика высших порядков

(4) машина Тьюринга

В чем разница между конструкциями fun и function в F#?

(1) fun – это более короткий способ записи function

(2) в function может использоваться сопоставление с образцом, в fun – нет

(3) fun служит для задания функциональной константы, function – для описания функции

(4) function служит для задания функциональной константы, fun – для описания функции

Какой список будет порожден конструкцией [1..2..10]?

(1) конструкция недопустима

(2) [1;2;3;4;5;6;7;8;9;10]

(3) [1;3;5;7;9]

(4) [2;4;6;8;10]

Как можно свести нелинейно-рекурсивную функцию к хвостовой рекурсии?

(1) используя стек для хранения оставшихся заданий на обработку

(2) используя дерево для представления цепочки вычислений

(3) используя продолжения для разворачивания рекурсии в цепочку функций

Какое из приведенных ниже преобразований является примером альфа-редукции?

(1) (λx.sin x) z → sin z

(2) (λx.sin x) z → (λy.sin y) z

(3) sin 0 → 0

(4) (λx.sin x) 0 → 0

Возможно ли в F# использовать ленивые вычисления?

(1) нет, F# - энергичный язык

(2) да, используя конструкции Lazy/Force

(3) да, используя последовательности seq

(4) да, используя ключи компилятора

Что такое денотационная семантика языка программирования?

(3) описание того, как некоторые свойства меняются в процессе применения конструкций языка

Сколько потоков выполнения операционной системы будет порождаться при выполнении операции Async.RunSynchronously(Async.Parallel([ for i in 1..100 → async { return fib(i) }]))?

(1) один

(2) менее 100

(3) 100

(4) 200

За счет чего функциональные программы обычно содержат меньше ошибок, чем императивные?

(1) они короче, поэтому меньше шанс ошибиться

(2) программисты на функциональных языках обычно умнее, поэтому делают меньше ошибок

(3) функциональные программы проще отлаживать из-за их естественной модульности

(4) функциональные программы не содержат побочных эффектов

Как описать повторяющиеся действия в функциональном языке?

(1) с помощью циклов

(2) с помощью оператора перехода

(3) с помощью рекурсии

(4) любым их перечисленных способов

Почему следует стараться использовать хвостовую рекурсию?

(1) она всегда может быть сведена компилятором к итерации

(2) определения с хвостовой рекурсией получаются проще

(3) хвостовая рекурсия – единственный вид рекурсии, поддерживаемый F#

(4) при хвостовой рекурсии выделяемая для параметров память выделяется в регистрах

Какой самый внешний редекс в выражении (λx.λy.y) ((λz.z z) (λz.z z))?

(1) (λz.z z)

(2) (λz.z z) (λz.z z)

(3) (λx.λy.y) ((λz.z z) (λz.z z))

(4) (λx.λy.y)

Как определяется наименьшая неподвижная точка непрерывной функции f в соответствии с теоремой о неподвижной точке?

(1) fix f = =∪_ifⁱ(⊥)

(2) fix f =∪_ifⁱ(Ø)

(3) fix f = З_ifⁱ(⊥)

(4) fix f =З_ifⁱ(Ø)

В каком представлении эффективнее хранить разреженные матрицы?

(1) в виде списка списков

(2) в порядковом представлении

(3) в виде двумерного массива

(4) в виде массива переменной длины

Какой будет следующий шаг при аппликативном порядке редукции выражения (λx.x+x)(2+3)?

(1) (2+3)+(2+3)

(2) (λx.x+x) 5

(3) 10

(4) (λx.(2+3)+x)(2+3)

Возможно ли построить автоматический верификатор произвольных функциональных программ на зацикливаемость?

(1) да, поскольку функциональные программы имеют четкие математические денотаты

(2) да, поскольку чистое лямбда-исчисление является полным

(3) нет, поскольку невозможно учесть побочные эффекты

(4) нет, поскольку проблема самоприменимости неразрешима

Какова сложность добавления элемента в конец списка длины n?

(1) O(1)

(2) O(n)

(3) O(log n)

(4) O(n²)

Что является следствием теоремы стандартизации?

(1) применение нормального порядка редукции позволяет всегда получить нормальную форму

(2) применение аппликативного порядка редукции позволяет всегда получить нормальную форму

Какие комбинаторы образуют наименьший базис?

(1) S, K

(2) I, K, S

(3) Y

(4) Y, I, K, S

Какой будет результат сопоставления let x::y::z = [1;2]?

(1) ошибка

(2) x=1, y=2, z=null

(3) x=1, y=2, z=[]

(4) x=[], y=1, z=2

(5) x=null, y=1,z=2

Как правильно описать двоичное дерево на F#?

(1) type 'T btree = Leaf of 'T | Node of 'T*('T btree list)

(2) type 't btree = Node of 't * 't btree * 't btree | Nil

(3) type 't btree = Node of 't * 't btree * 't btree

(4) type 't btree = Leaf of 't | Node of 't btree

В чем преимущества лямбда-исчисления как модели вычислений?

(1) это формальная аксиоматическая система

(2) оно соответствует тому, как происходят вычисления в компьютере

(3) на базе лямбда-исчисления просто построить язык программирования

(4) в лямбда-исчислении хорошо описывается различная семантика вызовов фунций

Как представляется число n в виде нумерала Черча?

(1) n → λf.λx.fxn

(2) n → λf.λx.fⁿx

(3) как список из n элементов

(4) как список из n+1-го пустого списка

Зачем в F# необходимо статически ассоциировать типы с именами?

(1) компилятору необходимо знать, сколько памяти выделять под объект

(2) это обеспечивает дополнительный контроль программы на этапе компиляции

(3) это обеспечивает дополнительный контроль программы на этапе выполнения

(4) это позволяет правильно форматировать строковое представление объекта при печати и преобразовании в строку (ToString())

Какой тип имеет функция apply в Eval/Apply-интерпретаторе?

(1) apply: env→expr→expr→expr

(2) apply: expr→expr

(3) apply: env→expr→ env→expr→expr

(4) apply: expr→expr→expr

В чем разница между записями <@ fun x→ x*2 @> и fun x→ <@ x*2 @>?

(1) первая запись допустима, вторая – нет

(2) вторая запись допустима, первая – нет

(3) нет разницы

(4) в первом случае создается дерево лямбда-выражения, во втором – функция, которая по заданному x возвращает дерево умножения его на 2

Как реализуются повторяющиеся действия в функциональных языках?

(1) с помощью рекурсии

(2) с помощью конструкций циклов

(3) с помощью оператора перехода

(4) с помощью функциональной абстракции

Как определяется функция в λ-исчислении?

(1) как множество пар <аргумент, значение>

(2) как строка, представляющая собой совокупность абстракций и аппликаций

(3) как алгоритм вычисления функции по заданному входному значению

Какая функция может быть использована для удаления из списка всех элементов, делящихся на 3?

(1) fold

(2) filter

(3) map

(4) ни одна из перечисленных

В каком порядка обходятся поддеревья в постфиксном порядке обхода?

(1) корень, левое поддерево, правое поддерево

(2) левое поддерево, корень, правое поддерево

(3) левое поддерево, правое поддерево, корень

(4) корень, правое поддерево, левое поддерево

Какая операция понижает порядок функции?

(1) аппликация

(2) абстрация

(3) композиция

(4) унификация

Как определяется множество значений для типа, описанного как type tree = {nil} + int X treeX tree?

(1) как решение доменного уравнения D = { nil } + int XDXD

(2) как неподвижная точка функции it.nil+x*t*t

(3) как множество троек <i,l,r>, i∈Int, l,r∈ tree

Что помещается в стек объектов S SECD-машины?

(1) выражения-операнды (в том числе замыкания) для выполнения операции аппликации

(2) примитивные операнды (базовых типов) для вычисления функций

(3) частично-вычисленные функции

(4) результаты уже вычисленных выражений для эффективной реализации отложенных вычислений

Укажите правильное монадическое свойство:

(1) m >>= return m є m

(2) f >>= return m є f m

(3) f >>= return m є m f

(4) m >>= return є m

Какие языки программирования являются преимущественно функциональными?

(1) C++

(2) Java

(3) C#

(4) Haskell

(5) F#

(6) FORTH

(7) OCaml

(8) Objective C

Пусть mul3 – каррированная функция умножения трех целых чисел, mul3 = xyz.x*y*z. Какой будет тип у выражения (mul3 5)?

(1) int

(2) int -> int

(3) int -> int -> int

(4) (int x int) -> int

Какой тип имеет функция fold_left?

(1) (‘a → ‘a → ‘a) → ‘a → ‘a list → ‘a

(2) (‘b → ‘a → ‘b) → b’ → ‘a list → ‘b

(3) (‘a → ‘a) → ‘a → ‘a list → ‘a

(4) ‘a → ‘a → ‘a → ‘a list

Как обычно представляется дерево арифметического выражения?

(1) деревом общего вида, в котором число поддеревьев соответствует количеству аргументов операции

(2) деревом общего вида, в котором число поддеревьев соответствует количеству аргументов для последовательной цепочки одинаковых операций

(3) двоичным деревом

Как правильно расставить скобки в выражении лямбда-исчисления, чтобы вычислить f(g(x))?

(1) f g x

(2) f(g(x))

(3) f (g x)

(4) (f g) x

Можно ли в F# изменять контекст вычисления функции внутри замыкания?

(1) нет

(2) да, если внутри создаются локальные переменные, описанные как mutable

(3) да, если внутри создаются ссылочные объекты ref

(4) да, если при компиляции включена опция позднего связывания

Алгоритм вывода типов W содержит в себе следующие основные этапы:

(1) генерация множества исходных уравнений, унификация для поиска решения

(2) генерация множества исходных уравнений, перебор всех возможных подстановок

(3) унификация типов имен и функций, генерация решения

(4) унификация наиболее общих типов, генерация подстановок

Почему контестно-свободная грамматика удобна для разбора методом рекурсивного спуска?

(1) на каждом шаге по начальным токенам можно однозначно понять, какое правило грамматики применять, что позволяет избежать возвратов и перебора

(2) нет необходимости передавать текущий контекст при рекурсивном вызове

(3) нет необходимости возвращать еще не обработанный хвост последовательности токенов

Как записать выражение для последующего параллельного вычисления значения функции fib?

(1) async { fib 100; }

(2) async { return (fib 100); }

(3) return async { fib 100 }

(4) async(fib 100)

В чем отличия фунционального программирования и императивного?

(1) функциональное программирование оперирует функциями и их применением к данным, императивное – операторами и тем, как они изменяют состояние памяти

(2) в фунциональном программировании каждая функция может оперировать только с той областью памяти, которая для нее выделена

(3) в функциональном программировании происходит автоматический поиск решения задачи по ее декларативному описанию

(4) все вышеперечисленное

Где может использоваться сопоставление с образцом в F#?

(1) в конструкциях function, match, let

(2) для этого предназначена специальная конструкция match

(3) в конструкции связывания let

(4) в конструкциях let и match

Какими способами можно создать список четных чисел от 1 до 10?

(1) [2..2..10]

(2) [ for x in 1..10 when x%2=0 → x ]

(3) [ for x in 1..10 step 2 do x ]

(4) [ 2..10 step 2]

Какие из преобразований надо применить, чтобы редуцировать (λx.sin x) 0 → 0?

(1) альфа-редукцию и бета-редукцию

(2) альфа-редукцию

(3) бета-редукцию

(4) бета-редукцию и дельта-редукцию

Что такое мемоизация?

(1) запоминание значений контекста вычислений при формировании замыкания

(2) использование заранее вычисленной таблицы значений функции для ускорения вычислений

(3) запоминание результатов вычисления функции при ленивых вычислениях

(4) запоминание результатов вычисления функции как при ленивых, так и при энергичных вычислениях

Что такое пропозициональная семантика языка программирования?

(3) описание того, как некоторые свойства меняются в процессе применения конструкций языка

Какие ошибки содержаться в приведенном фрагменте кода? 1 let ProcessImageAsync () = 2 async { let inStream = File.OpenRead(sprintf "Image%d.tmp" i) 3 let pixels = inStream.ReadAsync(numPixels) 4 let pixels' = TransformImage(pixels,i) 5 let outStream = File.OpenWrite(sprintf "Image%d.done" i) 6 do outStream.WriteAsync(pixels') }

(1) в строке 2 отсутствует восклицательный знак после let

(2) в строке 3 отсутствует восклицательный знак после let

(3) в строке 4 отсутствует восклицательный знак после let

(4) в строке 5 отсутствует восклицательный знак после let

(5) в строке 6 отсутствует восклицательный знак после do

Почему функциональные программы не содержат побочных эффектов?

(1) отсутствует понятие переменной и оператора присваивания

(2) функция может оперировать только над переменными, описанными внутри нее

(3) запрещено модифицировать внутренние переменные функции извне самой функции

(4) отсутствует понятие области видимости

Какая рекурсия называется линейной?

(1) при вызове функции осуществляется не более одного рекурсивного вызова

(2) в теле функции присутствует только один рекурсивный вызов

(3) рекурсивный вызов – это последнее действие в теле функции

(4) это разновидность рекурсии с одним параметром – номером шага

При вычислении длины списка n с помощью хвостовой рекурсии, сколько памяти выделяется в стеке?

(1) O(1)

(2) O(n)

(3) O(log n)

(4) O(n2)

Какая функция, определенная на домене D, обязательно имеет неподвижную точку?

(1) непрерывная

(2) монотонная

(3) произвольная

(4) целочисленная

Разреженная матрица размерности nXn с m ненулевыми элементами представляется в виде функции int*int → float. Какова будет сложность операции умножения всех элементов матрицы на 2?

(1) O(1)

(2) O(n)

(3) O(m)

(4) O(nXm)

При нормальном порядке редукции:

(1) редуцируется самый левый из самых внешних редексов

(2) редуцируется самый правый из самых внешних редексов

(3) редуцируется самый левый из самых внутренних редексов

(4) редуцируется самый правый из самых внутренних редексов

Почему проще формулировать и доказывать корректность программ на чистом функциональном языке?

(1) потому что отсутствие циклов снимает проблему остановки

(2) потому что чистое лямбда-исчисление является полным

(3) из-за отсутствия побочных эффектов

(4) потому что можно поставить в однозначное соответствие функциям программы некоторые математические функции

Какова сложность проверки вхождения элемента в список длины n?

(1) O(1)

(2) O(n)

(3) O(log n)

(4) O(n²)

Какой порядок редукции соответствует передаче параметров по значению?

(1) аппликативный

(2) нормальный

(3) нормальный с мемоизацией

(4) передача параметров не связана с порядком редукции

Какое максимальное количество неподвижных точек может иметь функция?

(1) одну, которая возвращается оператором Y

(2) бесконечное множество – Y возвращает наименьшую неподвижную точку

(3) бесконечное множество – Y возвращает наибольную неподвижную точку

Какая операция применяет функцию к аргументу?

(1) аппликация

(2) абстракция

(3) композиция

(4) унификация

При аппликативном порядке редукции:

(1) редуцируется самый левый из самых внешних редексов

(2) редуцируется самый правый из самых внешних редексов

(3) редуцируется самый левый из самых внутренних редексов

(4) редуцируется самый правый из самых внутренних редексов

Какому способу передачи параметров соответствует аппликативный порядок редукции?

(1) по имени

(2) по ссылке

(3) по значению

(4) по адресу

Система вывода типов (Хиндли-Милнера) – это:

(1) множество типовых уравнений типов для стандартных функций (map, fold, …)

(2) формальная аксиоматическая система для вывода типовых заключений

(3) система уравнений для типов базовых конструкций языка (let, if-then-else и др.)

Как определяется семантика рекурсивных функций?

(1) сведением к циклу

(2) как неподвижная точка некоторой порождающей функции

(3) как и любого другого лямбда-выражения

Для реализации ленивого Eval/Apply-интерпретатора необходимо, в частности:

(1) добавить дополнительную функцию susp: expr→env→expr для отложенного вычисления

(2) ввести в дерево выражения конструкцию susp(expr,env), похожую на конструкцию замыкания

(3) изменить функцию Apply, чтобы она вместо результата возвращала функцию для отложенного вычисления результата

В чем разница между записями <@ fun x→ x*2 @> и <@@ fun x→x*2 @@>?

(1) нет разницы

(2) в первом случае производится контроль типов и возвращается типизированное дерево, во втором – безтиповое

(3) в первом случае используются энергичные вычисления, во втором – ленивые

(4) в данном случае допустима только первая запись