4912
.pdfЗадача 8. Написать функцию добавления элемента в конец односвязного списка.
Задача 9. Написать функцию поиска первого вхождения элемента в односвязный список.
Задача 10. Написать функции Push и Pop для стека, хранящегося в односвязном списке.
Задача 11. Написать процедуру вставки элемента в упорядоченный по возрастанию односвязный список, инициализированный целыми числами.
Задачи для раздела 3.
Задача 1 Написать процедуру представления графа матрицей смежности.
Задача 2. Написать процедуру представления графа списком ребер.
Задача 3. Написать процедуру поиска в глубину dfs.
Задача 4. 4 Найти компоненты связности графа.
Задача 5. Составить нерекурсивный алгоритм топологической сортировки ориенти-
рованного графа без циклов.
Задача 6. Составить рекурсивный алгоритм топологической сортировки ориентиро-
ванного графа без циклов.
Задача 7. 8 Реализовать алгоритм поиска в ширину.
Задача 8. Найти кратчайшие пути от одной из вершин графа до другой, используя алгоритм Дейкстры.
Задача 9. На основании приведенной в лекции функции реализуйте программу, в
которой выполняется переборный алгоритм методом поиска в ширину.
Задача 10 Упорядочите вершины графа по возрастанию количества ребер, выходя-
щих из этой вершины. Результат дайте в следующем виде: номер вершины и рядом
(в круглых скобках) число, выражающее количество выходящих из этой вершины ребер.
Задача 11. Найти максимальную компоненту связности графа.
11
4. Методические рекомендации по организации самостоятельной ра-
боты
4.1 Общие рекомендации для самостоятельной работы
Самостоятельная работа студентов является основным способом овладения учебным материалом в свободное от обязательных учебных занятий время.
Целями самостоятельной работы студентов являются:
- систематизация и закрепление полученных теоретических знаний и практиче-
ских умений студентов;
-углубление и расширение теоретических знаний;
-формирование умений использовать нормативную, правовую, справочную до-
кументацию и специальную литературу;
-развитие познавательных способностей и активности студентов:
-формирования самостоятельности мышления, способностей к саморазвитию,
самосовершенствованию и самореализации.
Запланированная в учебном плане самостоятельная работа студента рассматри-
вается как связанная либо с конкретной темой изучаемой дисциплины, либо с подго-
товкой к курсовой, дипломной работе, а также к защите ВКР. В данном разделе рас-
сматривается только самостоятельная работа первого вида.
Самостоятельная работа выполняется в два этапа: планирование и реализация.
Планирование самостоятельной работы включает:
-уяснение задания на самостоятельную работу;
-подбор рекомендованной литературы;
-составление плана работы, в котором определяются основные пункты пред-
стоящей подготовки.
Составление плана дисциплинирует и повышает организованность в работе.
На втором этапе реализуется составленный план. Реализация включает в себя:
-изучение рекомендованной литературы;
-составление плана (конспекта) по изучаемому материалу (вопросу);
-взаимное обсуждение материала.
Необходимо помнить, что на лекции обычно рассматривается не весь материал.
12
Оставшаяся восполняется в процессе самостоятельной работы. В связи с этим рабо-
та с рекомендованной литературой обязательна.
Работа с литературой и иными источниками информации включает в себя две группы приемов: техническую, имеющую библиографическую направленность, и
содержательную. Первая группа – уяснение потребностей в литературе; получение литературы; просмотр литературы на уровне общей, первичной оценки; анализ надежности публикаций как источника информации, их относимости и степени по-
лезности. Вторая – подробное изучение и извлечение необходимой информации.
Для поиска необходимой литературы можно использовать следующие способы:
-поиск через систематический каталог в библиотеке;
-просмотр специальных периодических изданий;
-использование материалов, размещенных в сети Интернет.
Для того, чтобы не возникало трудностей понимания текстов учебника, моно-
графий, научных статей, следует учитывать, что учебник и учебное пособие предна-
значены для студентов и магистрантов, а монографии и статьи ориентированы на исследователя. Монографии дают обширное описание проблемы, содержат в себе справочную информацию и отражают полемику по тем или иным дискуссионным вопросам. Статья в журнале кратко излагает позицию автора или его конкретные до-
стижении в исследовании какой-либо научной проблемы.
В процессе взаимного обсуждения материала закрепляются знания, а также приобретается практика в изложении и разъяснении полученных знаний, развивает-
ся речь.
При необходимости студенту следует обращаться за консультацией к препода-
вателю.
Составление записей или конспектов позволяет составить сжатое представле-
ние по изучаемым вопросам. Записи имеют первостепенное значение для самостоя-
тельной работы студентов. Они помогают понять построение изучаемого материала,
выделить основные положения, проследить их логику.
Ведение записей способствует превращению чтения в активный процесс. У
студента, систематически ведущего записи, создается свой индивидуальный фонд
13
подсобных материалов для быстрого повторения прочитанного. Особенно важны и полезны записи тогда, когда в них находят отражение мысли, возникшие при само-
стоятельной работе.
Можно рекомендовать следующие основные формы записи: план, конспект, те-
зисы, презентация.
План – это схема прочитанного материала, краткий (или подробный) перечень вопросов, отражающих структуру и последовательность материала. Подробно со-
ставленный план вполне заменяет конспект.
Конспект – это систематизированное, логичное изложение материала источни-
ка. Объем конспекта не должен превышать 10 страниц. Шрифт Times New Roman,
кегль 14, интервал 1,5. Список литературы должен состоять из 5-8 источников, по возможности следует использовать последние издания учебных пособий и исследо-
ваний.
Тезисы — это последовательность ключевых положений из некоторой темы без доказательств или с неполными доказательствами. По объему тезисы занимают одну страницу формата А4 или одну – две страницы в ученической тетради. В конце те-
зисов студент должен сделать собственные выводы.
Презентации по предложенной теме составляются в программе Power Point или
Impress. Количество слайдов должно быть не менее 15 и не превышать 20 слайдов.
Кроме текста на слайдах можно создавать схемы и таблицы. Шрифт должен быть читаемым, например, шрифт черного цвета на светлом фоне или светлый шрифт на темном фоне. Также шрифт не должен быть слишком мелким. В слайдах указывают-
ся только основные тезисы, понятия и нормы.
4.2 Темы для самостоятельного изучения
1 Остовные деревья.
2.Динамическое программирование: задача о рюкзаке.
3.Алгоритм Дейкстры поиска кратчайших путей в графах.
4.Реализация основных операций над списками как методы класса List в языке Си#.
5.Реализация основных операций над массивами как методы класса Array в языке Си#.
14
4.3 Учебно-методическое обеспечение самостоятельной работы
1. Комбинаторные алгоритмы для программистов: учебное пособие/ Костюкова Н.
И. Интернет-Университет Информационных Технологий (ИНТУИТ), 2018.
2. Алгоритмы и структуры данных: Лабораторный практикум. Учебное пособие.
Синюк В. Г., Рязанов Ю. Д. Белгород: Белгородский государственный технологиче-
ский университет им. В.Г. Шухова, ЭБС АСВ, 2013.
3. Графы и их применение. Комбинаторные алгоритмы для программистов: учебное пособие. Костюкова Н. И. Москва: БИНОМ. Лаборатория знаний, Интернет-
Университет Информационных Технологий (ИНТУИТ), 2013.
4. Структуры и алгоритмы обработки данных. Примеры на языке СИ: Учебное по-
собие. – Финансы и статистика, 2004. – 464с.
4.4 Задания для самостоятельной работы
Раздел 1: Алгоритмы и данные
Задача 1 Написать процедуру вычисления чисел Фибоначчи (Сложность О(n)).
Задача 2. Дан одномерный целочисленный массив, заданный случайными числами.
Выполните циклический сдвиг элементов с нулевой позиции вправо на одну пози-
цию. То есть должна быть реализована схема перестановок: x[0] -> x[1], x[1] -> x[2],..., x[n-1] -> x[0].
Задача 3. Написать функцию вычисления корня многочлена f(x) = x5 + ax + b,
где a > 0, b – любое (абсолютно точный вещественный поиск).
Задача 4. Оптимизировать сортировку пузырьком по количеству пузырьков.
Задача 5. Написать процедуру Extract_min извлечения минимального элемента из кучи на минимум (предварительно сделав из массива кучу).
Раздел 2: Линейные структуры данных
Задача 1. Написать функцию добавления элемента в конец односвязного списка.
15
Задача 2. Вставьте элемент 3 в упорядоченный односвязный список 1, 2, 4, 5.
Задача 3. В двусвязный список 2, 1, 6, 7, 10, 3, 12, 15 добавить элемент 888 между 10
и 3.
Задача 4. Написать несколько функций для работы со структурой «Работники» (см.
лекции).
Задача 5. Написать процедуру инициализации двусвязного списка.
Раздел 3: « Типы данных. Структуры хранения данных Задача 1. На основании приведенной в лекции функции реализуйте программу, в
которой выполняется переборный алгоритм методом поиска в ширину.
Задача 2. Найдите вершину графа, из которой выходит наибольшее число ребер.
Задача 3. Найти количество компонент связности графа.
Задача 4. Неориентированный граф называется двудольным, если его вершины можно раскрасить в два цвета так, что концы любого ребра — разного цвета. Соста-
вить алгоритм проверки, является ли заданный граф двудольным, в котором число действий не превосходит C · (число рёбер + число
вершин).
/Указание: (а) Каждую связную компоненту можно раскрашивать отдельно. (б) Вы-
брав цвет одной вершины и обходя ее связную компоненту, мы определяем един-
ственно возможный цвет остальных.
Замечание. В этой задаче безразлично, производить поиск в ширину или в глубину./
Задача 5. Имеется семь городов, соединенных некоторой сетью дорог. В каком го-
роде необходимо провести конференцию так, чтобы суммарный путь всех делега-
тов, по одному из каждого города, был минимален.
16
О.В. Любимцев
АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
Учебно-методическое пособие
по подготовке к лекционным и практическим занятиям (включая рекомендации по организации самостоятельной работы)
для обучающихся по дисциплине «Алгоритмы и структуры данных» по направлению подготовки 09.03.04 Программная инженерия профиль Разработка программно-информационных систем
Федеральное государственное бюджетное образовательное учреждение высшего образования «Нижегородский государственный архитектурно-строительный университет»
603950, Нижний Новгород, ул. Ильинская, 65. http://www. nngasu.ru, srec@nngasu.ru
17