Задание

Добрый день, коллеги!
Для всех, кто не смог придти на лекцию 29 апреля и еще не присылал решение, остается в силе предыдущее задание. Пожалуйста, присылайте Ваши решения.
С уважением, Михаил Баранов.

Коды из лекций 10

Добрый день, коллеги!
Представляем очередную порцию слайдов с кодами из лекций. Располагаются по этой ссылке.
С уважением, Михаил Баранов.

Задание

Добрый день, коллеги!
Представляем Вам очередное задание для самостоятельной работы по курсу "Алгоритмы и структуры данных".

Напишите на естественном языке или на псевдокоде алгоритм поиска самого длинного пути в бинарном дереве поиска от корня к листовому узлу (или, что то же, алгоритм нахождения максимальной глубины в бинарном дереве поиска).

Ввод: ссылка на бинарное дерево поиска tree.

Вывод: число d, обозначающее максимальную глубину дерева tree.

С уважением, Михаил Баранов.

Коды из лекций 9

Добрый день, коллеги!
На очереди девятая порция кодов из лекций. Найти можно по ссылке.
С уважением, Михаил Баранов.

Задание+

Добрый день, коллеги!
Представляем Вам небольшое дополнительное задание для самостоятельной работы. За него можно будет получить дополнительный балл.

Напишите на естественном языке или на псевдокоде алгоритм поиска узла в бинарном дереве поиска, содержащего минимальное значение и алгоритм поиска узла, содержащего максимальное значение.

Ввод: ссылка на бинарное дерево поиска tree.

Вывод: узел, содержащий минимальное/максимальное значение в дереве tree.

С уважением, Михаил Баранов.

Коды из лекций 8

Добрый день, коллеги!
Представляем Вам восьмую порцию кодов из лекций. Найти можно здесь.
С уважением, Михаил Баранов.

Задание

Добрый день, коллеги!
Представляем Вам очередное задание для самостоятельной работы по курсу "Алгоритмы и структуры данных".

Напишите на естественном языке или на псевдокоде алгоритм обохода дерева SiblingTree по уровням, т.е. сначала посещается корень, затем все дочерние узлы (имеющие уровень 1), затем дочерние узлы дочерних узлов (имеющие уровень 2) и т.д., так что последовательно посещаются все узлы на одном уровне. Дерево SiblingTree состоит из узлов, каждый из которых имеет следующую структуру:

- значение, хранимое в данном узле;

- ссылка на узел, являющийся самым левым ребенком данного узла;

- ссылка на родительский узел для данного узла;

- ссылка на следующего (при отображении слева направо и корне вверху) брата/сестру.

Ввод: ссылка tree на дерево типа SiblingTree, ссылка на метод Visit(node), который выполняет некоторую работу при посещении узла node дерева.

Вывод: выполнение метода Visit(node) для каждого узла дерева tree по уровням, от меньшего уровня к большему.

С уважением, Михаил Баранов.

Лекция от 19 апреля

Добрый день, коллеги!
В лекции от 19 апреля мы лишь начали написание бинарного дерева поиска и дерева SiblingTree. Код будет опубликован после того, как мы закончим создание этих типов. Если Вам нужен текущий код для анализа, пожалуйста, присылайте соответствующий запрос мне на почту misha_bar@mail.ru.
С уважением, Михаил Баранов.

Курс в целом и успеваемость

