Дисциплина Алгоритмы и структуры данных

Министерство образования и науки Российской Федерации

ФГБОУ ВО «Ярославский государственный педагогический университет им. К.Д. Ушинского»

У Т В Е Р Ж Д А Ю

Проректор по учебной работе

__________________В.П. Завойстый

«____»_______________ 201_ г.

Программа учебной дисциплины

Наименование дисциплины:

Алгоритмы и структуры данных

Рекомендуется для направления подготовки:

44.03.05 Педагогическое образование

(профиль «Информатика и информационные технологии в образовании»,

«Математическое образование»)

Квалификация (степень) выпускника: бакалавр

Разработчики:

Утверждено на заседании кафедры

теории и методики обучения информатике

« » 201 г.

Протокол № ____

Заведующий кафедрой ТиМОИ_____________________ П.А. Корнилов

1. Цели и задачи дисциплины:

Цель дисциплины «Развивающие игры» - формирование системы знаний и умений в области методов представления данных в памяти ЭВМ, основных алгоритмов, освоение методов решения задач.

Основными задачами курса являются:

• понимание

  • межпредметных связей математических методов принятия решений в различных условиях;

  • основных математических игр и их стратегий решения;

  • связи оптимальных решений с рекуррентными последовательностями.

• овладение навыками

  • решения прикладных задач, специфических для теории игр.

• развитие умений

  • осуществлять поиск и отбор информации, необходимой для осуществления поставленной цели

1. Место дисциплины в структуре образовательной программы (ОП):

Дисциплина включена в обязательную часть ОПОП.

3. Перечень планируемых результатов обучения по дисциплине:

4.Объем дисциплины и виды учебной работы

Общая трудоемкость дисциплины составляет 2 зачетные единицы.

5. Содержание дисциплины

5.2. Разделы дисциплин и виды занятий

6. Перечень учебно-методического обеспечения для самостоятельной работы обучающихся по дисциплине

6.1. Содержание самостоятельной работы студентов по темам

6.2. Тематика курсовых работ (проектов)

Курсовые работы (проекты) не предусмотрены.

6.3. Примерная тематика рефератов

Рефераты не предусмотрены.

7. Фонды оценочных средств

7.1. Фонд оценочных средств для проведения текущей аттестации обучающихся по дисциплине

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

Критерии оценки видов работ

Рейтинговая суммарная оценка за семестр складывается из следующих рейтинговых оценок:

- посещение лекционных занятий или отсутствие на занятии – 1 балл за посещение всех занятий, посещение практических и лабораторных занятий – 1 балл за посещение всех занятий;

• характер работы на практических занятиях: +1 балл за активную работу, решение задач у доски на всех занятий по теме;

• выполнение домашних и практических работ – по 1 баллу за каждую решенную задачу, но не более 5 баллов за одну работу;

• контрольная работа – по 1 баллу за каждую решенную задачу, всего за 10 заданий можно получить максимум 10 баллов;

• доклад – оценивается по 5-балльной шкале;

К зачету допускаются студенты, набравшие 36 и более баллов.

Рейтинг план

Примеры заданий для практических занятий

1. Игра Баше

Правила игры:

Играют двое. Из n палочек, играющие поочередно берут не менее одной и не более k штук. Проигрывает тот, кто вытаскивает последнюю палочку.

Задание:

Написать процедуру с именем:

procedure player(номер игрока) (var n,k:integer;var a:integer);

(номер игрока)-число от 1 до 30 (номер в протоколе конкурса)

где

n – количество оставшихся палочек,

k – максимальное количество палочек, которое можно брать,

а – количество палочек взятых игроком из числа оставшихся палочек.

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

Игрокам запрещается изменять значение n и k. Нарушителю правил засчитывается поражение.

1. Решите игру Баше на бумаге для указанных исходных данных:

а) если оба игрока делают ходы в соответствии с выигрышной стратегией

б) если второй игрок берет всегда одну спичку

в) если первый игрок берет всегда 2 спички

(другие игры – аналогично)

Критерии оценивания заданий, выполненных на практических занятиях

Домашняя работа: решение задач

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

Доклад

На практических занятиях предусмотрено выступления студентов с устным докладом (5-7 минут) по заранее выбранной тематике.

Доклад – подготовленное устное выступление на определённую тему, включающее постановку проблемы; изложение тезисов (положений), доказательств и примеров; выводы.

Доклад имеет следующие признаки:

- включает основные тезисы (положения), которые подкреплены доказательствами и примерами;

