- •1. Понятие алгоритма: рекурсивные функции, системы текстовых замен.
- •2.Системы счисления, переводы чисел из одной позиционной системы в другую.
- •3/4.Понятие подпрограммы, функции, возвращающей/не возвращающей значение в
- •5.Передача параметров в подпрограмму,параметры входные и выходные,параметры,передаваемые по значению и по адресу.
- •6.Использование подпрограмм, параметры формальные, локальные, глобальные, обращения к подпрограммам, фактические параметры.
- •8.Статические и динамические переменные,динамическая память,работа с динамическими переменными.
- •9.Понятие линейного связного списка, типы списков, представление стека с помощью массива, пример использования стека.
- •10.Использование динамич. Переменных для представл. И работы со стеком.
- •11.Очередь,реализация очереди массивом.
- •12.Очередь, представление и реализация основных операций с помощью динамических переменных.
- •13.Реализация основных операций со списком:добавление, удаление, поиск.
- •14.Деревья,основные операции над деревьями, представление дерева массивом.
- •15.Двусвязные линейные списки, построение и обход бинарного дерева.
- •16.Операции поиска и удаления в бинарном дереве.
- •17.Понятие графа, представление графа в эвм.
- •18.Представление графа списком инцидентности,алгоритм обхода графа в глубину.
- •19.Представление графа списком списков,алгоритм обхода графа в ширину.
- •20.Технологии программирования,концепции,заложенные в ооп.
- •21.Основные понятия ооп:абстракция, инкапсуляция,полиморфизм.
- •22.Понятие объекта,его состояние и поведение,классы,определение класса и объявление класса.
- •23.Статистические,дружественные и виртуальные поля и методы,особенности их использования.
- •24.Абстрактные классы,их назначение и использование.
- •25.Понятие области видимости:общие,личные,защищенные и опубликованные поля и методы объекта.
- •26.Указатель This и перегрузка методов.
- •27.Использование классов,различные способы инициализации.
- •28.Использование классов,работа с массивами и указателями на объекты.
- •29.Наследование,пример использования наследования.
- •30.Конструкторы и деструкторы, их значение и использование.
- •31.Архитектура пк, основные функциональные устройства и их значения.
- •32.Мп с точки зрения программиста,регистры общего назначения.
- •33.Оперативная память,понятие исполняемого и физического адреса,сегментные регистры.
- •34.Регистр флажков, его назначение и использование.
- •35.Форматы данных и форматы команд.
- •36.Адресация операндов,способы адресации,примеры команд с различными способами адресации.
- •37.Структура программы на Ассемблере.Стандартные директивы сегментации.
- •38.Формат команды и директивы на Ассемблере.Примеры команд и директив.
- •39.Алфавит,слова,константы,переменные и выражения в Ассемблере.
- •40.Директивы определения данных и памяти.
- •41.Команды прерывания, команды работы со стеком.
1. Понятие алгоритма: рекурсивные функции, системы текстовых замен.
Алгоритм — конечная последовательность действий, приводящих к результату.
Терминистический — для любой последовательности шагов алгоритма, он заканчивается
за конечное число шагов.
Детерминированный — независимо от количества шагов результат определяется однозначно.
Детерминистический — нет никакой последовательности в выборе следующего шага.
Свойства алгоритма:
1.Конечность 2.Определенность 3.Результативность 4.Массовость
5.Состоит из конечного числа шагов 6.Эффективность
Алгоритм Евклида — Находит НОД двух чисел (вычитает наиб. и наим. и сравнивает)
Существование или не существование можно определить, если найти математический объект, который будет существовать тогда, когда существует алгоритм.
1) Оператор рекурсии строит рекурсивную функцию следующим образом: значение искомой функции при нулевом значении главного дополнительного аргумента считать значением функции f1, а для последующего значения главного дополнительного аргумента значение функции f2. Для предыдущего значения ГДА и для значения ВДА, совпадающего со значением искомой функции на предыдущем шаге : f(0)=f1;f(i)=fi(i,f(i)); Пример (для функции f(x)=x-1):
f::=R {φ0, ψ2, 1(x, y), x(y)}
f (0)=y0=0
f(1)=f2(0,0)= ψ2,1(0,0)=0
f(2)= f3(0,0)= ψ2,1(1,0)=1
2)Оператор подстановки и суперпозиции: Сначала вычисляются значения f1 и f2 и используют как аргумент для вычисления функции F: Ʈ(y)=λ(λ(y))=λ(y’)=y’’
3)Оператор минимизации или построения по первому нулю.
f::=μ{f1,y}; f(x1,..xn)= μ{f1(x1,..xn, y),y}
Замена s->t применение правила v->w, если есть слова a,v,w,z ЄV*, такие что справедливо: s=a*v*z; t=a*w*z
2.Системы счисления, переводы чисел из одной позиционной системы в другую.
Система счисления — совокупность правил наименований и записи числа.
Позиционные/Непозиционные — значение цифры числа зависит/не зависит от ее положения.
1. 2->10 2. 8->10. 3. 10->2 4. 2->8 5. 8->2 6.8->16.
3/4.Понятие подпрограммы, функции, возвращающей/не возвращающей значение в
С/С++, описание и использование.
Подпрограмма — отдельная структурная единица, имеющая собственное имя, реализующая вспомогательный алгоритм, который неоднократно используется в основной программе или в другой подпрограмме, с различными значениями этих величин, называемых параметрами.
Назначение:
1)Позволяет избегать дублирования программы, делает ее короче.
2)Делает структуру программы четкой и более понятной.
3)Подпрограммы позволяют расширять языки программирования, добавив новые
функции, операции, операторы, процедуры.
Функция — именованная последовательность описаний и операторов, выполняющая какое-либо законченное действие. Может принимать параметры возвращать значения.
Пример.
Функция возвращающая сумму 2-х чисел:
#include <iostream>
Using namespace std;
Int sum(int x,int y){return x+y;}
Int main() {int a=5,b=6,c; C=sum(a,b); Cout<<”sum=”<<c<<endl; Cout<<”sum=”<<sum(a,b);
Return 0; }
В С\С++ используется один тип подпрограмм — функция, но они могут выдавать один результат и тогда обращение к ним — указатель функции и в этом случае обращение-операнд, и когда несколько результатов и выходные параметры-результаты, а в С — это функции не возвращающие значение.
Пример.
#include <stdio.h>
Void p (int k(по значению),int *d(по адресу указатель))
{ Int j;*d=1; For (j=2;j<=k;j++) *d=*d*j; Return; }