Кто читает:: Кафедра информационных технологий в бизнесе (Пермь) (Факультет социально-экономических и компьютерных наук)

Статус:: Курс обязательный

Когда читается:: 1-й курс, 2, 3 модуль

Преподаватель

Марквирер Владлена Дмитриевна

Дополнительные материалы в LMS Задать вопрос

Аннотация

Дисциплина формирует фундаментальные знания о принципах представления и обработки информации в вычислительных системах, начиная с систем счисления и внутреннего представления чисел в памяти компьютера. Обучающиеся изучают адресную арифметику и организацию массивов, а также формальные модели описания алгоритмов и оценку их вычислительной сложности. Значительное внимание уделяется динамическим структурам данных и методам управления памятью. Отдельные разделы посвящены оптимизации индексирования данных в базах данных и файловых системах на основе древовидных структур и хеширования. Завершает курс изучение формальных языков и грамматик, обеспечивающее теоретическую базу для анализа и синтеза языковых конструкций.

Цель освоения дисциплины

Целью освоения дисциплины является формирование у обучающихся фундаментальных теоретических знаний о принципах представления, хранения и обработки информации в вычислительных системах, а также развитие навыков формального описания алгоритмов и структур данных для эффективного решения прикладных задач программирования и проектирования информационных систем.

Планируемые результаты обучения

Отличает позиционные и непозиционные системы счисления
Воспроизводит алгоритмы для перевода чисел из одной системы счисления в другую
Вычисляет внутреннее представление чисел в компьютере нужного типа и формата данных
Использует указатели для решения задач
Реализует массив для хранения и последующей обработки данных
Объясняет и формулирует алгоритмы сортировки и поиска в массивах
Придумывает алгоритмы для решения задач в системе команд Машины Тьюринга
Определяет набор подстановок для корректной работы по принципам Нормального Алгорифма Маркова при решении задач
Различает особенности разных динамических структур для хранения данных
Иллюстрирует порядок рекурсивных вызовов
Использует различные механизмы рехеширования данных
Описывает и реализует список для индексирования большого набора данных по ключевому(-ым) атрибуту(-ам)
Описывает и реализует бинарное дерево для индексирования большого набора данных по ключевому(-ым) атрибуту(-ам)
Объясняет и строит B-деревья для индексирования данных на простых примерах
Определяет правила для грамматики языка в нотациях БНФ/РБНФ и в виде диаграмм Вирта
Реализует описанные правила грамматики в виде исполняемой программы
Показывает деревья синтаксического разбора выражения
Использует Обратную польскую запись для вычисления выражения

Содержание учебной дисциплины

Системы счисления и внутреннее представление чисел в памяти компьютера
Адресная арифметика и массивы
Формальное описание алгоритмов
Динамические структуры данных
Оптимизация индексирования данных в базах данных и файловых системах
Формальные языки и грамматики

Элементы контроля

Операции с числами во внутреннем представлении
Работа в команде на решение заданий по операциям с числами во внутреннем представлении. Решение представляем на листочках и сдаём в конце семинара.
Указатели и массивы в C++
Решение теста в команде на одном компьютере в аудитории проведения занятия.
Алгоритмы сортировки массивов
Студенты в команде составляют алгоритмы сортировки и подготавливают примеры тестовых массивов для которых записывают пошаговую сортировку. Результаты выполнения сдаются в конце семинара.
МТ и НАМ
Студенты в команде решают задачи с помощью МТ и НАМ. Решения сдаются в конце семинара.
ТОИ-КВИЗ
Студенты в командах участвуют в квизе (викторине) по теоретическим основам информатики, отвечают на вопросы в режиме реального времени по правилам проведения туров квиза.
Рекурсивная закраска
Каждой команде выдаётся алгоритм закраски и случайная фигура. Команды строят дерево закраски и иллюстрируют порядок закраски фигуры.
Индексация данных
Презентация команды про реализацию индексирования данных в динамических структурах. Работа подготавливается студентами в командах самостоятельно, вне аудиторных занятий. Результаты представляются на семинаре в виде доклада с презентацией.
Построение B-дерева
Студенты в команде выполняют пошаговое построение B-дерева по исходному набору значений.
Интерпретатор калькулятора
Студенты в командах выполняют реализацию правил грамматики и работы своего калькулятора. В презентации демонстрируют результаты выполнения работы по этапам с чёткой фиксацией сложности грамматики.
Экзамен
Экзамен проводится в формате теста с отметкой ответов в бланке как в Ивановских тестах.

Промежуточная аттестация

2026/2027 3rd module
0.12 * Интерпретатор калькулятора + 0.03 * Рекурсивная закраска + 0.06 * Операции с числами во внутреннем представлении + 0.12 * Индексация данных + 0.03 * Построение B-дерева + 0.4 * Экзамен + 0.06 * Алгоритмы сортировки массивов + 0.06 * МТ и НАМ + 0.03 * Указатели и массивы в C++ + 0.09 * ТОИ-КВИЗ

Список литературы

Авторы

Карпович Марина Валерьевна
Марквирер Владлена Дмитриевна

Бакалаврская программа «Разработка информационных систем для бизнеса»

Теоретические основы информатики

Преподаватель

Программа дисциплины