- •Билет №1
- •1. Базовые конструкции языка программирования Pascal.
- •2. Предмет мпи, его цели и задачи.
- •Билет №2
- •1. Информационная технология. Этапы развития и перспективы информационных технологий.
- •2. Охарактеризовать информатику, как науку.
- •3. Задан некоторый набор товаров. Определить для каждого из товаров, какие из них имеются в каждом магазине и каких товаров нет ни в одном магазине.
- •Билет №3
- •1. Алгебра высказываний как модель алгебры Буля, ее аксиоматическое задание. Принцип двойственности и теорема двойственности.
- •3. Операция следования или импликации ( → )
- •4. Операция эквивалентности ( ↔ )
- •2. Цели пропедевтического курса информатики
- •3. Дан целочисленный массив с количеством элементов n. Напечатать те его элементы, индексы которых являются степенями двойки (1,2,4,8,…). Задачу решить с использованием процедуры или функции.
- •Билет №4
- •1. Метод простой итерации при решении уравнения с одной переменной.
- •2. Цели школьной информатики. Компьютерная грамотность, алгоритмическая и информационная культура.
- •3. В заданном одномерном массиве поменять местами соседние элементы, стоящие на четных местах, с элементами, стоящими на нечетных местах.
- •Билет №5
- •2. Классическое понятие урока, основные цели.
- •3. Задано некоторое множество м и множество т того же типа. Подсчитать количество элементов в т и м, которые не совпадают.
- •Билет №6
- •1. Основные комбинаторные объекты и числа.
- •2. Типы уроков информатики.
- •3. Дана посл-ть действительных чисел а1,а2,…,аn. Заменить все её члены, большие данного z, этим числом. Подсчитать количество замен.
- •Билет №7
- •1.Архитектура эвм
- •2. Внеурочная работа по информатике.
- •3. Определить те имена учеников, которые встречаются во всех классах данной параллели.
- •Билет №8
- •1. Понятие о компьютерных сетях. Типы сетей. Топология. Классификация.
- •2. Функции контроля знаний учащихся.
- •3. Решите задачу линейного программирования симплексным методом. При решении задачи покажите умения отыскания исходного базиса с помощью введения искусственного базиса:
- •Билет №9
- •1. Основные понятия теории кодирования. Оптимальный код Шеннона-Фано.
- •2. Виды контроля знаний
- •3. Распечатать список учеников, фамилии которых начинаются на букву в, с указанием даты их рождения.
- •Билет №10
- •1. Теория множеств: множества и операции над множествами, основные проблемы.
- •2. Схема анализа урока
- •3. Дана строка, содержащая английский текст; слова разделены пробелами. Найти количество слов, начинающихся с буквы b.
- •Билет №11
- •2. Примерная памятка для самоанализа урока учителем
- •Билет №12
- •1. Условный экстремум: функция Лагранжа, метод множителей Лагранжа.
- •2. Классификация педагогических программных средств.
- •3. Решите задачу линейного программирования графическим методом.
- •Билет №13
- •2. Дидактические требования к современному року
- •3. Составить программу, определяющую, в каком из данных двух чисел больше цифр. Задачу решить с использованием процедуры или функции.
- •Билет №14
- •Билет №15
- •1. Основы теории распознавания образов(ро).
- •2. Психологические требования
- •Билет №16
- •1. Рекуррентные соотношения.
- •2. Предмет мпи, его цели и задачи.
- •Билет №17
- •3. Даны целые положительные числа а1,а2,…,аn. Найти среди них те, которые являются квадратами числа m.
- •Билет №18
- •1. Информационная емкость. Формула информационной емкости.
- •2. Виды контроля знаний
- •3. Дана строка. Указать те слова, которые содержат хотя бы одну букву к. Задачу решить с использованием процедуры или функции.
- •Билет №19
- •1. Метод простой итерации для слау
- •2. Понятие алгоритма.
- •Базовые алгоритмические структуры
- •3. Решите задачу линейного программирования графическим методом.
- •Билет №20
- •1. Описание процедур и функции языка программирования Pascal.
- •Описание и вызов процедур и функций
- •2. Свойства алгоритмов. Формы представления алгоритмов.
- •3. Дана строка; слова разделены пробелами. Подсчитать, сколько в ней букв r, k, t.
- •Билет №21
- •2. Классификация педагогических программных средств.
- •3. Дана строка; слова разделены пробелами. Подсчитать, сколько слов в строке.
- •Билет №22
- •2. Система методов преподавания информатики в школе. (Группы, методы)
- •3. Дана последовательность действительных чисел а1,а2,…,аn. Указать те элементы, которые принадлежат отрезку [c,d].
- •Билет №23
- •2. Объяснительно-иллюстративный метод и репродуктивный метод
- •3. Составить программу для вычисления суммы факториалов, всех чисел, кратных 3, от а до в. Задачу решить с использованием процедуры или функции.
- •Билет №24
- •1. Методы численного интегрирования дифференциальных уравнений.
- •2.Проблемный метод, частично-поисковый и эвристический метод
- •3. Заполнить таблицу размерности n*n:
- •Билет №25
- •1. Основные типы данных Pascal.
- •2. Типы уроков информатики.
- •Билет №26
- •1. Перспективы развития информационной технологии.
- •2. Информатика как школьная дисциплина.
- •Билет №27
- •1. Средства программирования в Delphi. Работа в Delphi
- •2. Классическое понятие урока, основные цели.
- •3. Дано простое число р. Найти и вывести на экран следующее за ним простое число. Задачу решить с использованием процедуры или функции.
- •Билет №28
- •1. Двойственность в линейном программировании
- •2. Схема анализа урока
- •3. Дан файл, содержащий различные даты. Каждая дата – это число, месяц и год. Найти самую позднюю дату.
- •Билет №29
- •2. Понятие алгоритма.
- •Базовые алгоритмические структуры
- •3. Заполнить таблицу размерности n*n:
- •Билет №30
- •2. Свойства алгоритмов. Формы представления алгоритмов.
- •3. Дано натуральное число п. Вычислить:
- •Билет №31
- •1. Интерполяционный многочлен Лагранжа и оценка его погрешности
- •2. Внеурочная работа по информатике.
- •3. Дана строка символов, среди которых есть одна открывающаяся и одна закрывающаяся скобка. Вывести на экран все символы, расположенные внутри этих скобок.
- •Билет №32
- •1.Система счисления с произвольным основанием.Перевод из одной с.С в другую.Операции над числами в с.С с произвольным основанием.
- •2. Функции контроля знаний учащихся.
- •3. Составить программу, которая запрашивает пароль (например, четырёхзначное число) до тех пор, пока он не будет правильно введён.
- •Билет №33
- •1.Технология «КлиентСервер». Одноранговые и распределительные системы.
- •2. Дидактические требования к современному року
- •3. Заполнить таблицу размерности n*n:
- •Билет №34
- •1.Разработка мультимедийных приложений в среде Delphi.
- •2. Примерная памятка для самоанализа урока учителем
- •3. Из данного списка спортсменов распечатать сведения о тех из них, кто занимается плаванием. Указать того, кто занимается спортом дольше всех.
- •Билет №35
- •1. Проблема разрешимости (разрешения) для класса однотипных задач. Проблема разрешимости в алгебре высказываний и способы их разрешения.
- •2. Система методов преподавания информатики в школе. (Группы, методы)
- •3. Строка содержит одно слово. Проверить, будет ли оно читаться одинаково справа налево и слева направо (т.Е. Является ли оно палиндромом).
- •Билет №37
- •1. Высказывательные формы (предикаты). Способы их задания. Логические операции над предикатами.
- •2. Информатика как школьная дисциплина.
- •3. В строке имеется одна точка с запятой (;). Подсчитать количество символов до точки с запятой и после неё.
3. Дан файл, содержащий различные даты. Каждая дата – это число, месяц и год. Найти самую позднюю дату.
program lab14;
type
date = record
day: 1..31;
mounth: 1..12;
year: 1900..2100;
end;
var
j,i: integer;
tmp: date;
a: array [1..30] of date;
c: char;
begin
j:=0; { }
repeat
inc(j);
write(' : ');
readln(a[j].day);
write(' : ');
readln(a[j].mounth);
write(' : ');
readln(a[j].year);
write(' ?(y/n): ');
readln(c);
until not (c in ['y','Y']);
{ }
tmp:=a[1];
for i:= 2 to j do
if a[i].year>tmp.year then
tmp:=a[i]
else
if a[i].year=tmp.year then
if a[i].mounth>tmp.mounth then
tmp:=a[i]
else
if a[i].mounth=tmp.mounth then
if a[i].day>tmp.day then
tmp:=a[i];
writeln(' : ',tmp.day,' ',tmp.mounth,' ',tmp.year);
end.
Билет №29
1.Основные понятия теории графов. Изоморфизм графов. Связные графы. Деревья.
Графом G(V,E) называется совокупность 2х множеств- непустого множества V(множества вершин) и множества E неупорядоченных пар различных элементов множества V(E-множество ребер).
G(V,E)=<V;E>, V ,E V V, E=E-1. Число вершин графа G обозначим p, а число ребер - q:
P:=p(G):=|V|, q:=q(G):=|E.|
Если элементами множества Е являются упорядоченные пары, то граф назы вается ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е — дугами.
Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом).
Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мулътиграфом.
Если элементами множества Е являются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества Е называются гипердугами, а граф называется гиперграфом.
Если задана функция F: V -> М и/или F: Е -> М, то множество М называ ется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа
Количество ребер, инцидентных вершине v, называется степенью(или валентностью) вершины v и обозн. d(v):
.
Обозн. минимальную степень вершины графа G через (G), а макс.- через (G):
, .
Если степени всех вершин равны k, то граф наз-ся регулярным степени k:
.Степень регулярности яв-ся инвариантом графа и обоз-ся r(G). Для нерегулярных графов r(G) не определено.
Связные графы
Пусть G=(V,U) — некоторый неориентированный граф. Если для любых вершин х, у € V, существует цепь, соединяющая эти вершины, то граф О называется связным.
Считая, что каждая вершина графа связана сама с собой цепью длины ноль, то отношение связности на множестве вершин графа будет отношением симметричным, транзитивным и рефлексивным. Следовательно, отношение связности на множестве вершин графа является отношением эквивалентности.
Задав отношение связности на множестве V вершин графа, можно с помощью такого отношения определить разбиение множества V, причем, такое, что каждое подмножество этого разбиения является множеством вершин некоторого связного подграфа графа G. Такие подграфы называются компонентами связности или просто компонентами графа G, т.е. в общем случае граф может состоять из нескольких компонент. На рис. 5 изображен граф с двумя компонентами.
Ориентированный граф связен, если соответствующий ему неориентированный граф связен, то есть компоненты ориентированного графа определяются отношением связности для соответствующего ему неориентированного графа. В то же время для ориентированного графа вводится еще понятие «сильно связный». Ориентированный граф называется сильно связным, если для каждой пары различных вершин v и w существует путь
из v в w и из w в v
Деревья
Связный граф без циклов называется деревом. Граф, состоящий из нескольких Деревьев, называется лесом. Для леса можно дать и такое определение: граф, не имеющий циклов и состоящий из k- компонент связности, называется лесом из к деревьев. Легко проверяются такие утверждения:
Граф является деревом тогда и только тогда, когда каждая пара вершин соединена одной и только одной цепью.
Дерево, имеющее п-вершин, содержит n-1 ребро,
Проверим, например, второе утверждение.
Действительно, удаление одного ребра из дерева превращает его в граф из двух деревьев, удаление из графа второго ребра превращает его в лес из трех деревьев и т.д., удалив из графа n—1 ребер, мы получим п компонент связности (n изолированных вершин). Учитывая, что леса, состоящего из более чем n-компонент не может быть, поскольку количество вершин ограничено числом п, то мы получим, что дерево содержит п-1 ребро.
Пусть задан граф G=(V,U) и пусть G'-подграф графа G. G' называ ется покрывающим деревом, если:
1. G' содержит все вершины графа ;
2. G' связно и не содержит цикла.
На рис.ба изображен граф, его покрывают деревья как на рис.66, так инарис.бв. ' ' :
Задача.
Построить для данного графа покрывающее дерево,
Алгоритм.
Рассматривается произвольный цикл в графе. Из этого цикла удаляется одно ребро.
Проверяется, имеется ли еще цикл, если нет, то переходим к пункту 3, если имеется еще цикл, то возвращаемся к пункту 1.
Имеем покрывающее дерево.
Связный (ориентированный, неориентированный) граф G=(V, U) называется двудольным графом, если множество его вершин V можно разбить на два подмножества: V= V1 V2 так, что вершины V1 соединены ребрами с вершинами V2, но вершины одного подмножества V1 или V2 не соединены ребрами между собой.
На рис.7 изображен двудольный граф на множестве вершин {1,2,3,4,5,6,7}
Существуют два основных метода представления графов в памяти ЭВМ: матричный, т.е. массивами, и связными нелинейными списками. Выбор метода представления зависит от природы данных и операций, выполняемых над ними. Если задача требует большого числа включений и исключений узлов, то целесообразно представлять граф связными списками; в противном случае можно применить и матричное представление.