Подготовка к МЛиТА-2016

В качестве подготовки предлагаются задачи экзамена МЛиТА-2013:

Билет 1

1. Дан набор булевых функций {x=>y}.

1.1. Является ли набор полным? Доказать. Если набор не полон, привести пример функции, не выражающейся через функции набора и обосновать.

1.2. Сколько функций от 1 и 2 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

1.3.* Сколько функций от 3 и 4 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

2. Посылки: Все животные смертны. Все люди — животные.
Вывод: Все люди смертны.

2.1. записать условие силлогизма с помощью предикатов и кванторов

2.2. доказать справедливость силлогизма методом резолюций для предикатов

3. Автоматный язык на алфавите (a;b;c} построен на основе детерминированного автомата без символов пустой строки. Как нужно изменить грамматику языка, чтобы в него обязательно входили слова, заканчивающиеся на любое число букв b? К результирующей грамматике требование однозначности не предъявляется.

4. В полном неориентированном графе на n вершинах длины ребер A1A2 и A1A3 равны +3, а остальные +1. Какой результат даст алгоритм Форда-Беллмана, если источником берется вершина A1. Указать пометки всех вершин.

Билет 2

1. Дан набор булевых функций {xy; x|y}.

1.1. Является ли набор полным? Доказать. Если набор не полон, привести пример функции, не выражающейся через функции набора и обосновать.

1.2. Сколько функций от 1 и 2 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

1.3.* Сколько функций от 3 и 4 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

2. Посылки: Все котята игривые. Некоторые домашние животные — котята.
Вывод: Некоторые домашние животные — игривые.

2.1. записать условие силлогизма с помощью предикатов и кванторов

2.2. доказать справедливость силлогизма методом резолюций для предикатов

3. Автоматный язык на алфавите (a;b;c} построен на основе детерминированного автомата без символов пустой строки. Как нужно изменить грамматику языка, чтобы в него не входили слова, состоящие из одной буквы b?

4. В полном неориентированном графе на n вершинах длина ребра A1A2 равна -1, а остальные +1. Какой результат даст алгоритм Форда-Беллмана, если источником берется вершина A1, а правило модификации изменено на D(v):=max{D(v); D(u)+A(u;v)}. Указать пометки всех вершин.

Билет 3

1. Дан набор булевых функций {x+y; xy}.

1.1. Является ли набор полным? Доказать. Если набор не полон, привести пример функции, не выражающейся через функции набора и обосновать.

1.2. Сколько функций от 1 и 2 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

1.3.* Сколько функций от 3 и 4 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

2. Посылки: Ни одна рептилия не имеет меха. Все змеи — рептилии.
Вывод: Ни одна змея не имеет меха.

2.1. записать условие силлогизма с помощью предикатов и кванторов

2.2. доказать справедливость силлогизма методом резолюций для предикатов

3. Автоматный язык на алфавите (a;b;c} построен на основе детерминированного автомата без символов пустой строки. Как нужно изменить грамматику языка, чтобы в него обязательно входили все слова, начинающиеся на букву b? К результирующей грамматике требование однозначности не предъявляется.

4. В полном неориентированном графе на n вершинах длины ребер A1Ak равны k-1 (k=2,..., n), а остальных +1. Указать количество ребер и предпоследнюю вершину в кратчайших путях до всех вершин, полученных с помощью алгоритма Форда-Беллмана.

Билет 4

1. Дан набор булевых функций {x+y; x|y}.

1.1. Является ли набор полным? Доказать. Если набор не полон, привести пример функции, не выражающейся через функции набора и обосновать.

1.2. Сколько функций от 1 и 2 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

1.3.* Сколько функций от 3 и 4 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

2. Посылки: Ни одна домашняя работа не весела. Некоторое чтение — домашняя работа.

Вывод: Некоторое чтение не весело.

2.1. записать условие силлогизма с помощью предикатов и кванторов

2.2. доказать справедливость силлогизма методом резолюций для предикатов

3. Автоматный язык на алфавите (a;b;c} удовлетворяет свойству однозначности ветвления по первому символу. Как нужно изменить грамматику языка, чтобы в него не входили слова, содержащие слово ab?

4. В полном неориентированном графе на n вершинах длина ребра A1A2 равна -2, а остальные +1. Какой результат даст алгоритм Форда-Беллмана, если источником берется вершина A1. Указать пометки всех вершин.

Билет 5

1. Дан набор булевых функций {xy; x=>y}.

