Open the-homeless-god opened 3 months ago
1.
Детерминированная конечная машина - машина, в которой для каждого состояния и каждого символа входного алфавита есть точно одно следующее состояние. Значит, при получении определенного символа, происходит переход в одно и то же следующее состояние. Недетерминированная конечная машина - машина, в которой для каждого состояния и каждого символа входного алфавита может быть несколько следующих состояний. Значит, при получении определенного символа может произойти переход в несколько следующих состояний.
Лямбда-исчисление - это математическая система, которая позволяет оперировать функциями, не привязывать их к конкретным именам, а использовать анонимные выражения.
Идеи Черча и Тьюринга для лямбда-выражений имеют различия в основном в подходе к представлению и применению функций. Черч предлагает представлять функции с помощью лямбда-выражений и применять их путем подстановки значений аргументов в выражения. Тьюринг, с другой стороны, предлагает представлять функции как последовательности инструкций и применять их путем выполнения этих инструкций.
AST - дерево показывающее всевозможные наборы соединения частей алфавита воедино
Пример: имеем алфавит буа
все 3 буквенные слова начиная с буквы б
Число – одно из понятий в математике, которое используется для счёта, измерения, сравнения, выполнения каких-либо математических операций. Числа могут быть натуральными, дробными, положительными, отрицательными и т.д. А ещё числа состоят из цифр)
1.Детерменированный автомат. Он пребывает только в одном состоянии в определенный период времени и никак иначе.
Недетерменированный автомат. Он может пребывать в нескольких состояниях сразу в определенный момент времени.
2.Лямбда исчисление – это своего рода «анонимная» функция. А анонимная она потому что у нее нет имени, арифметических операций, циклов, констант, онли фукнции.
Детерминированная
Недетерминированная
Draw an example for determined and non-determined finite machine (paste a picture with explanation)
На первом рисунке показано, что из вершины S0 существует только один переход с 1, может существовать другой переход, к этой же вершине (или другой), но не с 1.
А на втором рисунке показано, противоположное, что из вершины S0 по переходу с 1 можно попасть в разные состояния ( S1, S0 ). Это обосновано тем, что в детерминированном автомате: следующее состояние однозначно определяется, текущим его состоянием и входным символом. А Недетерминированные автомат может переходить в разные состояния вод воздействием одного и того же входного символа.
What's Lambda Calculus? Лямбда-исчисление - это некая система, которая может быть использована для представления различных вычислений и/или операций.
What's difference between Church & Turing ideas for lambdas?
What's AST (abstract syntax tree)? Provide the real life example AST дерево - это некая структуризация информации в виде дерева, в котором узлами представлены операции или элементы, а связь между ними определяет их иерархию. В качестве жизненного примера AST дерева могу привести, любую инструкцию, ее можно представить в виде AST дерева, где каждый узел будет представлять отдельный шаг в процессе сборки.
What's a number? Число - это математическая абстракция, которая представляет собой концепцию количества или величины.
1) Детерменированная конечная машина - это машина в которой каждое последующее состояние имеет только одну вариацию, что обеспечивает полную предсказуемость.
Недетерминированная конечная машина - это машина это машина в которой каждое последующее состояние имеет несколько вариаций.
2) В лямбда-исчислении нет чисел, строк или любых других типов данных, с которыми мы привыкли работать в программировании. Вместо этого есть только функции.
3) Если учитывать тот факт что они взаимозаменяемы, то отличаться они будут только по структуре. Машину Тьюринга можно представить в виде неограниченного кортежа из ячеек, в то время как лямбда исчисление(Church) представляет собой выражение.
4) Абстрактное синтаксическое дерево это способ представления программного кода в виде древа, где операции над элементами стоят в узлах. Пример из жизни: строительство дома, где мы к каждому кирпичу прибавляем еще один кирпич.
5) Номер это способ что-то идентифицировать, классифицировать или описать количество.
Нарисуйте пример для детерминированной и недетерминированной конечной машины (вставьте картинку с пояснением)
Детерминированный автомат может находиться только в одном состоянии в данный момент времени.
Недетерминированный автомат может находиться только в нескольких состояниях сразу.
Что такое лямбда-исчисление? Лямбда-исчисление – это формальная система, придуманная американским математиком и логиком Алонзо Черчем в 1930-х годах для определения любой языковой конструкции или алгоритма.
В чем разница между идеями Черча и Тьюринга для лямбд? Идеи Черча и Тьюринга для лямбд различаются в подходах к формализации вычисления функций. Черч вычислял функции с помощью лямбда-исчислений. Тьюринг использовал свою машину для вычисления функций в виде последовательности переходов состояний алгоритма.
Что такое AST (абстрактное синтаксическое дерево)? Приведите пример из реальной жизни AST (Абстрактное синтаксическое дерево) – структура данных, представляющая собой в виде дерева и работающая как один из промежуточных слоев при преобразовании языков высокого уровня. В качества примера из жизни была взята сборка модели из конструктора лего, где, следуя по инструкции пошагово, к каждой детали прикрепляется еще одна деталь.
Что такое число? Число – это одно из основных понятий математики, отображающее количество или порядок по счету.
Детерминированная конечная машина может пребывать только в одном состоянии в конкретный момент времени. Также для определенного входного символа есть только одно следующее состояние.
Недетерминированная конечная машина может пребывать нескольких состояниях одновременно. Также для определенного входного символа есть несколько следующих состояний.
Лямбда исчисление - анонимная (потому что нет имени) функция, в которой есть аргумент и некоторые параметры. Например: (λx.x^2)3 После вычислений получится 9
AST - абстрактное древовидное представление программного кода.
Пример:
Приготовление пиццы:
x^2+4x-6
Число – количественная характеристика для сравнения, измерения, счета, нумерации, вычислений. Для записи чисел используются цифры. Числа есть натуральные, целые, рациональные, действительные (вещественные), комплексные. Если нужно что-то философское: числа являются важным компонентом в «построении» мира (хоть и достаточно абстрактным, ведь кто-то в любой момент может сказать и доказать, что 1 метр равен не 100 см, а 10, и тогда все наше привычное устройство мира переменится). Без чисел мы бы не смогли ориентироваться во времени, часовых поясах, измерять что-либо (линейка, рулетка), строить здания, пользоваться деньгами. С помощью чисел мы можем интерпретировать мир. Поэтому числа являются одним из ключей к пониманию мира.
Недетерминированный конечный автомат тоже является математической моделью, пути которой не однозначны, то есть есть недетерминируемые участки и состояния, находясь в которых мы не можешь определить какие состояни были до. Соответственно характерными чертами являются развилки, когда из одного и того же состояния в два другхи разных ведут рёбра при одних и тех же значениях. Простыми словами у нас появляются варианты переходов, когда при одних и тех же входных данных происходят разные операции (проходятся разные пути).
Я не знал точного определения и не использовал данное понятие, но почитав в интернете понял следующее. Лямбда-исчисление - это использованиея более простых атомарных функций для создания более сложных функций и асбтракций. Например возведение в квадрат как отдельную операцию можно представить как умножение числа и применение этой функции (умножение числа) для аргумента x следующим образом -> x (умножение числа) x.
Без понятия.
Я не знал точного определения и не использовал данное понятие, но почитав в интернете понял следующее. AST - это дерево, которое отображает структуру функции, то есть операторы, операнды и их отношение. ChatGPT привёл такой классный пример, который был для меня понятен (если он ещё и верный, то вообще супер), поэтому приведу его здесь: У нас есть функция x (y + z), передаём параметры 2, 3, 4, соответственно получаем 2 (3+4), в AST представляем вот так:
*
/ \
2 +
/ \
3 4
Условное обозначение количественной меры. В компьютере это набор нулей и едениц или интерпретируемый результат воздействия функции тока на функцию проводимости транзисторов. Есть ток - 1, нет тока - 0. Соответственно все числовые значения согласно двоичной системе счисления представляют собой комбинации символов двоичного алфавита, то есть 0 и 1.
1.
У нас есть алфавит (конечное множество неделимых символов формального языка) состоящий из 2 символов:
Также, есть три состояния ("ГОЛОДЕН", "ПЕЧАЛЕН", "СЧАСТЛИВ")
У детерминированного конечного автомата переход в каждое из состояний однозначно определен входящим символом.
У недетерминированного конечного автомата переход из состояния "голоден" уже не может быть известен, поскольку символ "СЪЕЛ БУРБУРОД С СЫРЫМ" приводит систему не в определенное состояние, а в одно из возможных.
2.
Лямбда-исчисление - это система Черча, рожденная при решении вопроса о существовании алгоритма, за конечное число шагов определяющего истинность или ложность утверждения, записанного на неком формальном языке.
Термы -выражения, вычисление которых даёт значение, которое есть всё тот же терм.
У нас есть алфавит, символы которого что-то значат - это основа, это, так сказать, база, на чем строятся последующие вычисления. Символы алфавита - термы. К символам алфавита мы можем применять функции одного аргумента (эти функции тоже являются термами). Возвращаемое функциями значение - некий терм, что значит, что функция может вернуть как значение, так и функцию, которую можно применить к другому терму.
Функции задаются записью (λx.M), где x - переменная, M - некая функция. Применение функции - (MN), где M- функция, а N - аргумент.
Задаем числа (некоторые скобочки опустил):
s - имя функции инкрементирования (+1)
z - имя функции, которая представляет 0
0 = λs.λz.z - тут мы определяем, что s это 0, который функция (+1) 1 = λs.λz.sz - здесь у нас s уже применяется к z, из-за чего мы получаем функцию +1, в которой уже есть 1 2 = λs.λz.s(sz) 3 = λs.λz.s(s(sz))
Получается, чтобы получить 50 надо сделать следующую функцию:
50 = λnλs.λz.s(nsz), где n - функция λs, применённая к функции λz, представляющей собой начальное значение, n раз.
Задание tru и folse:
tru = λa.λb.a false = λa.λb.b
Задание if:
if=λp.λt.λe.(pt)e
p - функция предиката (условия) t - функция, выполняемая если условие истинно e - функция, выполняемая если условие ложно
У нас выходит:
за t возьмём 1, а за e возьмём 0, тогда
((if tru) 1 0) = ((λt.λe.tru t e 1) 0) = (λe.tru 1 e 0) = (tru 1 0) = (λb.1 0) <- тут получается, что наш tru - это λa.λb.a, где в роли a выступила 1, а значит, что в b пойдёт 0, то есть будет функция вида (1 0), возвращающая 1
3.
У Тьюринга машина идет по алфавиту, меняя своё состояние (ленту) в зависимости от пришедшего символа, в то время как у Черча происходит работа с функциями, вычисление которых происходит рекурсивно.
Вообще, как я понял, лямбды сводятся к машине Тьюринга, как и наоборот.
4.
AST - структура данных, используемая синтаксическим анализатором для представления отношения операторов и операндов согласно грамматике языка. В реальной жизни это может быть сигнал светофора - оператор (сигнал) определяет отношение операндов (меня и автомобиля) на основе грамматики языка (правила ПДД). То есть простой человекочитаемый знак в нашем мозге обретает некое представление.
Слева машина детерминирована, ибо заранее определено из какого состояние в какое машина может перейти и при каких условиях.
Справа недетерминорована, потому что может перейти из состояния 1 как в состояние 2, так и в состояние 3 при одних и тех же условиях. Переход будет осуществляться случайно, то есть неопределённо.
Лямбда исчисление - система записи функций. В ней есть лишь абстракции самой функции и её применение к какому-то параметру. В качестве параметра можно передавать другие функции.
Не знаю.
Abstract syntax tree — представление сложной системы путём её разбиения на более простые элементы и выстраивание из этого дерева.
Например, любое предложение. "Я налил в чашку чай".
У нас есть сложная система (предложение), мы её разбиваем на менее сложные системы (словосочетания), которые в свою очередь разбиваем на совсем простые элементы (слова). И из этого выстраиваем дерево.
Число — удобная для восприятия запись каких-либо значений. Является состоянием функции в какой-то конкретный момент.
1.
Нарисуйте пример для детерминированной и недетерминированной конечной машины (вставьте картинку с пояснением). Детерминированный конечный автомат - модель, где для каждой пары состояние-входной символ существует однозначный переход в следующее состояние. Недетерминированный конечный автомат - это модель, где для одной пары состояние-входной символ может существовать несколько возможных переходов в различные состояния.
Что такое лямбда-исчисление? Как я поняла лямбда-исчисление - это абстрактное задание переменных и с анонимной функцией, которая являются универсальной моделью вычислений. Используется для машины Тьюринга.
В чем разница между идеями Черча и Тьюринга для лямбд? Лямбда-исчисление (идеи Черча) ориентировано на функциональное программирование и формальность математических функций с помощью абстрактных выражения. Модель Тьюринга (идеи Тьюринга) ориентирована на процессах универсального вычислительного устройства.
Что такое AST (абстрактное синтаксическое дерево)? Приведите пример из реальной жизни AST - структура данных, представляющая исходный код программы в виде дерева. Как пример: распределение студентов по группам/направлениям/ преподавателям и тд, составление расписания. Вообщем не знаю нормального примера.
Что такое число? Число - данные использумве для измерения и подсчета количества, порядка или качества.
1.Детерминированный конечный автомат может переходить только в одно состояние.
Недетерминированный конечный автомат может переходить из одного состояния в разные.
1.
Детерминированный конечный автомат - ДКА
Начальное состояние 0, конечное 2. ДКА принимает цепочку символов, если их последовательность будет "a", "b"
Недетерминированный конечный автоман - НКА.
Стартовое состояние 0 при входном сивволе "а", есть возможность перейти в состояние 1, из состояния 1 есть возможность перейти в состояния 1 и 2 при входном "b", т.е после входного "b" текущим состоянием будет множество {1,2}
Лямба-исчисление разработал Алонзо Чёрч, оно из себя представляло минималистичную формальную систему для записи математических функций. В лямбда-исчислении существует две операции: абстракция и аппликация. Абстракция (лямбда) – это объявление функции Аппликация – это применение функции к некоторым параметрам, например на JS: Абстракция: y = (x) => x + 1 Аппликация: z = y(1) – применение абстракции к числу 1 Алонзо Чёрч обнаружил, что с помощью абстракций и аппликаций возможно создать программу любой сложности, например, рассмотрим начало логики: true = (x, y) => x false = (x, y) => y Также с помощью этого, можно представить базовые логические операции and, or, not, if, целые числа, арифметические операции.
Тьюринг использовал термин «чисто механический», Чёрч использовал термин «эффективно вычислимый», чтобы указать, что существует эффективный метод получения значений функции. Тьюринг предложил анализ с точки зрения вычислимости с помощью логических вычислительных машин, Черч дал два альтернативных анализа: один с точки зрения концепции рекурсии, а другой с точки зрения лямбда-определимости (λ-определимости). Он предложил: Эффективно вычислимая функция натуральных чисел, отождествляется его с понятием рекурсивной функции натуральных чисел (или λ-определимой функции натуральных чисел). Функция называется λ-определимой, если значения функции можно получить определенным процессом повторной подстановки. Класс λ-определимых функций (целых положительных чисел) и класс рекурсивных функций (целых положительных чисел) идентичны. Тьюринг установил, что концепция λ-определимости и его концепция вычислимости эквивалентны. Тезис Чёрча. Функция натуральных чисел эффективно вычислима только в том случае, если λ-определима (рекурсивна). Если внимание ограничено функциями натуральных чисел, тезис Чёрча и тезис Тьюринга расширенно эквивалентны. «Расширенно эквивалентный» означает, что эти два тезиса относятся к одному и тому же классу функций. Класс λ-определимых функций (натуральных целых чисел) идентичен классу рекурсивных функций (целых положительных чисел) и к классу вычислимых функций (целых положительных чисел). Однако, эти два тезиса эквивалентны в этом смысле, но имеют разные значения, следовательно, являются двумя разными тезисами. Одно из важных различий между ними заключается в том, что тезис Тьюринга касается вычислительных машин, а тезис Чёрча - нет.
1.Draw an example for determined and non-determined finite machine (paste a picture with explanation)
Детерминированный конечный автомат - в нём для всех состояний имеется только один переход для любого возможного входного символа
Недетерминированный конечный автомат - в нём может быть ноль и более переходов для одного символа в каких-либо состояниях.
2.What's Lambda Calculus? Лямбда-исчисление - это система записи коротких и анонимных функций для различных вычислений. Была выведена и разработана Алонзо Чёрчем.
3.What's difference between Church & Turing ideas for lambdas? Чёрч был сосредоточен на функциях , а Тьюринг на вычислимости для своей машины Тьюринга.
4.What's AST (abstract syntax tree)? Provide the real life example Абстрактное синтаксическое дерево - представляет собой разбиение сложных систем, компонентов или каких-нибудь уравнений на более простые части, а их ещё на боле простые и т.д. (похоже на 4 задание из ЕГЭ по информатике)
5.What's a number? Числа состоят из цифр (от 0 до 9). Они нужны нам для подсчёта или вычисления чего-либо в математике или где-нибудь ещё. Числа так же делятся на виды: натуральные, целые, рациональные, иррациональные и т.д.
1.
Детерминированная конечная машина
Прибывает только в одном состоянии в один момент времени
Конечная определенная машина (Deterministic Finite Automaton, DFA) - это модель вычислений, которая может находиться в одном из конечного числа состояний и переходить между ними в зависимости от входных символов. Ниже приведен пример DFA для распознавания строки "ab"
Лямбда-исчисление - это формальная система, разработанная Алонзо Чёрчем в 1930-х годах, которая используется для изучения функций и их вычислимости. Оно представляет собой простой математический язык, в котором функции представляются анонимными функциями без имени.
Основное различие между идеями церкви и Тьюринга для лямбд заключается в том, что Чёрч использовал лямбда-исчисление для формализации понятия функции, в то время как Тьюринг использовал машины Тьюринга для формализации понятия алгоритма.
Абстрактное синтаксическое дерево (Abstract Syntax Tree, AST) - это структура данных, которая представляет собой иерархическое дерево, описывающее синтаксическую структуру программы. Примером AST может служить дерево разбора арифметического выражения, где операторы и операнды представлены узлами дерева.
Число - это абстрактное понятие, используемое для количественного измерения или подсчета объектов или явлений. В математике числа могут быть натуральными, целыми, рациональными, действительными или комплексными, и они играют важную роль в различных областях науки и повседневной жизни.
У недетерминированного конечного автомата при получении одного и того же входного значения возможны различные переходы
Лямбда-исчисление – это математическая система, которая представляет функции в виде объектов для вычислений.
Машина Тьюринга конкретнее лямбда-исчисления, и используется для изучения алгоритмов. Лямбда-исчисление – более абстрактно, и применяется в логике и функциональном программировании.
Абстрактное синтаксическое дерево (AST) – это дерево, в котором каждый узел представляет собой определенную часть алгоритма, а связи между узлами обозначают отношения между ними. Примером может быть вязание. Когда на каждой строчке основывается следующая.
Число – это абстрактное понятие, используемое для определения количества чего-то. Состоит из цифр.
if x > 5: y = x * 2 else: y = x + 2
Лямбда-исчисление - это формальная система, разработанная Алонзо Чёрчем в 1930-х годах, которая используется для изучения функций и их вычислимости. Оно представляет собой простой математический язык, в котором функции представляются анонимными функциями без имени.
Алгоритмы и вычисления получили формальное представление благодаря:
Число – это абстрактное понятие, используемое для определения количества чего-то. Состоит из цифр.
1) Draw an example for determined and non-determined finite machine (paste a picture with explanation) Детерминированный конечный автомат:
Недетерминированный конечный автомат:
2) What's Lambda Calculus? Лямбда-исчисление – формальная система, которая позволяет за конечное количество шагов определить истинность или ложность утверждения. 3) What's difference between Church & Turing ideas for lambdas? Лямбда-исчисления Черча были ориентированы на функции, Тьюринга – на последовательность, перебор. Он разрабатывал свою машину - абстрактную модель для описания алгоритмов и процессов вычислений, его идеи ориентированы на универсальное вычислительное устройство. 4) What's AST (abstract syntax tree)? Provide the real life example Абстрактная структура данных – структура данных, представленная в виде дерева, позволяющая представить какой-либо сложный процесс/функцию в виде иерархической структуры более простых компонент. Пример – процесс приготовления любого блюда. Чтобы испечь пирог, нужно поставить его в духовку, для этого нужно соединить тесто с начинкой, для этого приготовить тесто и начинку, чтобы приготовить тесто, нужно замесить его и дать ему “отдохнуть”, чтобы замесить тесто, нужно добавить яйца, муку, дрожжи и т.д. 5) What's a number? В парадигме фп абстракция, используемая для обозначения количества или величины.
Draw an example for determined and non-determined finite machine (paste a picture with explanation) Детерминированные - в один момент времени одно состояние
6bbd28a1"> Недетерминированные - в один момент времени несколько состояний.
What's Lambda Calculus? Абстрактная функции (т.е. без имени) для вычисления
What's difference between Church & Turing ideas for lambdas? Честно говоря, не знаю
What's AST (abstract syntax tree)? Provide the real life example Разбиение сложных задач (функций) на более простые. Например, сдача экзамена - подготовка к экзамену - получение допуска - работа в семестре
What's a number? Цифра - абстракция, используемая для записи чисел.