Добрый день, коллеги!
На данном этапе очень бы хотелось оценить ход курса "Алгоритмы и структуры данных" как со стороны материала, способов его изложения, так и со стороны успеваемости всех слушателей курса. Пожалуйста, пишите в комментариях к данному сообщению или мне на почту misha_bar@mail.ru Ваши впечатления, замечания, пожелания по поводу курса, просто общие слова. Возможно, Вы бы хотели обсудить какую-то определенную тему, скажем, на последнем, дополнительном занятии, или встретиться и подвести итоги по пройденному материалу.
В свою очередь, здесь, в этом сообщении, будет публиковаться некоторый рейтинг успеваемости слушателей, которые хотя бы раз присылали свои решения к заданиям.
На текущий момент таблица успеваемости выглядит следующим образом (последнее обновление 31 мая; красный цвет означает, что по итогам выполнения домашних заданий, курс усвоен менее, чем на 50%, оранжевый - от 50% до 80%, зеленый - усвоено более 80%):
 Андрей Кашин (97%)
 Виталий Зубков (76%)
 Алексей Хоченков (74%)
 Дмитрий Вакин (72.5%)
 Александр Масалин (69%)
 Наталья Станкова (61%)
 Александр Рыбаков (58%)
 Илья Левцов (50%)
 Анна Смородина (40%)
 Александр Николаев (37%)

Ждем Ваши комментарии и письма!
С уважением, Михаил Баранов.

Задание

Добрый день, коллеги!

Представляем Вам очередное задание для самостоятельной работы по курсу "Алгоритмы и структуры данных".

Разработайте тип данных, представляющий список управления доступом (Access Control List, ACL). Под разработкой понимается описание типа данных на естественном языке: поддерживаемые операции, внутренние структуры данных, обоснование выбора этих структур. 

В простом варианте, ACL должен представлять собой тип данных, содержащий список пользователей, которым разрешен доступ к какому-то ресурсу. 

В более сложном (и необязательном) варианте, ACL должен различать виды доступа: создание (create), чтение (read), запись (update), удаление (delete), полный доступ (full trust).

Использование данного типа может быть следующим. Логические объекты в системе (например, файлы или документы) содержат указатель на экземпляр списка управления доступом. Данный экземпляр содержит список пользователей, имеющих разрешение на получение доступа к этому логическому объекту (к файлу или документу). Клиент может проверить, разрешен ли доступ или разрешен ли конкретный вид доступа какому-то пользователю.

С уважением, Михаил Баранов.

Коды из лекций 7

Добрый день, коллеги!
Представляем Вам седьмую порцию кодов из лекций. Как и всегда, найти их можно по ссылке.
С уважением, Михаил Баранов.

Задание

Добрый день, коллеги!
Представляем Вам очередное задание для самостоятельной работы по курсу "Алгоритмы и структуры данных".

Напишите на естественном языке или псевдокоде алгоритм проверки правильности простановки скобок в выражении, используя стек.

Ввод: строковое выражение, содержащее, возможно, кроме прочих символов, скобки различного вида, а именно: (),{},[],<>

Вывод: истина, если все скобки правильно открыты/закрыты, ложь – в противном случае.

Например, на входе может быть строка "class Vector<T> { public Vector() {} }". Здесь все скобки открыты и закрыты верно. А, например, строка "[3+(5*6)/2" имеет незакрытую скобку.

С уважением, Михаил Баранов.

Коды из лекций 6

Добрый день, коллеги!
Представляем Вам шестую порцию кодов из лекций. Найти их можно по этой ссылке.
С уважением, Михаил Баранов.

Задание

Добрый день, коллеги!

Представляем Вам очередное задание для самостоятельной работы по курсу "Алгоритмы и структуры данных".

Напишите план, которым Вы будете руководствоваться при создании типа данных Сетка со следующими совйствами:

1. Сетка (grid) представляет прямоугольник, состоящий из ячеек, в которых хранятся некоторые данные.

2. Ширина и высота сетки задаются при ее создании.

3. Сетка должна позволять работать со всеми ячейками.

Какие внутренние структуры Вы выберете для создания такой сетки? Какие основные операции реализуете?

С уважением, Михаил Баранов.

Коды из лекций 5

Добрый день, коллеги!
Представляем Вам очередную, пятую, порцию кодов из лекций. Они доступны по этой ссылке.
С уважением, Михаил Баранов.

Коды из лекций 4

Добрый день, коллеги!
Представляем очередную порцию слайдов с кодом из лекций. Найти можно здесь.
С уважением, Михаил Баранов.