Algorithms and data structures

Краткое содержание учебной дисциплины, модуля / Brief summary

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

Темы:

1. Создание простейших программ

2. Массивы и функции

3. Интерактивный ввод, файлы и графика

4. Сложность алгоритмов, рекурсия, методы сортировки

5. Стек, очередь, бинарная куча

6. Словари, множества, графы

7. Жадные алгоритмы, перебор с возвратом, динамическое программирование

The course is designed to develop knowledge and practical skills in writing programs in Python (version 3) using fundamental data structures and algorithmic paradigms. Prior knowledge of Python is not required, as the course is taught through solving a significant number of practical problems covering the basics of programming.

Topics:

1. Creating basic programs

2. Arrays and functions

3. Interactive input, files, and graphics

4. Algorithm complexity, recursion, sorting methods

5. Stack, queue, binary heap

6. Dictionaries, sets, graphs

7. Greedy algorithms, backtracking, dynamic programming

Формируемые компетенции / The formed competences

Базовые профессиональные компетенции:

БПК-3. Применять математический аппарат в интеграции с компьютерными средами для создания и исследования моделей различных уровней абстракции.

Специализированные компетенции:

СК-2. Применять современные технологии и базовые конструкции языков программирования, проектировать, создавать и использовать базы данных для реализации алгоритмических прикладных задач и разработки веб- проектов.

Basic professional competencies:

BPC-3. Apply mathematical apparatus in integration with computer environments to create and study models of different levels of abstraction.

Specialized competencies:

SC-2. Apply modern technologies and basic constructs of programming languages, design, create, and use databases for implementing algorithmic applied tasks and developing web projects.

Результаты обучения (знать, уметь, владеть) / Learning outcomes (know, can, be able)

знать:

– O-асимптотику и классы сложности алгоритмов;

– Основные структуры данных (список, кортеж, стек, очередь, бинарная куча, словарь, множество, граф), их реализацию в Python и оценку сложности операций над ними;

– Вычислительные алгоритмы (алгоритм Евклида, перевод числа в другую систему счисления, построение таблицы истинности, разложение числа на множители, приведение матрицы к ступенчатому виду, матричное произведение, метод Гаусса);

– Приближенные вычислительные алгоритмы (метод Ньютона, разложение числа пи, численное интегрирование, метод МонтеКарло);

– Основные алгоритмические парадигмы (метод грубой силы, жадная стратегия, бинарный поиск, рекурсия, перебор с возвратом, «разделяй и властвуй», динамическое программирование);

– Основные методы сортировки (пузырьком, вставками, выбором, слиянием, быстрая сортировка, сортировка кучей);

– Основные алгоритмы на графах (обход в ширину, обход в глубину, топологическая сортировка, алгоритм Дейкстры);

уметь: 

– Составлять алгоритмы решения практических задач;

– Писать программы и алгоритмы на языке Python (версии 3);

– Анализировать эффективность алгоритмов и выбирать наиболее

подходящий в конкретной ситуации;

владеть: 

– Навыками создания программ с использованием алгоритмов и алгоритмических парадигм для решения практических задач на языке Python;

– Умением работать с различными инструментами для анализа и оптимизации алгоритмов.

know:

– O-asymptotics and algorithm complexity classes;

– Basic data structures (list, tuple, stack, queue, binary heap, dictionary, set, graph), their implementation in Python, and their complexity analysis;

– Computational algorithms (Euclidean algorithm, number conversion to another numeral system, truth table construction, number factorization, matrix row reduction, matrix multiplication, Gaussian elimination);

– Approximate computational algorithms (Newton’s method, calculation of Pi number, numerical integration, Monte Carlo method);

– Main algorithmic paradigms (brute force, greedy strategy, binary search, recursion, backtracking, “divide and conquer,” dynamic programming);

– Basic sorting methods (bubble sort, insertion sort, selection sort, merge sort, quicksort, heap sort);

– Main graph algorithms (breadth-first search, depth-first search, topological sorting, Dijkstra’s algorithm);

be able to: 

– Design algorithms for solving practical problems;

– Write programs and algorithms in Python (version 3);

– Analyze the efficiency of algorithms and choose the most suitable one in a particular situation;

possess: 

– Skills in creating programs using algorithms and algorithmic paradigms for solving practical problems in Python;

– The ability to work with various tools for analyzing and optimizing algorithms.

Семестр изучения учебной дисциплины, модуля / Semester of study

2

2

Пререквизиты / Prerequisites

–

–

Трудоемкость в зачетных единицах (кредитах) / Credit units

3

3

Количество аудиторных часов и часов самостоятельной работы / Academic hour of students’ class work, 

hours of self-directed learning

Всего 90 часов, в том числе 50 аудиторных часов, из них: лекции – 16 часов, лабораторные занятия – 30 часов, управляемая самостоятельная работа – 4 часа.

Total 90 hours, including 50 classroom hours, including: lectures – 16 hours, 30 hours, self-directed learning – 4 hours.

Требования и формы текущей и промежуточной аттестации / Requirements and forms of current and interim certification

Текущая аттестация: отчет по лабораторной работе с устной защитой; отчет по заданиям УСР с устной защитой; контрольная работа.

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

Current certification: report on laboratory work with oral defense; report on the self-directed learning tasks with oral defense; control work.

Interim certification: test.