- допускает обоснованную субъективную позицию;

- ориентирован на устное изложение текста и подразумевает общение с аудиторией, возможность и способность донести до неё информацию по проблеме исследования, умение доказать свою точку зрения.

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

Примерные темы докладов

1. Коллективные игры без ограничения числа и качества участников, обстановки. Правила. Стратегии. Примеры игр.

2. Парные игры. Типы выигрышных стратегий для конечных игр.

3. Виды соревнований. Круговая система организации соревнований.

4. Виды соревнований. Швейцарская система организации соревнований.

5. Виды соревнований. Итальянская система организации соревнований.

6. Виды соревнований. Система с выбыванием.

7. Виды соревнований. Смешанная система организации соревнований.

8. Виды соревнований. Блицтурниры.

9. Принятие решений в ситуациях с неполной информацией. Понятие математического ожидания действия и его использование.

Критерии оценивания доклада

Контрольная работа

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

Контрольная работа выполняется на аудиторном занятии, проводится 1 раз в конце семестра с целью диагностики уровня освоения студентами программы курса и возможной корректировки учебного процесса. Работа рассчитана на 2 академических часа. Контрольная работа состоит из 10 задач, требующих поиска обоснованного ответа.

Выполнение этой работы является подтверждением освоения студентом разделов курса и наряду с другими требованиями становится основанием для допуска к экзамену.

Примерный вариант контрольной работы

1. Решите игру Баше для указанных исходных данных:

а) если оба игрока делают ходы в соответствии с выигрышной стратегией

б) если второй игрок берет всегда одну спичку

в) если первый игрок берет всегда 2 спички

1. Решите игру Ним для указанных исходных данных, если оба игрока делают ходы в соответствии с выигрышной стратегией.

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

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

4. Решите игру Чет для указанных исходных данных, если первый игрок всегда берет две монетки, а второй одну.

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

6. Решите игру Спички Бергсона для указанных исходных данных, если первый игрок на номере хода, кратного двум, берет минимальное количество спичек, а некратного двум – максимальное.

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

8. Решите игру Кейлеса для указанных исходных данных, если первый игрок взял два крайних карандаша справа, а второй игрок должен победить.

9. Решите игру 24 карты, если первый игрок взял туза. Оба играют в соответствии с выигрышной стратегией.

Критерии оценивания заданий, выполненных на контрольной работе

7.2. Фонд оценочных средств для проведения промежуточной аттестации обучающихся по дисциплине

7.2.1. Требования к проведению промежуточной аттестации по дисциплине:

В качестве промежуточной аттестации по данной дисциплине является зачет.

Зачет является итогом учебной деятельности студента в течение семестра.

Допуск к зачету предполагает:

1. суммарный балл должен быть не менее 36;

2. контрольная работа должны быть оценена не ниже 6 баллов.

7.2.2 Критерии оценки результатов прохождения студентом промежуточной аттестации по дисциплине

* соответственно форме промежуточной аттестации по учебному плану

7.2.3 Спецификация оценочных средств

7.2.4. Описание оценочных средств для проведения промежуточной аттестации

Наименование оценочного средства

1. Ответ на зачете.

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

1. Определитель.

2. Игра Баше.

3. Игра Чёт.

4. Игра 4 карты.

5. Спички Бергсона.

6. Игра Кейлеса.

7. Ним.

Перечень вопросов для самоподготовки к зачету

1. Математические игры. Симметричные стратегии.

2. Математические игры. Инварианты.

3. Математические игры. Связь оптимальных решений с рекуррентными последовательностями.

4. Математические игры. Числа Спрага – Грюнди.

5. Различные способы организации соревнований.

6. Комбинационные игры.

7. Использование двоичной системы счисления для решения парных конечных игр.

8. Ним-сумма в математических играх.

Критерии оценивания

8. Перечень основной и дополнительной литературы, необходимой для освоения дисциплины

а) основная литература

1. Салмина Н.Ю. Теория игр [Электронный ресурс] : учебное пособие / Н.Ю. Салмина. — Электрон. текстовые данные. — Томск: Томский государственный университет систем управления и радиоэлектроники, Эль Контент, 2012. — 92 c. — 978-5-4332-0079-1. — Режим доступа: http://www.iprbookshop.ru/13870.html

2. Арсак Ж. Программирование игр и головоломок. М.: Наука.Гл. ред. физ. мат. лит., 1990. 224 с.

