5009
.pdf3. Методические указания по подготовке к практическим
занятиям
3.1 Общие рекомендации по подготовке к практическим занятиям
В ходе подготовки к практическим занятиям необходимо изучать ос-
новную литературу, знакомиться с дополнительной литературой, а также с новыми публикациями в периодических изданиях: журналах, газетах и т.д.
При этом необходимо учесть рекомендации преподавателя и требования учебной программы.
В соответствии с этими рекомендациями и подготовкой полезно дора-
батывать свои конспекты лекции, делая в нем соответствующие записи из литературы, рекомендованной преподавателем и предусмотренной учебной программой. Целесообразно также подготовить тезисы для возможного выступления по всем учебным вопросам, выносимым на практическое за-
нятие.
При подготовке к занятиям можно также подготовить краткие кон-
спекты по вопросам темы. Очень эффективным приемом является состав-
ление схем и презентаций.
Готовясь к докладу или реферативному сообщению, желательно об-
ращаться за методической помощью к преподавателю. Составить план-
конспект своего выступления. Продумать примеры с целью обеспечения тесной связи изучаемой теории с реальной жизнью. Своевременное и каче-
ственное выполнение самостоятельной работы базируется на соблюдении настоящих рекомендаций и изучении рекомендованной литературы. Сту-
дент может дополнить список использованной литературы современными источниками, не представленными в списке рекомендованной литературы,
и в дальнейшем использовать собственные подготовленные учебные мате-
риалы при написании курсовых и дипломных работ.
11
3.2 Примеры задач для практических занятий
Задачи для раздела 1.
Задача 1. Написать процедуру Insert вставки элемента в упорядоченный массив.
Задача 2. Написать функцию поиска второго максимума в массиве (за один проход по массиву).
Задача 3. Написать функцию Search поиска с барьером элемента в массиве.
Задача 4. Написать процедуру бинарного поиска элемента в массиве.
Задача 5. Написать процедуру Sort_insert сортировки массива вставками, используя процедуру Insert вставки элемента в упорядоченный массив.
Задача 6. Написать процедуру Sort_bubble сортировки массива пузырьком.
Задача 7. Сортировка массива Heap_sort (сортировка кучей на месте).
Задача 8. Написать процедуру Quick_sort быстрой сортировки.
Задача 9. При различных входных данных сравнить время работы
Quick_sort, Bubble_sort, Heap_sort.
Задача 10. Дано n отрезков [a[i], b[i]] на прямой (i = 1 . . . n). Найти макси-
мальное k, для которого существует точка прямой, покрытая k отрезками («максимальное число слоев»). Число действий — порядка n log n.
Задача 11. Оптимизировать сортировку пузырьком по направлению пузырьков (шейкерная сортировка).
Задача 12. Отсортировать массив с помощью кучи на минимум, используя два массива.
12
Задачи для раздела 2.
Задача 1. Написать функции Push и Pop для стека, хранящегося в массиве.
Задача 2. Решить задачу о правильной скобочной последовательности, ис-
пользуя стек, хранящегося в массиве.
Задача 3 Реализовать операции с очередью ограниченной длины так, что-
бы количество действий для каждой операции было ограничено констан-
той, независящей от длины очереди.
Задача 4. Написать процедуру инициализации односвязного списка.
Задача 5. Написать функцию удаления элемента из односвязного списка.
Задача 6. Написать функцию добавления элемента в конец двусвязного списка.
Задача 7. Деком называют структуру, сочетающую очередь и стек: класть и забирать элементы можно с обоих концов. Как реализовать дек ограни-
ченного размера на базе массива так, чтобы каждая операция требовала ограниченного числа действий?
Задача 8. Написать функцию добавления элемента в конец односвязного списка.
Задача 9. Написать функцию поиска первого вхождения элемента в одно-
связный список.
Задача 10. Написать функции Push и Pop для стека, хранящегося в одно-
связном списке.
Задача 11. Написать процедуру вставки элемента в упорядоченный по воз-
растанию односвязный список, инициализированный целыми числами.
13
Задачи для раздела 3.
Задача 1 Написать процедуру представления графа матрицей смежности.
Задача 2. Написать процедуру представления графа списком ребер.
Задача 3. Написать процедуру поиска в глубину dfs.
Задача 4. 4 Найти компоненты связности графа.
Задача 5. Составить нерекурсивный алгоритм топологической сортировки ориентированного графа без циклов.
Задача 6. Составить рекурсивный алгоритм топологической сортировки ориентированного графа без циклов.
Задача 7. 8 Реализовать алгоритм поиска в ширину.
Задача 8. Найти кратчайшие пути от одной из вершин графа до другой, используя алгоритм Дейкстры.
Задача 9. На основании приведенной в лекции функции реализуйте про-
грамму, в которой выполняется переборный алгоритм методом поиска в ширину.
Задача 10 Упорядочите вершины графа по возрастанию количества ребер,
выходящих из этой вершины. Результат дайте в следующем виде: номер вершины и рядом (в круглых скобках) число, выражающее количество вы-
ходящих из этой вершины ребер.
Задача 11. Найти максимальную компоненту связности графа.
14
4. Методические рекомендации по организации самостоя-
тельной работы
4.1 Общие рекомендации для самостоятельной работы
Самостоятельная работа студентов является основным способом овла-
дения учебным материалом в свободное от обязательных учебных занятий
время.
Целями самостоятельной работы студентов являются:
-систематизация и закрепление полученных теоретических знаний и практических умений студентов;
-углубление и расширение теоретических знаний;
-формирование умений использовать нормативную, правовую, спра-
вочную документацию и специальную литературу;
-развитие познавательных способностей и активности студентов:
-формирования самостоятельности мышления, способностей к само-
развитию, самосовершенствованию и самореализации.
Запланированная в учебном плане самостоятельная работа студента рассматривается как связанная либо с конкретной темой изучаемой дисци-
плины, либо с подготовкой к курсовой, дипломной работе, а также к защи-
те ВКР. В данном разделе рассматривается только самостоятельная работа первого вида.
Самостоятельная работа выполняется в два этапа: планирование и ре-
ализация.
Планирование самостоятельной работы включает:
-уяснение задания на самостоятельную работу;
-подбор рекомендованной литературы;
-составление плана работы, в котором определяются основные пунк-
ты предстоящей подготовки.
Составление плана дисциплинирует и повышает организованность в
15
работе.
На втором этапе реализуется составленный план. Реализация включа-
ет в себя:
-изучение рекомендованной литературы;
-составление плана (конспекта) по изучаемому материалу (вопросу);
-взаимное обсуждение материала.
Необходимо помнить, что на лекции обычно рассматривается не весь материал. Оставшаяся восполняется в процессе самостоятельной работы. В связи с этим работа с рекомендованной литературой обязательна.
Работа с литературой и иными источниками информации включает в себя две группы приемов: техническую, имеющую библиографическую направленность, и содержательную. Первая группа – уяснение потребно-
стей в литературе; получение литературы; просмотр литературы на уровне общей, первичной оценки; анализ надежности публикаций как источника информации, их относимости и степени полезности. Вторая – подробное изучение и извлечение необходимой информации.
Для поиска необходимой литературы можно использовать следующие способы:
-поиск через систематический каталог в библиотеке;
-просмотр специальных периодических изданий;
-использование материалов, размещенных в сети Интернет.
Для того, чтобы не возникало трудностей понимания текстов учебни-
ка, монографий, научных статей, следует учитывать, что учебник и учебное пособие предназначены для студентов и магистрантов, а монографии и ста-
тьи ориентированы на исследователя. Монографии дают обширное описа-
ние проблемы, содержат в себе справочную информацию и отражают по-
лемику по тем или иным дискуссионным вопросам. Статья в журнале крат-
ко излагает позицию автора или его конкретные достижении в исследовании какой-либо научной проблемы.
16
В процессе взаимного обсуждения материала закрепляются знания, а
также приобретается практика в изложении и разъяснении полученных знаний, развивается речь.
При необходимости студенту следует обращаться за консультацией к преподавателю.
Составление записей или конспектов позволяет составить сжатое представление по изучаемым вопросам. Записи имеют первостепенное значение для самостоятельной работы студентов. Они помогают понять построение изучаемого материала, выделить основные положения, просле-
дить их логику.
Ведение записей способствует превращению чтения в активный про-
цесс. У студента, систематически ведущего записи, создается свой индиви-
дуальный фонд подсобных материалов для быстрого повторения прочи-
танного. Особенно важны и полезны записи тогда, когда в них находят от-
ражение мысли, возникшие при самостоятельной работе.
Можно рекомендовать следующие основные формы записи: план, кон-
спект, тезисы, презентация.
План – это схема прочитанного материала, краткий (или подробный)
перечень вопросов, отражающих структуру и последовательность материа-
ла. Подробно составленный план вполне заменяет конспект.
Конспект – это систематизированное, логичное изложение материала источника. Объем конспекта не должен превышать 10 страниц. Шрифт
Times New Roman, кегль 14, интервал 1,5. Список литературы должен со-
стоять из 5-8 источников, по возможности следует использовать последние издания учебных пособий и исследований.
Тезисы — это последовательность ключевых положений из некоторой темы без доказательств или с неполными доказательствами. По объему те-
зисы занимают одну страницу формата А4 или одну – две страницы в уче-
нической тетради. В конце тезисов студент должен сделать собственные выводы.
17
Презентации по предложенной теме составляются в программе Power Point или Impress. Количество слайдов должно быть не менее 15 и не пре-
вышать 20 слайдов. Кроме текста на слайдах можно создавать схемы и таб-
лицы. Шрифт должен быть читаемым, например, шрифт черного цвета на светлом фоне или светлый шрифт на темном фоне. Также шрифт не должен быть слишком мелким. В слайдах указываются только основные тезисы,
понятия и нормы.
4.2 Темы для самостоятельного изучения
1 Остовные деревья.
2.Динамическое программирование: задача о рюкзаке.
3.Алгоритм Дейкстры поиска кратчайших путей в графах.
4.Реализация основных операций над списками как методы класса List в
языке Си#.
5.Реализация основных операций над массивами как методы класса Array
в языке Си#.
4.3 Учебно-методическое обеспечение самостоятельной работы
1. Комбинаторные алгоритмы для программистов: учебное пособие/ Ко-
стюкова Н. И. Интернет-Университет Информационных Технологий (ИН-
ТУИТ), 2016.
2. Алгоритмы и структуры данных: Лабораторный практикум. Учебное по-
собие. Синюк В. Г., Рязанов Ю. Д. Белгород: Белгородский государствен-
ный технологический университет им. В.Г. Шухова, ЭБС АСВ, 2013.
3. Графы и их применение. Комбинаторные алгоритмы для программи-
стов: учебное пособие. Костюкова Н. И. Москва: БИНОМ. Лаборатория знаний, Интернет-Университет Информационных Технологий (ИНТУИТ),
2013.
4. Структуры и алгоритмы обработки данных. Примеры на языке СИ:
18
Учебное пособие. – Финансы и статистика, 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. Написать функцию добавления элемента в конец односвязного списка.
Задача 2. Вставьте элемент 3 в упорядоченный односвязный список 1, 2, 4, 5.
Задача 3. В двусвязный список 2, 1, 6, 7, 10, 3, 12, 15 добавить элемент 888
между 10 и 3.
19
Задача 4. Написать несколько функций для работы со структурой «Работ-
ники» (см. лекции).
Задача 5. Написать процедуру инициализации двусвязного списка.
Раздел 3: " Типы данных. Структуры хранения данных Задача 1. На основании приведенной в лекции функции реализуйте про-
грамму, в которой выполняется переборный алгоритм методом поиска в ширину.
Задача 2. Найдите вершину графа, из которой выходит наибольшее число ребер.
Задача 3. Найти количество компонент связности графа.
Задача 4. Неориентированный граф называется двудольным, если его вершины можно раскрасить в два цвета так, что концы любого ребра — разного цвета. Составить алгоритм проверки, является ли заданный граф двудольным, в котором число действий не превосходит C · (число рёбер +
число вершин).
/Указание: (а) Каждую связную компоненту можно раскрашивать отдель-
но. (б) Выбрав цвет одной вершины и обходя ее связную компоненту, мы определяем единственно возможный цвет остальных.
Замечание. В этой задаче безразлично, производить поиск в ширину или в глубину.
/
Задача 5. Имеется семь городов, соединенных некоторой сетью дорог. В
каком городе необходимо провести конференцию так, чтобы суммарный путь всех делегатов, по одному из каждого города, был минимален.
20