1.1. Является ли набор полным? Доказать. Если набор не полон, привести пример функции, не выражающейся через функции набора и обосновать.

1.2. Сколько функций от 1 и 2 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

1.3.* Сколько функций от 3 и 4 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

2. Посылки:Ни одна здоровая еда не полнит. Все торты полнят.

Вывод: Ни один торт не здоровая еда.

2.1. записать условие силлогизма с помощью предикатов и кванторов

2.2. доказать справедливость силлогизма методом резолюций для предикатов

3. Автоматный язык на алфавите (a;b;c} построен на основе детерминированного автомата без символов пустой строки. Как нужно изменить грамматику языка, чтобы в него не входили слова, у которых вторая буква b?

4. В полном неориентированном графе на n вершинах длина ребра A1A2 равна -2, а остальные +1. Какой результат даст алгоритм Форда-Беллмана, если источником берется вершина A1, а правило модификации изменено на D(v):=max{D(v); D(u)+A(u;v)}. Указать пометки всех вершин.

Билет 6

1. Дан набор булевых функций {x+y; x=>y}.

1.1. Является ли набор полным? Доказать. Если набор не полон, привести пример функции, не выражающейся через функции набора и обосновать.

1.2. Сколько функций от 1 и 2 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

1.3.* Сколько функций от 3 и 4 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

2. Посылки: Все лошади имеют вздутие живота. Ни один человек не имеет вздутия живота.

Вывод: Ни один человек не лошадь.

2.1. записать условие силлогизма с помощью предикатов и кванторов

2.2. доказать справедливость силлогизма методом резолюций для предикатов

3. Автоматный язык на алфавите (a;b;c} построен на основе детерминированного автомата без символов пустой строки. Как нужно изменить грамматику языка, чтобы в него не входили слова, начинающиеся на ab?

4. В полном неориентированном графе на n вершинах длина ребра A1A2 равна -2, а остальные +1. Указать количество ребер и предпоследнюю вершину в кратчайших путях до всех вершин, полученных с помощью алгоритма Форда-Беллмана.

Билет 7

1. Дан набор булевых функций {x=>y; x|y}.

1.1. Является ли набор полным? Доказать. Если набор не полон, привести пример функции, не выражающейся через функции набора и обосновать.

1.2. Сколько функций от 1 и 2 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

1.3.* Сколько функций от 3 и 4 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

2. Посылки: Ни один ленивый человек не сдаёт экзамены. Некоторые студенты сдают экзамены. Вывод: Некоторые студенты не ленивы.

2.1. записать условие силлогизма с помощью предикатов и кванторов

2.2. доказать справедливость силлогизма методом резолюций для предикатов

3. Автоматный язык на алфавите (a;b;c} построен на основе детерминированного автомата без символов пустой строки. Как нужно изменить грамматику языка, чтобы в него обязательно входили слова, содержащие только букву b? К результирующей грамматике требование однозначности не предъявляется.

4. В полном неориентированном графе на n вершинах длины ребер A1A2 и A1A3 равны -1, а остальные +1. Какой результат даст алгоритм Форда-Беллмана, если источником берется вершина A1, а правило модификации изменено на D(v):=max{D(v); D(u)+A(u;v)}. Указать пометки всех вершин.

Билет 8

1. Дан набор булевых функций {x<=>y;x=>y}.

1.1. Является ли набор полным? Доказать. Если набор не полон, привести пример функции, не выражающейся через функции набора и обосновать.

1.2. Сколько функций от 1 и 2 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

1.3.* Сколько функций от 3 и 4 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

2. Посылки: Все информативные вещи полезны. Некоторые сайты не полезны.

Вывод: Некоторые сайты не информативны.

2.1. записать условие силлогизма с помощью предикатов и кванторов

2.2. доказать справедливость силлогизма методом резолюций для предикатов

3. Автоматный язык на алфавите (a;b;c} построен на основе детерминированного автомата без символов пустой строки. Как нужно изменить грамматику языка, чтобы в него не входили слова, у которых предпоследняя буква b?

4. В полном неориентированном графе на n вершинах длины ребер AmAk равны |m-k| (k=2,..., n), а остальных +1.

Какой результат даст алгоритм Форда-Беллмана, если источником берется вершина A1, а правило модификации изменено на ЕСЛИ D(u)+A(u;v) <= D(v) ТО D(v):=D(u)+A(u;v). Указать количество ребер в кратчайших путях, вычисляемых на основе этого правила, для всех вершин.

Билет 9

1. Дан набор булевых функций {x<=>y; x|y}.

