Теоретические основы информатики (Росдистант) 2025
Практические работы №1,2,3,4
Выполнены на 100%
Задания в демонстративных файлах
Разработка алгоритма хеш-функции для реализации таблиц идентификаторов
1. Разработать программу, на выбранном языке программирования, генерирующей 400 случайных идентификаторов (начинаются с символа латиницы и имеют случайную длину) и сохранить их в файл ID.txt. 2. Выбрать 2 любые хеш функции на основе открытых источников или предложенной для практики литературы. Диапазон значений хеш функций должен лежат в пределах от 1 до 1000. 3. Реализовать вычисление хеш функций на выбранном языке программирования. 4. Реализовать чтение идентификаторов с файла ID.txt, вычисление для них хеш функции и сохранение в массив M_ID в ячейку с номеров полученного хеш значения идентификатора (для которого вычислялась хеш функция). 5. Если в данном элементе массива уже есть идентификатор (коллизия), то добавить новый идентификатор через разделитель к имеющемуся в элементе массива. Одновременно занести оба идентификатора в отдельный массив M_Col в порядке их обнаружения. 6. По окончании чтения всего списка входных идентификаторов вывести массивы M_Col и M_ID в отдельные файлы с расширением txt. 1. Файл M_ID должен иметь запись всех ячеек массива в порядке возрастания с указанием в 1 столбце номера элемента массива. Пустые элементы также подлежат выводу в файл. 2. Файл M_Col должен содержать номер элемента массива, хеш- значение и список идентификаторов. 3. В конце файла должно быть вычислено отношение количества коллизий к количеству идентификаторов в %. 4. Расчет хеш значений должен быть выполнен для двух хеш функций. 7. Провести сравнение полученных результатов на эффективность хеш функций с точки зрения возникновения коллизий.
Разработка и реализация модуля по созданию таблицы идентификаторов
1. Разработать программу, реализующую создание таблицы идентификаторов по заданным алгоритмам (один из них на основе хэш функции, взятой с предыдущей работы. Варианты заданий приведены на стр 28 в «Системное программное обеспечение. Лабораторный практикум.pdf» 2. Добавить в программу глобальный счетчик для подсчета затраченных элементарных тактов процессора с целью исследования эффективности разработанной программы. 3. Выполнить исследование эффективности работы разработанной программы с помощью подсчета затраченных элементарных операций при заполнении таблицы идентификаторов на 25, 50, 75 и 100 %. 4. Представить сравнительный анализ эффективности работы разработанной программы в виде электронной таблицы с получением выводов по данным алгоритмам реализации.
Разработка конечного автомата для заданной грамматики
1. На основе заданной грамматики выделить и описать все лексемы для данной грамматики. Для сложных лексем привести грамматику. 2. Построить описание КА, лежащего в основе лексического анализатора (в виде набора множеств и функции переходов или в виде графа переходов) Работа должна содержать: - выбор способа описания конечного автомата (граф или таблица состояний). - исходя из задания перечень в виде списка всех лексем. - описание грамматики сложных лексем. - в виде списка перечень символов для границ лексем. - перечень выбранных состояний конечного автомата. - разработанный конечный автомат.
Разработка лексического анализатора на основе автоматного программирования
1. выбрать стиль программирования для разработки ЛА (предлагается использовать автоматное программирование). 2. Разработать блок схему алгоритма для реализации ЛА. 3. Привести список переменных и структур разрабатываемого ЛА. 4. Разработать ЛА в виде примера исходного текста в соответствии с грамматикой к КР и полученной таблицы лексем. 5. Привести исходный текст и работающая программа 6. Выбрать способ передачи таблицы лексем с ЛА в синтаксический разборщик ( через файл, область памяти или другой способ). 7. Описать выбранную структуру для передачи таблицы лексем: например имя файла, состав столбцов в файле, примененный разделитель и т. д. 8. Привести пример внутренней структуры для передачи таблицы лексем.
Реализация синтаксического управляемого перевода для заданной КС грамматики
1. Выбрать формы внутреннего представления программы: тетрады, триады, ассемблер или обратная польская запись (ПОЛИЗ). 2. Привести дерево операций полученное из дерева разбора в предыдущей практике 3 Разработать таблицу преобразования узлов дерева операций в выбранный выходной код внутреннего представления программы. 4. Привести пошаговый пример преобразования дерева операций в выходной код на основе СУ перевода. 5 Разработать алгоритм реализации процесса преобразования дерева операций в выходной код на основе СУ перевода. 6. Реализовать программу преобразования дерева операций в выходной код на основе СУ перевода, включающей исходный текст примера и выходной код. 7. Привести исходный текст программы и ее рабочую реализацию в отдельном каталоге.
Разработка компилятора для заданной КС грамматики
1. Выбрать способ интеграции разработанных программ по созданию таблицы идентификаторов, ЛА, СР и СУ перевода в единую программу-компилятор. Например в виде последовательно применяемых программ, или запись всех компонент в один файл программу, или создание проекта в среде программирования и объединение всех компонент через единый заголовочный файл. 2. Привести таблицу описания всех компонент с входящими в них файлами. 3. В качестве дополнительного материала (необязательного) может быть приведена диаграмма компонент или классов. 4. Разработать функциональный алгоритм работы разработанного компилятора в виде последовательности выполняемых разработанных компонент компилятора. 5. Привести исходный текст программы и ее реализацию в отдельном каталоге. 6. Описать разработанный компилятор в виде руководства по работе с программой на основе стандартного подхода описания программ в ОС, например http://man7.org/linux/man-pages/man1/ls.1.html (писать описание на русском).
Разработка матрицы предшествования для заданной КС грамматики
1. Описать грамматику разрабатываемого разборщика на основе задание по КР. Данная грамматика может разделена на отдельные структуры с целью минимизации разрабатываемого разборщика. Например сделать 2 грамматики, отдельно для управляющей структуры и отдельно для арифметических выражений. 2. Разработать таблицы всех крайних левых и крайних правых символов относительно нетерминальных символов. 3. Разработать таблицы всех крайних левых и крайних терминальных правых символов относительно нетерминальных символов. 4. Разработать матрицу предшевствования.
Реализация синтаксического разбора для заданной КС грамматики
1. Привести пример пример исходного текста программы для проверки работы синтаксического разборщика (СР). 2. Описать остовную грамматику в соответствии с заданием к КР. 3. Привести пример преобразования исходного текста в список правил. Пример должен включать пошаговую работу СР с демонстрацией входного потока, состояния магазинной памяти и списка примененных правил для выполнения свертки кода. 4. Разработать блок схему алгоритма для реализации СР. 5. Реализовать работающую программу СР. 6. Привести плученное дерево разбора в результате полученных правил для используемого примера исходного текста. 7. Привести исходный текст программы и ее реализация в отдельном каталоге.