3. Гарднер М. Математические головоломки и развлечения / [перевод с англ. Ю. Данилов]. - М.: АСТ; Зебра Е, 2010. – 640 с.

б) дополнительная литература

1. Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. — М.: ФИМА, МЦНМО, 2006. —400 с.

2. Меньшиков И.С. Лекции по теории игр и экономическому моделированию. - М.: МЗ Пресс, 2006. - 208 с.

3. Наумова Н.И. Вектор Шепли в ТП-кооперативных играх. Методическое пособие, СПб.. 2002

4. Оуэн Г. Теория игр. М.: УРСС, 2004

5. Шень А. Игры и стратегии с точки зрения математики. – М.: МЦНМО, 2007. - 40 с.

в) программное обеспечение

1. Среда программирования;

2. Программное обеспечение для организации турниров программ.

12. Перечень ресурсов информационно-телекоммуникационной сети «Интернет», необходимых для освоения дисциплины

1. Федеральный портал «Российской образование» http://www.edu.ru

2. Единая Коллекция цифровых образовательных ресурсов http://school-collection.edu.ru

3. Федеральный центр информационно-образовательных ресурсов http://fcior.edu.ru

4. Сайт «Теория и методика обучения информатике» http://timoi.gnomio.com/

5. Научная электронная библиотека «КиберЛенинка» http://cyberleninka.ru/

6. Сайт Института Развития Образования Ярославской области http://iro.yar.ru

7. Поисковые системы https://www.yandex.ru/ , https://www.google.ru

8. Сайт дистанционной подготовки по информатике - http://informatics.mccme.ru/

9. Сайт учителя информатики К.Ю. Полякова – http://kpolyakov.spb.ru

10. Методические указания для преподавателя и обучающихся по освоению дисциплины

В соответствии с требованиями ФГОС ВО по направлению подготовки «Педагогическое образование» в программе данного курса предусмотрено использование в учебном процессе активных форм проведения занятий и организации самостоятельной работы.

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

Самостоятельная работа обучающегося – это вид учебной, научно-исследовательской деятельности, направленный на развитие его компетенций, организуемый самим обучающимся в наиболее удобное с его точки зрения время, контролируемый обучающимся в процессе и по результату деятельности, на основе опосредованного системного управления со стороны преподавателя. Самостоятельная работа является неотъемлемой частью учебного процесса и осуществляется в объеме в соответствии с утвержденной рабочей программой дисциплины «Развивающие игры».

Самостоятельная работа обеспечивает подготовку студента к контрольной работе и зачету по дисциплине «Развивающие игры».

Самостоятельная работа включает следующие виды работ:

• работа с лекционным материалом, предусматривающая проработку конспекта лекций и учебной литературы;

• выполнение домашнего задания к занятию (решение задач, выполнение упражнений);

• подготовка к практическим занятиям;

• подготовка к докладу;

• подготовка к контрольным работам;

• подготовка к зачету.

Работа с лекционным материалом

Проработка лекционного материала сводится к прочтению конспекта лекций и/или рекомендованной литературы. Рекомендуется при самостоятельной проработке материала, во-первых, внимательно проанализировать теоретический материал, предложенный в лекциях, во-вторых, ознакомиться с материалами по соответствующей тематике из рекомендуемых источников.

Выполнение домашнего задания к занятию

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

Подготовка к практическим занятиям и контрольной работе

Практические задания – задания, направленные на формирование знаний, умений и навыков обучающихся.

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

При подготовке к практическим занятиям и контрольной работе необходимо обратиться к конспектам лекций по данному вопросу и рекомендуемым источникам, чтобы уточнить терминологию; внимательно проанализировать ход решения задач, предложенных в лекциях; самостоятельно решить по 1-2 задачи соответствующей тематики из рекомендуемых сборников задач.

Подготовка к докладу

Доклад – подготовленное устное выступление на определённую тему, включающее постановку проблемы; изложение тезисов (положений), доказательств и примеров; выводы.

Виды докладов:

1) доклад – учебное выступление на заданную тему;

2) доклад-отчёт о результатах проделанной работы (в том числе доклад на предзащите и защите курсовой работы и дипломного исследования).

Доклад имеет следующие признаки:

- включает основные тезисы (положения), которые подкреплены доказательствами и примерами;

- допускает обоснованную субъективную позицию;

- ориентирован на устное изложение текста и подразумевает общение с аудиторией, возможность и способность донести до неё информацию по проблеме исследования, умение доказать свою точку зрения.

