Главная /
Функциональное программирование
Функциональное программирование - ответы на тесты Интуит
Курс знакомит слушателей с парадигмой функционального программирования, в которой решение задач сводится к описанию функций, перерабатывающих некоторые входные данные в выходные и строящихся из более простых функций на основе принципов функциональной абстракции и аппликации. Рассматриваются теоретические основы функционального программирования (лямбда-исчисление, комбинаторная логика, вопросы вычислимости), на примере функционального подхода дается представление о некоторых теоретических разделах компьютерных наук (семантика языков программирования, доказательство программ). С другой стороны курс содержит значительную практическую составляющую, основанную на промышленном языке программирования F# (входит в состав Microsoft Visual Studio 2010), рассматриваются вопросы использования функциональных языков для построения компиляторов, грамматического разбора и т.д.
Список вопросов:
- # Как можно отделить голову и хвост списка?
- # Какой будет результат выполнения let x::y = [1;2;3;4] ?
- # Какой будет результат сопоставления let x::y::z = [1;2]?
- # C помощью какой функции можно эффективно посчитать сумму элементов целочисленного списка?
- # С помощью какой функции можно удалить из списка все элементы, стоящие на четных позициях?
- # Какая функция может быть использована для удаления из списка всех элементов, делящихся на 3?
- # Какой тип имеет функция map?
- # Какой тип имеет функция filter?
- # Какой тип имеет функция fold_left?
- # Какой функции эквивалентна запись [ for x in L → x*2 ]?
- # Какой список будет порожден конструкцией [1..2..10]?
- # Какими способами можно создать список четных чисел от 1 до 10?
- # Какие условия являются необходимыми для хвостовой рекурсии?
- # Почему следует стараться использовать хвостовую рекурсию?
- # При вычислении длины списка n с помощью хвостовой рекурсии, сколько памяти выделяется в стеке?
- # В каком представлении матриц проще реализовать операцию транспонирования?
- # В каком представлении эффективнее хранить разреженные матрицы?
- # Разреженная матрица размерности nXn с m ненулевыми элементами представляется в виде функции int*int → float. Какова будет сложность операции умножения всех элементов матрицы на 2?
- # Какова сложность добавления элемента на первое место списка длины n?
- # Какова сложность добавления элемента в конец списка длины n?
- # Какова сложность проверки вхождения элемента в список длины n?
- # Как связаны двоичные деревья и деревья общего вида?
- # Как правильно описать дерево общего вида на F#?
- # Как правильно описать двоичное дерево на F#?
- # В каком порядка обходятся поддеревья в инфиксном порядке обхода?
- # В каком порядка обходятся поддеревья в префиксном порядке обхода?
- # В каком порядка обходятся поддеревья в постфиксном порядке обхода?
- # Что такое дерево поиска?
- # Какова сложность поиска в дереве поиска?
- # Как обычно представляется дерево арифметического выражения?
- # Что такое продолжение (continuation)?
- # Как можно свести нелинейно-рекурсивную функцию к хвостовой рекурсии?
- # Какие есть основные модели вычислений?
- # Какая модель вычислений служит формальной основой функционального программирования?
- # В чем преимущества лямбда-исчисления как модели вычислений?
- # Какие базовые операции чистого лямбда-исчисления?
- # Какая операция повышает порядок функции?
- # Какая операция понижает порядок функции?
- # Какая операция применяет функцию к аргументу?
- # Как расставляются скобки в выражении λx.λy.e1e2?
- # Как расставляются скобки в выражении f sin x*2?
- # Как правильно расставить скобки в выражении лямбда-исчисления, чтобы вычислить f(g(x))?
- # Какое из приведенных ниже преобразований является примером бета-редукции?
- # Какое из приведенных ниже преобразований является примером альфа-редукции?
- # Какие из преобразований надо применить, чтобы редуцировать (λx.sin x) 0 → 0?
- # Какой самый внутренний редекс в выражении (λx.λy.y) ((λz.z z) (λz.z z))?
- # Какой самый внешний редекс в выражении (λx.λy.y) ((λz.z z) (λz.z z))?
- # Какой будет следующий шаг при нормальном порядке редукции выражения (λx.x+x)(2+3)?
- # Какой будет следующий шаг при аппликативном порядке редукции выражения (λx.x+x)(2+3)?
- # При нормальном порядке редукции:
- # При аппликативном порядке редукции:
- # Что является следствием теоремы Черча-Россера?
- # Что является следствием теоремы стандартизации?
- # Какой порядок редукции соответствует передаче параметров по значению?
- # Какому способу передачи параметров соответствует аппликативный порядок редукции?
- # Как определяют рекурсивные вычисления в лямбда-исчислении?
- # Какие комбинаторы образуют наименьший базис?
- # Какое максимальное количество неподвижных точек может иметь функция?
- # Как определяются значения логического типа при формальном построении языка функционального программирования?
- # При введении списков, как определяется функция отделения первого элемента hd?
- # Как представляется число n в виде нумерала Черча?
- # Как определяется конструкция let?
- # Как определяется конструкция letrec?
- # Что такое замыкание?
- # Пусть геометрическое преобразование определяется функцией трансляции координат int*int → int*int. Мы хотим определить функцию сдвига translate : int*int, которая возвращался бы замыкание. Как это сделать?
- # Можно ли в F# изменять контекст вычисления функции внутри замыкания?
- # Пусть L – генератор последовательности длины n. Какова сложность операции map f L?
- # Возможно ли в F# использовать ленивые вычисления?
- # Что такое мемоизация?
- # В динамических языках программирования:
- # При статическом контроле типов:
- # Зачем в F# необходимо статически ассоциировать типы с именами?
- # Какое множество значений у прямой суммы T1+T2?
- # Какое множество значений у типа T1 → Т2?
- # Как определяется множество значений для типа, описанного как type tree = {nil} + int X treeX tree?
- # Какой будет наиболее общий тип для функции tl: let tl x::t = t?
- # Что необходимо сделать для вывода типов в некотором выражении?
- # Алгоритм вывода типов W содержит в себе следующие основные этапы:
- # Система вывода типов (Хиндли-Милнера) – это:
- # Что такое операционная семантика языка программирования?
- # Что такое денотационная семантика языка программирования?
- # Что такое пропозициональная семантика языка программирования?
- # Что такое домены?
- # Как определяется наименьшая неподвижная точка непрерывной функции f в соответствии с теоремой о неподвижной точке?
- # Какая функция, определенная на домене D, обязательно имеет неподвижную точку?
- # Как определяется семантика рекурсивных функций?
- # Неразрешимость проблемы остановки означает:
- # Возможно ли построить автоматический верификатор произвольных функциональных программ на зацикливаемость?
- # Почему проще формулировать и доказывать корректность программ на чистом функциональном языке?
- # Eval/Apply-интерпретатор состоит из
- # Какой тип имеет функция eval в Eval/Apply-интерпретаторе?
- # Какой тип имеет функция apply в Eval/Apply-интерпретаторе?
- # Для реализации ленивого Eval/Apply-интерпретатора необходимо, в частности:
- # Какие стеки включает в себя SECD-машина?
- # Что помещается в стек возвратов D SECD-машины?
- # Что помещается в стек объектов S SECD-машины?
- # Программа, порожденная генератором fsyacc:
- # При реализации синтаксического анализатора методом рекурсивного спуска, какой тип удобно использовать для функции parse:
- # Почему контестно-свободная грамматика удобна для разбора методом рекурсивного спуска?
- # Какого типа выражение <@@ (1+2)*3 @@>?
- # Что означает запись <@ fun x→ x*2 @>?
- # В чем разница между записями <@ fun x→ x*2 @> и fun x→ <@ x*2 @>?
- # В чем разница между записями <@ fun x→ x*2 @> и <@@ fun x→x*2 @@>?
- # Что такое монада?
- # Укажите правильное монадическое свойство:
- # Укажите правильное монадическое свойство:
- # Чему равен результат выражения nondet { return 10; } для монады недетерминированных вычислений?
- # Какого типа выражение async { return 10; }?
- # Как записать выражение для последующего параллельного вычисления значения функции fib?
- # Как правильно параллельно вычислить сумму 100-го и 200-го чисел Фибоначчи?
- # Сколько потоков выполнения операционной системы будет порождаться при выполнении операции Async.RunSynchronously(Async.Parallel([ for i in 1..100 → async { return fib(i) }]))?
- # Какие ошибки содержаться в приведенном фрагменте кода? 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') }
- # За счет чего функциональные программы содержат меньше ошибок?
- # Какие операторы традиционно отсутствуют в функциональных языках?
- # Как реализуются повторяющиеся действия в функциональных языках?
- # Какой принцип построения функциональных программ?
- # Какие основные способы борьбы со сложностью используются в функциональных программах?
- # Какие языки программирования являются преимущественно функциональными?
- # Какая алгоритмическая модель лежит в основе функционального программирования?
- # Какая алгоритмическая модель лежит в основе императивного программирования?
- # В чем отличия фунционального программирования и императивного?
- # Почему функциональное программирование сейчас представляет повышенный интерес для изучения?
- # За счет чего функциональные программы обычно содержат меньше ошибок, чем императивные?
- # Почему функциональные программы не содержат побочных эффектов?
- # Какие основные операции в чистом λ-исчислении?
- # Какие недостатки "классической" нотации для определения функции f(x)=2*x+1?
- # Как определяется функция в λ-исчислении?
- # Что такое каррирование?
- # Какой тип у каррированной функции сложения целых чисел?
- # Пусть mul3 – каррированная функция умножения трех целых чисел, mul3 = xyz.x*y*z. Какой будет тип у выражения (mul3 5)?
- # В чем разница между конструкциями fun и function в F#?
- # В чем разница между конструкциями fun и function в F#?
- # Где может использоваться сопоставление с образцом в F#?
- # Как описываются рекурсивные функции в F#?
- # Как описать повторяющиеся действия в функциональном языке?
- # Какая рекурсия называется линейной?