1.1. Является ли набор полным? Доказать. Если набор не полон, привести пример функции, не выражающейся через функции набора и обосновать.

1.2. Сколько функций от 1 и 2 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

1.3.* Сколько функций от 3 и 4 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

2. Посылки: Ни один кувшин в этом шкафу не нов. Все кувшины в этом шкафу треснутые.

Вывод: Некоторые треснутые вещи в этом шкафу не новы.

2.1. записать условие силлогизма с помощью предикатов и кванторов

2.2. доказать справедливость силлогизма методом резолюций для предикатов

3. Автоматный язык на алфавите (a;b;c} построен на основе детерминированного автомата без символов пустой строки. Как нужно изменить грамматику языка, чтобы в него не входили слова, начинающиеся на букву b?

4. В полном неориентированном графе на n вершинах длины ребер A1A2 и A1A3 равны +2, а остальные +1.
Какой результат даст алгоритм Форда-Беллмана, если источником берется вершина
A1, а правило модификации изменено на ЕСЛИ D(u)+A(u;v) <= D(v) ТО D(v):=D(u)+A(u;v). Указать количество ребер в кратчайших путях для всех вершин. Как изменится ответ, если начальной будет вершина A2 ?

Билет 10

1. Дан набор булевых функций {x<=>y; xy}.

1.1. Является ли набор полным? Доказать. Если набор не полон, привести пример функции, не выражающейся через функции набора и обосновать.

1.2. Сколько функций от 1 и 2 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

1.3.* Сколько функций от 3 и 4 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

2. Посылки: Некоторые кошки бесхвосты. Все кошки — млекопитающие.

Вывод: Некоторые млекопитающие бесхвосты.

2.1. записать условие силлогизма с помощью предикатов и кванторов

2.2. доказать справедливость силлогизма методом резолюций для предикатов

3. Автоматный язык на алфавите (a;b;c} построен на основе детерминированного автомата без символов пустой строки. Как нужно изменить грамматику языка, чтобы в него не входили слова, заканчивающиеся на ab?

4. В полном неориентированном графе на n вершинах длины ребер A1A2 и A1A3 равны +2, а остальные +1. Какой результат даст алгоритм Форда-Беллмана, если источником берется вершина A1, а правило модификации изменено на D(v):=max{D(v); D(u)+A(u;v)}. Указать пометки всех вершин.

Билет 11

1. Дан набор булевых функций {x+y; x<=>y}.

1.1. Является ли набор полным? Доказать. Если набор не полон, привести пример функции, не выражающейся через функции набора и обосновать.

1.2. Сколько функций от 1 и 2 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

1.3.* Сколько функций от 3 и 4 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

2. Посылки: Все яркие цветы ароматны. Ни один ароматный цветок не выращен в помещении. Вывод: Ни один выращенный в помещении цветок не ярок.

2.1. записать условие силлогизма с помощью предикатов и кванторов

2.2. доказать справедливость силлогизма методом резолюций для предикатов

3. Автоматный язык на алфавите (a;b;c} построен на основе детерминированного автомата без символов пустой строки. Как нужно изменить грамматику языка, чтобы в него не входили слова, заканчивающиеся на букву b?

4. В полном неориентированном графе на n вершинах длина ребра A1A2 равна -1, а остальные +1. Какой результат даст алгоритм Форда-Беллмана, если источником берется вершина A1. Указать пометки всех вершин.

Билет 12

1. Дан набор булевых функций {x<=>y}.

1.1. Является ли набор полным? Доказать. Если набор не полон, привести пример функции, не выражающейся через функции набора и обосновать.

1.2. Сколько функций от 1 и 2 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

1.3.* Сколько функций от 3 и 4 переменных, не имеющих фиктивных аргументов, входят в замыкание исходного набора?

2. Посылки: Некоторые небольшие птицы питаются мёдом. Все питающиеся мёдом птицы цветные. Вывод: Некоторые цветные птицы небольшие.

2.1. записать условие силлогизма с помощью предикатов и кванторов

2.2. доказать справедливость силлогизма методом резолюций для предикатов

3. Автоматный язык на алфавите (a;b;c} построен на основе детерминированного автомата без символов пустой строки. Как нужно изменить грамматику языка, чтобы в него не входили слова, содержащие букву b?

4. В полном неориентированном графе на n вершинах длины ребер A1A2 и A1A3 равны -1, а остальные +1. Какой результат даст алгоритм Форда-Беллмана, если источником берется вершина A1. Указать пометки всех вершин.



Comments