Требования к подбору и использованию докладов:

1. Подобранный материал должен соответствовать заявленной теме доклада.

2. Используемый материал должен соответствовать уровню знаний и умений обучающихся, а также реализовывать определенную учебную задачу.

3. Теоретический материал должен подбираться с учетом требований и особенностей учебной дисциплины, в рамках которой он используется.

4. Доклад должен строиться в соответствии с определенной композицией: введение; основная часть, включающая тезисы, доказательства и примеры; вывод.

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

Общие этапы подготовки к докладу на практическом занятии:

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

Самостоятельную работу над темой доклада следует начать с изучения литературы. В поисках книг заданной тематики необходимо обратиться к библиотечным каталогам, справочникам, тематическим аннотированным указателям литературы, периодическим изданиям (газетам и журналам), электронным каталогам, Интернету. При подготовке текста доклада, презентации нужно отобрать не менее 10 наименований печатных изданий (книг, статей, сборников). Предпочтение следует отдавать литературе, опубликованной в течение последних 5 лет. Допускается обращение к Интернет-сайтам. Осуществив отбор необходимой литературы, далее необходимо составить рабочий план доклада. В соответствии с составленным планом производится изучение литературы и распределение материала по разделам доклада. Необходимо отмечать основные, представляющие наибольший интерес положения изучаемого источника. Изложение текста доклада должно быть четким, аргументированным. Изучая литературу, можно столкнуться с научной полемикой разных авторов, с различными подходами в рассмотрении вопросов. Следует учитывать все многообразие точек зрения, а в случае выбора какой-либо одной из них –обосновывать, аргументировать свою позицию. При необходимости изложение своих взглядов на проблемы можно подтвердить цитатами. Цитирование представляет собой дословное воспроизведение фрагмента какого-либо текста. Поэтому необходимо тщательно выверить соответствие текста цитаты источнику. В заключение доклада студент должен сделать выводы по теме. Продолжительность доклада не более 7 минут.

Подготовка к тесту

Тесты – это вопросы или задания, предусматривающие конкретный, краткий, четкий ответ на имеющиеся эталоны ответов. При самостоятельной подготовке к тестированию необходимо проработать лекционный материал, а также материал практических занятий по дисциплине. Заранее выяснить все условия тестирования, в частности, время, отводимое на тестирование, количество вопросов в тесте, критерии оценки результатов. Приступая к работе с тестами, внимательно и до конца прочтите вопрос и предлагаемые варианты ответов. Выберите правильные (их может быть несколько). На отдельном листке ответов выпишите цифру вопроса и буквы, соответствующие правильным ответам. Если какой-то вопрос оказался чрезвычайно трудным, то не тратьте много времени на него. Переходите к другим вопросам, после ответа на которые, нужно вернуться к пропущенным вопросам. Обязательно нужно оставить время для проверки ответов, чтобы избежать механических ошибок.

Подготовка к зачету

Для успешной сдачи зачета рекомендуется соблюдать следующие правила:

1. Подготовка к зачету должна проводиться систематически, в течение всего семестра.

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

3. 3-4 дня перед зачетом необходимо использовать для повторения: студент распределяет вопросы на первые 2-3 дня, оставив последний день свободным. Последний день используется для повторения курса в целом, чтобы систематизировать материал, а также доучить некоторые вопросы.

11. Перечень информационных технологий, используемых при осуществлении образовательного процесса по дисциплине

• Контроль знаний студентов по дисциплине осуществляется в рамках электронной среды фиксации успеваемости студентов (БРС) ЯГПУ.

• Презентации по отдельным темам курса.

12. Материально-техническое обеспечение дисциплины

Учебная аудитория для проведения занятий лекционного типа

Специализированная мебель, набор демонстрационного оборудования (мультимедийный переносной проектор, ноутбук, экран)

Microsoft Windows, номер лицензии 69108710; Microsoft Office, номер лицензии 69108710; Kaspersky Endpoint Security для бизнеса - Стандартный Russian Edition, номер лицензии 1FB6-180215-114440-5-110.

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

Специализированная мебель, 13 ПК, набор демонстрационного оборудования (мультимедийный переносной проектор, ноутбук), интерактивная доска, экран настенный, МФУ печати, выход в интернет

Microsoft Windows, номер лицензии 69582054; Microsoft Office, номер лицензии 69582054; Kaspersky Endpoint Security для бизнеса - Стандартный Russian Edition, номер лицензии 1FB6-180215-114440-5-110.