Практикум (4 курс, весенний семестр)
Общая информация
Семинар проходит по понедельникам с 12:15 до 13:45. Практические занятия и самостоятельные работы проходят в аудитории 604.
Семинары ведет Шуплецов Михаил Сергеевич.
Второе домашнее задание
Необходимо спроектировать и реализовать при помощи СУБД Postgres базу данных для информационной поддержки учебного процесса.
Текстовое описание базы данных.
Задание разбито на несколько этапов:
- создание первичной структуры базы данных;
- написание типовых запросов;
- оптимизация базы данных;
- нормализация базы данных;
- написание правил и других проверок для поддержания целостности базы данных.
Каждый этап оценивается отдельно.
Первое домашнее задание
Необходимо спроектировать и реализовать при помощи СУБД Postgres базу данных для хранения инфомации о сложности булевых функций небольшого числа переменных, а также об известных минимальных и близких к ним контактных схемах (и схемах из функциональных элементов --- за дополнительные баллы ). База данных должна содержать все необходимые индексы, первичные и внешние ключи, а также минимальный набор проверок целостности и корректности ввода данных в таблицы.
База данных должна быть заполнена с использованием следующей информации:
Примечание. Каждая строка файла содержит информацию о сложности некоторой функции, где четыре числа, разделенные запятой, соответствуют порядковому номеру функции, столбцу значений функции (минкоду), записанному в виде десятичного числа, текущей известной оценки сложности указанной функции и значению сложности контактных схем для этой функции, получаемых методом каскадов.
Примечание. Каждая строка содержит информацию о некоторой контактной схеме, где блоки разделенные запятым соответствуют порядковому номеру схемы, минкоду, который схема реализует схема, служебный блок (для большинства схем значение равно нулю), сложности схемы, описанию схемы и служебный блок, который хранит информацию о том, является ли схема минимальной.
Опишем формат представления контактной схемы. Пусть задана контактная схема, содержащая $n, n>1$, вершин и $k$, $k \ge 0$, контактов. Считается, что все вершины схемы пронумерованы начиная с $0$ до $(n-1)$. Переменной $x_i$, $1 \leqslant i \leqslant 5$, присвоен номер $i$. Каждый контакт описывается четверкой чисел, где первые два числа являются номерами смежных с контактом вершин схемы, третье число характеризует номер переменной, приписанной контакту, а четвертое число~--- степень этой переменной ($0$~--- переменная входит с отрицанием, $1$~--- переменная входит без отрицания). Для описания контактной схемы используется следующее представление (в расширенной форме Бекуса---Наура; как обычно, фигурные скобки означают возможность пропуска либо повторения произвольное число раз):
<номер вершины> ::= '0' | ... | 'n-1'
<номер переменной> ::= '1' | ... | '5'
<степень переменной> ::= '0' | '1'
<контакт> ::= <номер вершины> ' ' <номер вершины> ' ' <номер переменной>
' ' <степень переменной>
<контактная схема> ::= <номер вершины> ' ' <номер вершины> { ' ' <контакт> }
Примечание. Лексема \tech{<контакт>} входит ровно $k$ раз. Первые два вхождения лексемы \tech{<номер вершины>} характеризуют входной и выходной полюс схемы соответственно.
Опишем формат представления схемы из функциональных элементов. Формулы Бекуса---Науэра для строк, описывающих СФЭ, имеют следующий вид:
<код ФЭ> ::= '0' | '1' | '2' | '3'
<номер вершины> ::= <НЕОТРИЦАТЕЛЬНОЕ ЦЕЛОЕ>
<список дочерних вершин> ::= <номер вершины> { ' ' <номер вершины> }
<описание вершины> ::= <номер вершины> ',' <код ФЭ> ','
<список дочерних вершин>
<список вершин> ::= <описание вершины> { ';' <описание вершины> }
<описание СФЭ> ::= <список вершин> '.'
Считается, что любая СФЭ всегда содержит шесть специальных вершин, которые служат вспомогательным целям и не учитываются при подсчёте её сложности~--- это специальная выходная вершина и одна вершина на каждую из входных переменных. Выходная вершина является стоком; в нее ведет единственная дуга, которая исходит из вершины, являющейся выходом СФЭ. Остальным специальным вершинам взаимно однозначно сопоставлены символы входных переменных $x_1$, $x_2$, $x_3$, $x_4$, $x_5$; они является истоками.
Для описания СФЭ в списке \tech{<список вершин>} перечисляются (в произвольном порядке) те и только те вершины СФЭ, из которых исходит хотя бы одна дуга. Каждая вершина СФЭ получает в описании уникальный номер \tech{<номер вершины>}. Номер выходной вершины равен нулю. Вершина, которой приписана переменная~$x_i$, $1 \leqslant i \leqslant 5$, имеет номер~$i$. Остальные вершины получают номера, строго большие $5$. Кодами функциональных элементов, реализующих конъюнкцию, дизъюнкцию, отрицание являются соответственно числа 1, 2, 3. Для вспомогательных вершин СФЭ \tech{<код ФЭ>} равен 0, для остальных вершин \tech{<код ФЭ>} принимает значение, равное коду функционального элемента, приписанного данной вершине. Список \tech{<список дочерних вершин>} перечисляет номера тех и только тех вершин, в которые из описываемой вершины исходят дуги.
В качестве результата выполнения работы присылается отчет, который должен содежать следующую информацию:
- описание структуры спроектированной базы данных в виде .sql скрипта, позволяющего создать эту базу данных в системе Postgres;
- описание запросов к спроектированной базе и результатов их выполнения.
В отчете должны содержаться следующие запросы:
- количество строк в каждой из таблиц спроектированной базы данных;
- гистограмма, указывающая число функций с заданной сложностью;
- гистограмма, указывающая число схем с заданной сложностью
Дополнительные баллы начисляются за реализацию в базе данных проверки корректности ввода схемы (ее представления).
